Easy A* (star) Pathfinding

ゲーム開発者であれば、キャラクター (または敵) の経路探索として A* を実装したいと常々思っているかもしれませんね。 数年前、私はそうしましたが、当時の私のプログラミングのレベルでは、現在出ている記事には問題がありました。 私は、誰でも簡単に手に取って自分のゲームで使用できるように、A*経路探索の明確なソースコード例と簡単な紹介としてこれを書きたいと思いました。 f、g、および h 変数は、Node クラスにあり、新しいノードを作成するたびに計算されます。

G は現在のノードと開始ノード間の距離です。

H は現在のノードから終了ノードまでのヒューリスティックに推定された距離です。

これを説明するために、簡単な図を見てみましょう。

Awesome ! node(0)を開始位置、node(19)を終了位置としましょう。

G

G は現在のノードと開始ノード間の距離です。

逆算すると、node(4)は開始ノードから4スペース離れていることが分かります。

H

H はヒューリスティックな推定距離で、現在のノードから終了ノードまでの距離です。 見てみると、7スペース越えて3スペース上がれば、終了ノード（node(19)）に到達していることがわかります。

ピタゴラスの定理を適用してみましょう！

この定理を適用すると、終了ノードまでの距離を計算することができます。 a² + b² = c². これを適用した後、currentNode.h = 7² + 3²のようになります。 またはcurrentNode.h = 58.

でも、58に平方根を当てはめる必要はないのでは？ いいえ！そうではありません。 すべてのノードでその計算を飛ばしても、同じ出力が得られるのです。 賢い！

ヒューリスティックでは、実際に計算できることを確認する必要があります。 また、ヒューリスティックは常に総経路の過小評価であることが非常に重要で、過大評価すると、A* はf値の点で「最善」でないかもしれないノードを介して検索することになります。

F

F はノードの総コストです。 currentNode.f = currentNode.g + currentNode.h. あるいはcurrentNode.f = 4+ 58。 Or currentNode.f = 62.

時間 f = g + h

さて、それでは大変でしたね。

この新しい f 値を使用して、すべてのノードを見て、「今、前進するために選択できる最良のノードはこれですか」と言うことができます。 すべてのノードを実行するのではなく、目標に到達する可能性が最も高いノードを選択できます。

ここで、図解します。 上は、このf値を使わずに検索するダイクストラのアルゴリズム、下は、このf値を使うA*です。

ダイクストラのアルゴリズム

そこでダイクストラのアルゴリズムを見てみよう。 ただひたすら検索し続けることがわかります。 どのノードが「最善」なのか見当もつかないので、それらすべての経路を計算します。

A* アルゴリズム

A* では、いったん障害を乗り越えると、アルゴリズムは、最も低い f と最後に到達する「最善の」チャンスを持つノードを優先させることが分かります。