c++ - 给定起点和目标，如何在导航网格中找到最短路径？

Question

我用谷歌搜索“导航网格上的 A* 算法”只是为了得到错误的估计 g 值的方法，像这样

或这个

通过总结蓝色线段的长度，我们得到了g值，但它被高估了（g值应该被低估了）。该算法将返回一个优化的路径，但不保证是最短的。

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

还有其他方法可以计算导航网格中的最短路径吗？

Answer 1

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

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

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

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

或者，在计算您的 A-star 之后尝试更改路径节点，如当前所做的那样，使用类似的标准。

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

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