假设你有一个由单元格组成的二维网格，其中一些单元格被墙壁填充。角色可以从一个方块移动到任何水平或垂直相邻的方块，但不能穿越墙壁。
给定一个起始位置和一个结束位置，我们可以通过使用A*算法和一个可接受的启发式方法来找到从起始位置到结束位置的最短路径。在当前设置中，曼哈顿距离是可接受的，因为它永远不会高估到目的地的距离。
现在假设除了墙壁外，世界中还存在成对的传送门。踏上传送门会立即将角色传送到与之相连的传送门。传送门的出现打破了上述可接受的启发式方法，因为使用传送门可能比走最优的曼哈顿距离更快到达目的地。例如，考虑这个带有传送门标记为T，起始位置标记为S，结束位置标记为E的线性世界：
T . S . . . . . . . . . . . . . E . T在这里，最佳路线是走到左边的传送门，然后向左走两步。
我的问题是：在带有传送门的网格世界中，A*算法的良好可接受启发式方法是什么？
谢谢！
回答：
构建传送门的图形：
- 为每个传送门和结束位置各设一个节点。
- 每个节点之间都有一条边，形成一个完全连通的图。
- 对于边的权重，使用每个节点的目标单元格（当你进入传送门时去的地方）与所有其他节点之间的曼哈顿距离。
使用Dijkstra算法计算从每个节点到结束位置的最短距离。
现在，你可以使用特定位置与所有节点之间的距离的最小值加上从节点到结束位置的预计算距离作为启发式函数。Dijkstra算法只需作为预处理步骤运行一次。然而，如果传送门的数量占单元格总数的很大比例，你可能不会比使用更简单的启发式函数获得更多好处。
