A*（A-star）
代表的な迷路探索アルゴリズムには、
・BFS
・Dijkstra’s Algorithm
・A（A-star）
があります。
BFSは最小歩数を探すアルゴリズムでした。
Dijkstra’s Algorithmはそこに通路コストの概念を追加し、
・ダークゾーンを避ける
・罠を避ける
といった判断が可能になりました。
ただし、ダイクストラも本質的には総当たり探索です。
そのため、
・ゴールとは真逆の方向
についても探索してしまいます。
そこで登場するのが、
A（A-star）
です。
A*は、
「スタート地点からのコスト」
に加えて、
「ゴールまでどれくらい近いか」
という評価も行います。
つまり、
「安全な経路を探す」
だけではなく、
「ゴールに近づく方向を優先して探す」
という考え方が追加されています。
ダイクストラをさらに賢くしたもの。
と言うとイメージしやすいかもしれません。
A*の基本概念
ダイクストラが評価していたのは、
スタート地点からここまで来るためのコスト
だけでした。
例えば、この様に右方向にゴールがある場合でも、
・右へ向かう道
・左に向かう道
両方の道のコストが同じなら、
両方を同じ優先度で探索してしまいます。
A*ではここに、
ゴールまでの予想距離
という考え方を追加します。
そのため、
ゴールから遠ざかる方向よりも、
ゴールへ近づく方向を優先的に探索するようになります。
基本構造はダイクストラと同じ
前回説明した
・これから調べる座標のリスト
・どこから来たかの記録
・調査済み座標の記録
そして
・スタート地点からその座標までの最小コスト
という考え方は、Aでもそのまま使います。
Aになっても、
基本的な流れはBFSやダイクストラと同じです。
BFSやダイクストラ、A*の違いは、
ざっくり言ってしまえば、
「queueの中からどの座標を優先して取り出して探索するか」
という部分だけです。
全体像
サンプルコードはこんな感じになります。
public class PathNode { public Vector2Int pos; public int cost; public PathNode(Vector2Int pos, int cost) { this.pos = pos; this.cost = cost; } } public List<Vector2Int> FindPathAStar( int[,] map, Vector2Int start, Vector2Int goal) { int width = map.GetLength(0); int height = map.GetLength(1); List<PathNode> queue = new List<PathNode>(); bool[,] visited = new bool[width, height]; Dictionary<Vector2Int, Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>(); int[,] costSoFar = new int[width, height]; for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { costSoFar[x, y] = int.MaxValue; } } queue.Add(new PathNode(start, 0)); costSoFar[start.x, start.y] = 0; Vector2Int[] dirs = { Vector2Int.up, Vector2Int.right, Vector2Int.down, Vector2Int.left }; while (queue.Count > 0) { // cost最小を探す int bestIndex = 0; for (int i = 1; i < queue.Count; i++) { if (queue[i].cost < queue[bestIndex].cost) { bestIndex = i; } } PathNode currentNode = queue[bestIndex]; queue.RemoveAt(bestIndex); Vector2Int current = currentNode.pos; if (visited[current.x, current.y]) continue; if (current == goal) { List<Vector2Int> path = new List<Vector2Int>(); Vector2Int p = goal; while (p != start) { path.Add(p); p = cameFrom[p]; } path.Reverse(); return path; } foreach (var dir in dirs) { Vector2Int next = current + dir; // 範囲外 if (next.x < 0 || next.x >= width || next.y < 0 || next.y >= height) continue; // 通行不能 if (map[next.x, next.y] == -9) continue; // 確定済み if (visited[next.x, next.y]) continue; int moveCost = map[next.x, next.y]; int newCost = costSoFar[current.x, current.y] + moveCost; if (newCost < costSoFar[next.x, next.y]) { costSoFar[next.x, next.y] = newCost; cameFrom[next] = current; // ゴールまでの予想距離 int heuristic = Mathf.Abs(goal.x - next.x) + Mathf.Abs(goal.y - next.y); // A*評価値 int priority = newCost + heuristic; queue.Add( new PathNode( next, priority ) ); } } visited[current.x, current.y] = true; } return null; }
今回のサンプルダンジョン
ダイクストラとの違いが分かりやすいように、
ダイクストラの時と同じダンジョンです。
スタート地点は(x3,y5)、ゴール地点は(x10,y10)。
コストも前回と同じ
・99：通行不可
・1：通常通路
・10：ダークゾーン
・50：罠
と言う設定です。
ダイクストラとの違い
ダイクストラでは、
スタート地点からの合計コスト
が、一番低い座標をqueueから取り出し、
その座標の四方向を調査して、
有効な座標があれば移動コストを加算してqueueへ登録する。
という探索方法でした。
A*では、この合計コストに
『ゴールまでの予想距離』
を加えます。
つまり、queueに登録する値は、
・スタート地点からの合計コスト
・次の座標に進むために必要なコスト
・ゴールまでの予想距離
の加算になります。(priority)
『ゴールまでの予想距離』を出す方法は
vectorの差からvector.lengthを出すなど色々ありますが、
今回はシンプルに
int heuristic = Mathf.Abs(goal.x - next.x) + Mathf.Abs(goal.y - next.y);
で求める事にします。
それでは、具体的な流れを見ていきましょう。
まず、queueから登録されている値(priority)が一番低い調査対象座標を取り出すわけですが、
・スタート地点からの合計コスト
・ゴールまでの予想距離
の合計が格納されています。
この『ゴールまでの予想距離』は調査対象座標とゴール座標との相対的な値で、
調査対象座標の四方の計算時には邪魔になりますので
調査対象座標への『スタート地点からの合計コスト』は
costSoFarから取得してきます。
costSoFar[current.x, current.y]
queueは、あくまで調査対象座標を決めるために用い、
調査の判断としてのコストはcostSoFarから取得してくるわけです。
では、続きを見ていきましょう。
調査対象座標への 『スタート地点からの合計コスト』は取得できました。
そこに、『次の座標に進むために必要なコスト』
int moveCost = map[next.x, next.y];
を加算します。
int newCost = costSoFar[current.x, current.y] + moveCost;
そこに『ゴールまでの予想距離』
int heuristic = Mathf.Abs(goal.x - next.x) + Mathf.Abs(goal.y - next.y);
を加算します。
サンプルダンジョンのスタート位置でいうと、
上下と右方向は、
『スタート地点からの合計コスト』と
『次の座標に進むために必要なコスト』の合計
はダイクストラと同じで、いずれも1になります。
違いがでるのは、
『ゴールまでの予想距離』（heuristic）で、
int heuristic = Mathf.Abs(goal.x - next.x) + Mathf.Abs(goal.y - next.y);
上方向：（10-3）+（10-6）=7+4=11
右方向：（10-4）+（10-5）=6+5=11
下方向：（10-3）+（10-4）=7+6=13
となります。
つまり、queueに登録される値（priority）
・スタート地点からの合計コスト
・次の座標に進むために必要なコスト
・ゴールまでの予想距離
は、
上方向：0+1+11=12
右方向：0+1+11=12
下方向：0+1+13=14
となり、
ゴールから遠ざかる方向の下方向の優先度が下がる事になります。
後はダイクストラと同じ
後のフローはBFSやダイクストラの時と同じです。
後はqueueが空になるか（ゴールに辿り着けない。）、ゴールに辿り着くまで、
ひたすら調査を継続することになります。
ゴールに至った時、各記録はこんな感じになります。
A*は最強なのか？
ここまでで、
・BFS
・Dijkstra’s Algorithm
・A*（A-star）
と代表的な3つのアルゴリズムを噛み砕いてきました。
BFS、ダイクストラに比べて更に無駄な探索が減り、
明らかにゴール地点に向かっているのが判るかと思います。
ちなみに、今回のマップの各アルゴリズムでの探索回数（queueに格納される座標の数）
はこんな感じになります。
| BFS | Dijkstra’s Algorithm | A* |
|---|---|---|
| 78 | 60 | 22 |
Aではしっかりとゴールに向かって探索されました。
他のアルゴリズムに比べると、最強なのでは・・・？と思ってしまいますが、
実は必ずしもそうではなかったりします。
ウィザードリィライクのダンジョンで、
自動移動の経路探索であればAは最強のアルゴリズムと言えるかもしれません。
しかし、
これがもっと広大なダンジョンで、
しかもストラテジーゲームの様に、
敵が数十、数百、千以上いて、
それらが、プレイヤーへの経路探索に全員がA*を使う
となると
これは流石に負荷が大きくなります。
そんな場合の解決手段の一つとしてあるのが、
フローフィールドアルゴリズム
です。
詳細は今回は書きませんが、
簡単に言うと、フローフィールドとは
「ゴールから逆算して全マスに矢印を書く」
手法です。
・まずゴール（プレイヤー位置）から全マスまでのコストマップを作ります。
これは実質Dijkstraから利用しているcostSoFarです。
次に、
・各マスに「一番数字の小さい隣」への移動指示を書きます。
これがフローフィールドです。
敵はこのフローフィールドの、自分のいる座標の指示を見て移動する。
と言うイメージです。
同じフローフィールドを全ての敵が利用するので、
プレイヤーの移動後にフローフィールドを更新するだけでよく、
敵が何体いても問題ありません。
まとめ
つまり、
BFSは、最小歩数で探す。
ダイクストラは、コストを見て探す。
Aは、コストに加えてゴールの方向も見て探す。
そして、フローフィールドは、多数のユニットが同じ目的地へ向かう時に強い。
ということになります。
どのアルゴリズムが常に最強というより、
「何をしたいのか」
「どれくらいの規模で使うのか」
「何体が同時に経路探索するのか」
によって、向き不向きが変わってくるわけですね。
今回のAbyssBounderのような、
ウィザードリィライクのダンジョンでの自動移動なら、
Aはかなり相性の良い選択肢ではないかと思っています。
