tem*_*def 18 algorithm artificial-intelligence heuristics a-star path-finding
假设你有一个2D网格的单元格,其中一些是用墙填充的.角色可以从一个正方形到任何与其一步水平或垂直的正方形,但不能穿过墙壁.
给定起始位置和结束位置,我们可以通过使用具有可允许启发式的A*算法找到从起始位置到结束位置的最短路径.在目前的设置中,曼哈顿距离是可以接受的,因为它永远不会高估到目的地的距离.
现在假设除了墙壁之外,世界上还有成对的传送器.踏上传送器会立即将角色传送到链接的传送器.传送器的存在打破了上面给出的允许启发式,因为通过使用传送器来减少距离,可能比通过最佳曼哈顿距离步行更快地到达目的地.例如,考虑这个线性世界,其中传送器标记为T,开始位置标记为S,结束位置标记为E:
T . S . . . . . . . . . . . . . E . T
在这里,最好的路线是步行到左边的传送器,然后向左走两步.
我的问题是:在带有传送器的网格世界中,A*的一个很好的可接受的启发式算法是什么？
谢谢!
us2*_*012 14
如果您的世界中没有太多的远程传送器,我会尝试以下启发式算法,其中MHD(a,b)是单元格a和之间的曼哈顿距离,b并且T(i)是最靠近单元格的远程传送器i:
h(x,y) = min( MHD(x,y), MHD(x,T(x)) + MHD(T(y),y) )
形成传送器的图形:
使用Dijkstra算法计算从每个节点到结尾的最短距离.
您现在可以使用特定位置和所有节点之间的距离的最小值加上从节点到结束的预先计算的距离作为启发式函数.Dijkstra算法只需作为预处理步骤运行一次.但是,如果传送器的数量是单元数量的一个较大的百分比,则使用更简单的启发式功能可能无法获得任何好处.