基于多边形的路径查找

Question

我已经在Java中实现了基于网格的A * pathfindinder。我想作一个导航网/基于多边形探路者，但我的问题是这样的：

如果我找到了橙色的路线，然后我可以使用类似a funnel algorithm进行纠正，以获得所需路线（蓝色）。但是，如果程序计算每条路线的成本，红色和橙色，那么它会说红色是更便宜的路线。如何编程我的A *算法和/或创建我的网格，以防止这种情况发生。

Answer 1

第15章在Computational Geometry: Algorithms and Applications中描述并准确解决了这个问题：自由空间可以用梯形图描述，但使用映射找到的路径不一定是最短的。推荐的表示法（也在LaValle的Planning Algorithms (Section 6.2.4)中进行了讨论）是一种所谓的可见性图形，它具有连接障碍物顶点的边缘。

伪代码和数字可从书主页获得，Google preview也包含本章的部分内容。

Answer 2

你应该检查这个链接：http://alienryderflex.com/shortest_path/ 它解释了如何计算多边形内的最短路径，一个非常清晰的解释和代码实现。

Answer 3

对不起，我不能直接帮你解决问题，但是我们将一个基于多边形的路径查找器移植到haxe中，并且它可以编译为java（只能在swing中尝试，但可能很快会尝试slick2d），并且可以集成到Java项目进行了一些研究。它被称为hxDaedalus，并在github上，可能是一个有趣的参考点。