21

假设您有一个 2D 单元格网格，其中一些被墙填充。角色可以从一个方格跨步到任何水平或垂直的方格，但不能穿过墙壁。

给定一个起始位置和一个结束位置，我们可以通过使用具有可接受启发式的 A* 算法找到从起始位置到结束位置的最短路径。在当前的设置中，曼哈顿距离是可以接受的，因为它永远不会高估到目的地的距离。

现在假设除了墙之外，世界还有成对的传送器。踏上传送器会立即将角色传送到链接的传送器。传送器的存在打破了上面给出的可接受的启发式方法，因为通过使用传送器缩短距离，可能比采取最佳曼哈顿距离步行更快地到达目的地。例如，考虑这个线性世界，传送器标记为 T，起始位置标记为 S，结束位置标记为 E：

T . S . . . . . . . . . . . . . E . T

在这里，最好的路线是步行到左边的传送器，然后向左走两步。

我的问题是：在带有传送器的网格世界中，什么是 A* 的良好可接受启发式？

谢谢！

4

2 回答 2

15

如果你的世界中没有太多的传送器，我会尝试以下启发式方法，其中MHD(a,b)是 cell 之间的曼哈顿距离a，b并且T(i)是最接近 cell 的传送器i：

h(x,y) = min( MHD(x,y), MHD(x,T(x)) + MHD(T(y),y) )
于 2013-01-20T19:29:38.747 回答
7

形成传送器的图表：

  • 每个传送器都有一个节点，末端位置有一个节点。
  • 您有一条边将每个节点连接到其他节点，形成一个完全连接的图。
  • 对于边权重，使用每个节点的目标单元格（当您进入传送器时进入的单元格）与所有其他节点之间的曼哈顿距离。

使用 Dijkstra 算法计算每个节点到末端的最短距离。

您现在可以使用特定位置与所有节点之间的距离的最小值加上从节点到末端的预先计算的距离作为启发式函数。Dijkstra 的算法只需运行一次作为预处理步骤。但是，如果传送器的数量占细胞数量的很大百分比，则与使用更简单的启发式函数相比，您可能不会获得任何好处。

于 2013-01-20T19:38:41.157 回答