artificial-intelligence - 使用 2D 多边形而不是航路点的 AI 寻路 - 有推荐的算法吗？

Question

我正在尝试在一系列凸多边形而不是路径点上使用路径查找。更复杂的是，多边形是由用户创建的，并且可能具有不一致的顶点。例如:

我们知道这个对象是 X 宽乘以 Y 深，并且多边形在某些位置有顶点。是否有一种特定的算法可以在将整个对象保持在多边形中的同时找到达到目标的最快方法(如果我理解正确，A * 仅适用于航路点)？您如何处理不是同一对象但位于同一位置的顶点？

编辑:多边形是凸的；它是 2 个独立的多边形，边缘在线。此外，您如何实现 * 寻路，因为基于节点的系统无法在“无限”分辨率多边形中工作？

Answer 1

一般来说，所有最短路径段的终点都是多边形顶点或起点和终点。如果您构建一个包含所有这些段的图(从开始到每个“可见”多边形顶点，从目标到每个“可见”多边形顶点，以及从每个多边形顶点到每个其他多边形顶点)并在该图上运行 A* ，你有你的最佳路径。为 A* 构建图的成本是:

• 对于每个顶点，进行可见性测试以查找可见顶点:简单算法(对于每对顶点，查看从一个顶点到另一个顶点的线段是否位于多边形内)是 O(n^3)。构建凸多边形并独立处理它们，或者使用更智能的“径向扫描”算法可以大大降低这个，但我怀疑它仍然在 O(n^2) 左右。
• 对于每个查询(从起点到目标点)，O(n) 用于可见性测试以找到它可以看到的所有顶点。

如果您只打算应用一次 A*，那么为单次遍历构建 A* 图的固定部分的代价可能会有些高。另一种方法是在使用时逐步构建图形:

可以找到实现上述方法的 Java 代码 here .