我正在尝试为世界海洋上的探路者编程。我之前在包含陆地和水单元格的单元格网格上使用了 A* 算法。但我认为更好的解决方案是拥有大陆、岛屿和多边形；计算中间空间的可见性网格(仅一次)；然后在可见性图中包含起点和终点；然后在结果图上求解 A*。环顾四周，我找到了一本名为计算几何的书，其中描述了一种计算可见性图的算法。但是，在尝试用 C++ 实现它之前 - 这听起来是个好主意吗？
据我所知，已经提出了许多不同的算法来计算可见性图，具有不同的数值复杂性。在我看来，这是一个活跃的领域，而不是已经永久解决的问题。所以在我看来，这是一个真正的问题。如果您不这么认为，请告诉我原因!
编辑: 我现在已经实现了一种算法，该算法首先在由多边形组成的世界地图上计算可见性图，其中约有 5,000 个顶点。第二步，A* 在可见性图上运行。 就运行时间和内存而言， map 的详细程度可能存在限制。目前，在我的笔记本电脑上计算可见性图大约需要 10 分钟(我相信该算法非常高效；但我也相信我的代码效率不高，可以显着加快速度)。一旦计算出可见性图，A* 就非常快。 再次感谢您的回答和评论!
最佳答案
在图上进行规划而不是单元分解是提高路径和运动规划算法性能的绝佳方法。然而，许多处理计算几何的算法都充满挑战(尤其是当您不能犯错误时)，通常最好依赖该领域专家开发的可靠计算几何库。
与其让您的解决方案过于复杂，不如指出过去 15 年路径规划方面的大部分研究都集中在概率运动规划技术上。这些技术的两个最著名的例子是快速探索随机树 (RRT) 和概率路线图 (PRM)。这些算法易于实现，有大量可用示例，并且几乎不需要深入的几何知识即可上手。
- Chapter 5 - Sampling Algorithms来自 LaValle 的“规划算法”涵盖了开始使用概率运动规划所需了解的大部分内容
- Chapter 6 - Combinatorial Algorithms from the same 遍历了大多数经典的可见性，如分解，并以警告 “警告:某些方法不切实际。在研究本章的算法时注意不要做出错误的假设。其中一些高效且易于实现，但许多可能两者都不是”
关于algorithm - 快速可见性图形求解器？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24555017/