基于多边形的寻路

Question

我在Java中实现了一个基于A*pathfindinder的基本网格.我想制作一个基于导航网格/多边形的探路者,但我遇到的问题是:

如果我找到橙色路线,那么我可以使用类似漏斗算法的东西来拉直它以获得所需的路线(蓝色).但是,如果程序计算每条路线的成本,红色和橙色,那么它会说红色路线的价格更便宜.如何编程我的A*算法和/或创建我的网格,以便不会发生这种情况.

Answer 1

《计算几何：算法与应用》第 15 章准确描述并解决了这个问题：自由空间可以用梯形图描述，但使用梯形图找到的路径不一定是最短的。推荐的表示（也在 LaValle 的规划算法（第 6.2.4 节）中讨论）是所谓的可见性图，它具有连接障碍物顶点的边。

伪代码和图表可从本书主页获得，Google 预览也包含该章的部分内容。