algorithm - 変化する環境のための経路探索アルゴリズム

Question

変化する環境を処理するために A* アルゴリズムを適応させるのに問題があります。最小限の例として、次のローグライクマップを考えてみましょう。

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

ゴールはからまで到達することSですFが、そうするためにプレイヤー!はドアを踏む必要があります。私が抱えている問題は、A * でグリッドポイントにアクセスすると、それが「閉じられ」、再入力できないことです。このパズルを解くためにアルゴリズムを変更するにはどうすればよいですか?

score 3 · Accepted Answer

A* を 2 回実行できます。

最短経路は、これら 2 つの経路の組み合わせになります。

score 2 · Accepted Answer

あなたの問題では、ポイント（x、yコード）を訪れたときにA *で同じポイントを再び訪れないというのは真実ではありません。

その理由は、問題では状態がグリッド内の位置であり、各ドアの状態 (開いているか閉じているか) であるためです。したがって、最初の例では、初期状態は (3,1,{false}) です。(false はドアが閉じていることを意味します)。

「！」に到達すると、新しい状態は (1,1,{true}) になるため、ドアに到達するとドアを通過します。

2 に答える 2