algorithm
*経路探索アルゴリズム
サーチ…
前書き
このトピックでは、A * Pathfindingアルゴリズム、その使用方法、および動作する理由について説明します。
将来の貢献者への注意:4x4グリッドにA * Pathfindingの例を追加しました。障害のある例がまだ必要です。
A * Pathfindingの簡単な例:障害のない迷路
次の4 x 4グリッドがあるとしましょう:
これが迷路であると仮定しよう。しかし、壁や障害物はありません。出発点(緑色の四角形)と終点(赤い四角形)のみがあります。緑色から赤色になるために、我々は斜めに動くことができないと仮定しよう。そこで、緑色の四角形から始めて、どの四角形に移動できるかを見て、青色で強調表示してみましょう:
次に進むべき四角形を選択するには、2つのヒューリスティックを考慮する必要があります。
- "g"値 - これは、このノードが緑色の正方形からどれくらい離れているかです。
- "h"値 - これは、このノードが赤い四角からどのくらい離れているかです。
- "f"値 - これは "g"値と "h"値の合計です。これは、どのノードに移動するかを指示する最後の番号です。
これらの経験則を計算するために、これは私たちが使用する式です: distance = abs(from.x - to.x) + abs(from.y - to.y)
これは「マンハッタン距離」の式として知られています。
abs(3 - 2) + abs(2 - 2) = 1
緑の四角形のすぐ左側の青い正方形の "g"の値を計算しましょう。
すばらしいです! 1.値を計算してみましょう: abs(2 - 0) + abs(2 - 0) = 4
完璧。さて、 "f"値を取得しましょう: 1 + 4 = 5
したがって、このノードの最終的な値は「5」です。
他のすべての青い四角に対しても同じことをしましょう。左上の数字は「g」の値で、右上の数字は「h」の値ですが、各正方形の中央の大きな数字は「f」の値です。
すべての青色ノードのg、h、fの値を計算しました。今、私たちはどちらを選ぶのですか?
どちらが最低のf値を有するか。
しかし、この場合、同じf値を持つ2つのノードがあります。
単に、ランダムに選択するか、または優先順位を設定します。私は通常、次のような優先順位を持つことを好みます: "右>上>下>左"
f値が5のノードの1つが「下」方向に、もう一方が「左」になります。 DownはLeftよりも優先順位が高いので、私たちは「Down」となる四角形を選択します。
私たちはヒューリスティックを計算したノードをオレンジ色にしましたが、シアン色として選択したノードにマークしました。
さて、シアンノードの周りのノードについて同じヒューリスティックを計算しましょう。
ここでも、すべてのオプションが同じf値を持つため、シアンノードからノードを選択します。
シアンノードが持つ唯一のネイバーのヒューリスティックを計算しましょう。
申し訳ありませんが、同じパターンに従うので私たちは次のようにしています:
もう一度、ノードの隣人のヒューリスティックを計算しましょう:
そこに行こう:
最後に、我々は私たちの隣に勝利の広場があることがわかります。そこで私たちはそこに移動し、私たちは完了です。