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

Question

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

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

编辑：多边形是凸的；它是 2 个独立的多边形，边在一条线上。另外，您如何实现*寻路，因为基于节点的系统在“无限”分辨率多边形中不起作用？

Answer 1

通常，所有最短路径段都将具有多边形顶点或起点和目标点作为终点。如果您构建了一个包含所有这些段的图（从开始到每个“可见”多边形顶点，从目标到每个“可见”多边形顶点，以及从每个多边形顶点到每个其他多边形顶点）并在其上运行 A* ，你有你的最佳路径。为 A* 构建图的成本是：

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

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

可以在此处找到实现上述方法的 Java 代码。