algorithm - 多变环境的寻路算法

Question

我无法调整 A* 算法来处理不断变化的环境。举个最简单的例子，考虑这张类似流氓的地图：

######
#!   #
###  #
#S   #
##+###
##F###
######

目标是从S到F，但为了做到这一点，玩家必须踏上!去打开门。我遇到的问题是，在 A* 中，一旦访问了一个网格点，它就会“关闭”并且无法重新输入。如何修改算法来解决这个难题？

Answer 1

您可以运行 A* 两次：

1. 首先找到!门像墙的开关（ ）的最短路径
2. 然后找到从开关到门的最短路径，那里的门是空白瓷砖。

最短路径将是这两条路径的组合。

Answer 2

在您的问题中，在 A* 中，当您访问一个点（x，y 线）时，您不会再次访问同一点，这是不正确的。

原因是在您的问题中，状态是网格中的位置，并且每个门的状态（打开或关闭）。所以一开始，在你的例子中，初始状态是 (3,1,{false})。（false 表示门已关闭）。

当你到达'！位置，新状态将是 (1,1,{true}) 所以现在当你到达门口时，你将通过门。