在连续空间中寻找路径的算法

Question

我有一张大 map (20000 x 20000)，我偶尔会遇到多边形形状的障碍物(从 4 到 20 条边)。如何找到两点之间的路径，适合使用哪种算法可以相当快？(目前我正在将 map 拆分为单元格并使用 A* 算法查找路径但平滑度不好，因为它从一个单元格的中心传递到另一个单元格，并且对于更远的开始/结束对很慢)。你能建议哪种算法，不需要实现只是建议。

Answer 1

A* 确实是用于此任务的正确算法。这仍然是一个最短路径问题；您的“平滑度”和效率问题可能来自您将 map 划分为图上的节点的方式，而不是您用来遍历它们的技术。

为了更好地控制 Actor 在 map 上移动的方式并让他们快速找到路径，您可能希望尝试使用 navigation meshes or waypoints .这个想法是，与其在有很多很多节点的图上做 A*，不如想办法在复杂得多的图上做，通过非常广泛的路径层次结构过滤到这些路径的更精细的细节——这非常减少完成任务的时间，因为即使是最短路径问题的有效实现仍然具有很高的计算复杂度。