Lae*_*tia 5 algorithm performance path-finding graph-algorithm
我正在尝试为世界海洋上的探路者编程。我以前在包含陆地和水细胞的单元网格上使用了A *算法。但是我认为更好的解决方案是拥有大洲，岛屿和多边形。计算之间的空间的可见性网格（仅一次）；然后在可见性图表中包括起点和终点；然后在结果图上求解A *。环顾四周，我发现了一本名为“计算几何”的书，其中描述了一种计算可见度图的算法。但是，在尝试用C ++实现之前-听起来像个好主意吗？
据我所知，已经提出了许多不同的算法来计算可见度图，但具有不同的数值复杂度。在我看来，这是一个活跃的领域，而不是永久解决的问题。所以在我看来，这是一个真正的问题。如果您有其他意见，请告诉我原因！
编辑：我现在实现了一种算法，该算法首先在包含约5,000个顶点的多边形组成的世界地图上计算可见性图。在第二步中，A *在可见性图上运行。就运行时间和内存而言，映射的详细程度可能存在限制。目前，在笔记本电脑上计算可见性图大约需要10分钟（我相信该算法非常有效；但是我也相信我的代码不是很有效，可以大大加快速度）。一旦计算了可见度图，A *就会非常快。再次非常感谢您给出的答案和评论！
在图形上进行规划而不是单元分解是一种改善路径和运动规划算法性能的绝妙方法。但是，许多处理计算几何的算法都充满挑战（特别是在您无法承担失误的情况下），通常最好依靠该领域专家开发的可靠的计算几何库。
除了使您的解决方案复杂化之外，还有可能值得一提的是，过去15年中有关路径规划的许多研究都集中在概率运动规划技术上。这些技术的两个最著名的示例是快速探索随机树（RRT）和概率路线图（PRM）。这些算法易于实现，提供了很多示例，并且对几何学的深入了解很少。