1

タワーディフェンスゲームを書いていて、チュートリアルなどからA *パスファインディングアルゴリズムを実装していますが、まだコード化できない状況に遭遇しました。下の図を検討してください。シアンのノードはこれまでに見つかった最短経路を表し、紫のノードは検査されたノードを表し、濃い灰色のノードは壁を表します。

私がA*アルゴリズムについて知っていることから、以下の状況のパスを計算するために、それは...

  1. 「開始」から開始し、上位ノードが使用可能かどうかを確認します。です。GスコアとHスコアを計算します。右、下、左のノードでも同じことをします。
  2. 右側のノードのFスコアが最も低いことを検出します（F = G + H）。次に、手順1と同じ方法を繰り返して次のノードを見つけ、「開始」ノードを親としてマークします。
  3. このパターンを継続し、「Cトラップ」の中央にあるノードに到達します。これは、このノードのFスコアがこれまでで最も低いためです。
  4. 上部、右側、下部、および左側のノードがすべて閉じていることを検出します。次に、A *はこのノードを閉じたものとしてマークし、このノードをそのままにしておくことを理解して、最初からやり直します。

＃4の直後はどうなりますか？ A *は、新しく閉じられたノードをスキップして、同じパスに沿ってGスコアとHスコアを再検査しますか？また、このSWFを使用してこのシナリオを描画すると、ここで提案されているように、トラップを補うためにより多くのノードが検出されたことを示します。なんで？

A*問題のグラフィック

4

1 に答える 1

1

あなたが見逃しているように見えるのは、A * はグリッドに沿って移動する単一のユニットのようなものではなく、壁にぶつかったときにバックトラックするということです。これは、オブザーバーがグラフの周りのさまざまなノードを見て、次のノードが最短経路にある可能性が最も高いと常に考えているようなものです。

したがって、上記のステップ 4 は発生しません。A* は、ノードが最適パスの一部ではないと判断した場合、そのノードを閉じたものとしてマークしません。アクセスするclosedとすぐに、表示されたすべてのノードをリストに追加するだけです。また、「最初からやり直す」ことはありません。常に次の「最も可能性が高い」ノードを調べます。ここで「最も可能性が高い」とは、によって並べ替えられた優先度キューf(x)の先頭を意味します。

したがって、上記の例では、A* は次に青いノードの 1 つにジャンプします。これは、それらがすべてopenリストにあり、すべてが同じf(x)値を持っているためです。技術的には次のいずれかを考慮することができますが、正しいタイブレーク基準を使用すると、最後に最も近い 2 つのうちの 1 つが採用されます。

于 2012-10-03T12:23:05.693 に答える