algorithm
*経路探索アルゴリズム

前書き

A * Pathfindingの簡単な例：障害のない迷路

次の4 x 4グリッドがあるとしましょう：

これが迷路であると仮定しよう。しかし、壁や障害物はありません。出発点（緑色の四角形）と終点（赤い四角形）のみがあります。緑色から赤色になるために、我々は斜めに動くことができないと仮定しよう。そこで、緑色の四角形から始めて、どの四角形に移動できるかを見て、青色で強調表示してみましょう：

次に進むべき四角形を選択するには、2つのヒューリスティックを考慮する必要があります。

1. "g"値 - これは、このノードが緑色の正方形からどれくらい離れているかです。
2. "h"値 - これは、このノードが赤い四角からどのくらい離れているかです。
3. "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値を持つため、シアンノードからノードを選択します。

シアンノードが持つ唯一のネイバーのヒューリスティックを計算しましょう。

申し訳ありませんが、同じパターンに従うので私たちは次のようにしています：

もう一度、ノードの隣人のヒューリスティックを計算しましょう：

そこに行こう：

最後に、我々は私たちの隣に勝利の広場があることがわかります。そこで私たちはそこに移動し、私たちは完了です。