java - 基于多边形的寻路

Question

我已经用 Java 实现了一个基于网格的基本 A* 寻路器。我想制作一个基于导航网格/多边形的探路者，但我遇到的问题是:

如果我找到橙色路线，那么我可以使用类似 a funnel algorithm 的东西拉直它以获得所需的路线(蓝色)。但是，如果程序计算每条路线(红色和橙色)的成本，那么它会说红色路线最便宜。我该如何编写我的 A* 算法和/或创建我的网格，以免发生这种情况。

Answer 1

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

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