我有一张（20000 x 20000）的大地图，偶尔会有多边形障碍物（从4到20条边）。如何找到两点之间的路径，哪种算法适合使用，这样比较快？
（目前，我正在将地图拆分到单元格，并使用*算法查找路径，但平滑度不好，因为它是从一个单元格的中心传递到另一个单元格的，而且对于较远的起点/终点对，速度很慢）。
你能建议哪种算法，不需要实现只是建议。
最佳答案
A*确实是用于此任务的正确算法这仍然是一个最短路径问题；您的“平滑度”和效率问题可能来自于您将地图划分为图形上节点的方式，而不是您用来遍历它们的技术。
为了更好地控制参与者在地图上移动的方式，让他们快速找到路径，您可能希望尝试使用navigation meshes or waypoints。其思想是，与其在一个有很多节点的图上做*操作，不如在一个复杂得多的图上做*操作，通过一个由非常宽的路径组成的层次结构来过滤这些路径的更精细的细节——这大大减少了完成任务的时间，因为即使是最短路径问题的有效实现仍然有计算复杂度高。
关于algorithm - 在连续空间中寻找路径的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34073652/