适用于多变环境的路径查找算法

Question

我无法适应A *算法来处理变化的环境。作为最小的例子，考虑这个流氓般的地图：

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

的目标是得到S到F，但为了做到这一点的球员必须踩!开门。我遇到的问题是，在A *中，一旦访问了一个网格点，它将变为“关闭”并且不能重新进入。我如何修改算法来解决这个难题？

Answer 1

在你的问题中，在A *中当你访问一个点（x，y线）时，你不会再访问同一个点。

原因是，在你的问题中，状态是在网格中的位置以及每个门的状态（打开或关闭）。 所以在开始时，在你的例子中，初始状态是（3,1，{false}）。 （错误意味着门已关闭）。

当您到达'！'位置，新状态将为（1,1，{true}），所以现在当你到达门时，你将通过门。

Answer 2

您可以运行两次A *：

1. 首先找到最短路径开关（!），其中门就像是 墙
2. 然后找到最短路径，从交换机上，在那里结束门 是空白的瓷砖。

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