给定一个开始和目标,如何找到导航网格中最短的方式？

Question

我用google搜索"导航网格上的A*算法"只是为了得到错误的估算g值的方法,就像这样

或这个

通过总计蓝线段的长度,我们得到g值,但它被高估了(g值应该被低估).此算法将返回优化路径,但不保证最短路径.

我能想到的唯一方法是根据导航网格绘制可见性图.但这会花费太多内存.

有没有其他方法来计算导航网格中的最短路径？

Answer 1

为了获得更接近您的意思的最短路径，您应该停止使用固定点作为 A 星节点，即停止使用三角形中心或三角形边缘中心。

尝试在 A 星传播时移动点。例如，在三角形的边上使用 A 星节点，它们是：

• 下一个 A 星节点的三角形边与前一个 A 星节点和目的地形成的线段的交点

• 或者下一个 A 星节点的三角形边缘上距上述交点最近的点

或者，在按照当前完成的方式计算 A-star 后，尝试使用类似的标准更改路径节点。

请注意，这将使最终路径变得平滑（如绘图上的红线）。但这只会有助于减少高估，并不能保证找到您想要的最短路径。

更好的是，在使用三角形边的中心计算 A 星后，尝试使用拉绳又名漏斗算法来更改路径节点。这将为您提供 A 星输出路径所经过的三角形的最短路径。