適用於多變環境的路徑查找算法

Question

我無法適應A *算法來處理變化的環境。作爲最小的例子，考慮這個流氓般的地圖：

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

的目標是得到S到F，但爲了做到這一點的球員必須踩!開門。我遇到的問題是，在A *中，一旦訪問了一個網格點，它將變爲「關閉」並且不能重新進入。我如何修改算法來解決這個難題？

Answer 1

在你的問題中，在A *中當你訪問一個點（x，y線）時，你不會再訪問同一個點。

原因是，在你的問題中，狀態是在網格中的位置以及每個門的狀態（打開或關閉）。 所以在開始時，在你的例子中，初始狀態是（3,1，{false}）。 （錯誤意味着門已關閉）。

當您到達'！'位置，新狀態將爲（1,1，{true}），所以現在當你到達門時，你將通過門。

Answer 2

您可以運行兩次A *：

1. 首先找到最短路徑開關（!），其中門就像是 牆
2. 然後找到最短路徑，從交換機上，在那裏結束門 是空白的瓷磚。

最短路徑將是這兩條路徑的組合。