Aスター

ひとことで

スタートからゴールまでの最短経路を、「ここまでにかかったコスト」と「ゴールまでの残りの見積もり」の合計が小さい所から順に調べていく探索です。ゴールの方向を知っているので、全方向を調べるダイクストラ法よりずっと少ない手間で済み、しかも見積もりが実際より大きくならない限り、最短経路が保証されます。ゲームの経路探索で最も広く使われている方法です。

ゲームでの使いどころ

• 敵や仲間の移動：クリックした地点までユニットを歩かせる、敵がプレイヤーの所まで回り込む。格子の地図でも、ナビメッシュの上でも同じしくみで動く。
• 地形のコスト：沼や林を通ると遅い、危険な場所を避けたい、といった「通りにくさ」をコストに入れて、単なる最短距離でない経路を選ばせる。
• 行動の計画：経路だけでなく、「状態」をノードにすれば手順の探索にも使える（GOAP）。
• パズルやカードの手順探索：ソリティアやパネルパズルの解法探し、自動プレイのテスト。

しくみ

各ノード $n$ に 3 つの値を持たせます。

• $g(n)$：スタートから $n$ までの、見つかった中で最小の累積コスト。
• $h(n)$：$n$ からゴールまでの残りコストの見積もり（ヒューリスティック）。
• $f(n)$：その 2 つの和。$n$ を通る経路全体のコストの見積もり。

手順は次のとおりです。

1. スタートを「オープンリスト」（次に調べる候補）に入れます。
2. オープンリストから $f$ が最小のノードを取り出し、「クローズ」（確定）にします。ゴールなら終わりです。
3. その隣のノードそれぞれについて、$g + (\text{隣へ進むコスト})$ が今までの $g$ より小さければ、$g$ と「どこから来たか」を更新し、オープンリストに入れます。
4. 2 に戻ります。

最後に「どこから来たか」をゴールからたどると、経路が得られます。

見積もり $h$ の条件：$h$ が実際の残りコストを決して超えない（許容的な）とき、A* は最短経路を返します。斜めに進める格子なら、オクタイル距離

がちょうどよい見積もりです（$d_x, d_y$ は縦横のマス数）。$h = 0$ にするとダイクストラ法、$g$ を無視して $h$ だけで選ぶと最良優先探索になります。

実装のポイント

• 優先度付きキュー：オープンリストは二分ヒープで持ちます。同じノードを何度入れてもよいことにして、取り出したときに確定済みなら捨てる方法が簡単です。
• 見積もりの重み：$f = g + w \cdot h$（$w > 1$）にすると、ゴールへまっすぐ向かいやすくなり、調べるノードが減ります。最短の保証はなくなりますが、コストが最短の $w$ 倍以内に収まります。
• 1 フレームで終わらない場合：大きな地図では、1 フレームに調べるノード数の上限を決めて、数フレームに分けて探します。
• 角のすり抜け：斜めに進むとき、両隣の縦横どちらかが壁なら、角をかすめて壁にめり込みます。斜めの移動は、両隣が通れる場合だけにします。

つまずきやすい点

• 見積もりが大きすぎる：コストの最小値が 1 より小さい地形（道路が 0.5 など）があるのに、距離そのものを $h$ にすると、見積もりが実際を超えて最短でなくなります。$h$ には「最小のコスト × 距離」を使います。
• ゴールに届かない：ゴールが壁の中や閉じた部屋にあると、地図全体を調べ尽くしてから失敗します。先に届くかどうか（つながっている領域の番号）を調べておくと無駄がありません。
• 経路がカクカク：格子の経路は 8 方向の折れ線です。そのまま歩かせるとロボットのように見えるので、見通しのきく点を飛ばしたり、ファネル法で引き締めたりします。

デモで試すこと

1. 水色が調べ終えたセル、黄色が次の候補です。A* はゴールの方向へ伸びるように探し、少ないセルでゴールに着きます。
2. 「ダイクストラ法」にすると、スタートから全方向へ同心円状に広がり、調べるセルがずっと増えます。経路のコストは同じ（100%）です。
3. 「最良優先」にすると、調べるセルはさらに減りますが、コの字の壁に入り込んだり、沼を突っ切ったりして、経路のコストが 100% を超えることがあります。
4. 「見積もり h の重み」を上げると、調べるセルが減る代わりに、最短との比が少しずつ悪くなります。地図をクリックして、いろいろな場所をゴールにしてみてください。