algorithm - 在有障碍物的连续大地图上查找路径

Question

我正在尝试在带有一些障碍物的连续棋盘（没有网格单元）上创建游戏（例如随机点的盒子和毁坏的墙壁，地图很大）。我可以使用什么算法来解决这个问题（网格板中有类似的 A*）？我做了一些研究，我可以使用 Voronoi 图吗？

Answer 1

在 Skiena 的算法设计手册中是计算几何下的一个条目，称为“运动规划”。它为此列出了一些实现，即Motion Planning Toolkit、SWIFT++和CGAL。如果可以的话，看看那本书，我发现它读起来非常实用，虽然它并没有真正提供很多解决方案，但它总是有一些指向哪里可以找到它们。基本上，一种方法是从地图中生成合适的图形，然后使用 Dijkstra 算法（或者可能是 A*？）来找到最短路径。生成图表需要分析您可以在哪些点之间移动而不会越过障碍。