基于多边形的路径规划

Question

9

我已经用Java实现了基本的基于网格的A*路径查找。我想制作一款基于导航网格/多边形的路径查找器，但我面临的问题是：

basic polygon map with possible routes

如果我找到了橙色的路线，那么我可以使用类似漏斗算法的方法将其变直以获取期望的路线（蓝色）。然而，如果程序计算出了每条路径（红色和橙色）的成本，那么它会认为红色是更便宜的。我该如何编写我的A*算法和/或创建我的网格，以避免这种情况发生。

- angrydust

2个回答

0

很抱歉我无法直接回答你的问题，但我们将基于多边形的路径查找器移植到了Haxe上，并且它可以编译成Java（目前只尝试过Swing，但可能会尝试Slick2D），并且可以在进行一些研究后集成到Java项目中。它被称为hxDaedalus，可以在Github上找到，可能是一个有趣的参考点。

- Justinfront

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- antonakos · Accepted Answer

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

伪代码和图示可从书籍主页和Google预览获得，其中包含了本章的部分内容。