Dijkstra’s （ダイクストラ） アルゴリズム
代表的な迷路探索アルゴリズムには、
・BFS
・Dijkstra's Algorithm
・A*（A-star）
があります。
BFSについては前回噛み砕いた通り、
・ゴールへの近さ
・危険地帯
・通路コスト
といった要素を一切考慮しない総当たり探索です。
ただし、結果として得られる経路は「最小歩数」で到達できるルートになります。
BFSではできない事
例えば、
・近道でもダークゾーンは避けたい
・多少遠回りでも安全な道を選びたい
・発見済みの罠を避けたい
といった判断をさせたい場合。
BFSではそれができません。
そこで登場するのが、
Dijkstra's Algorithm
です。
ダイクストラの基本概念
考え方は単純です。
各マスに通過コストを設定し、
「何歩進んだか」
ではなく、
「スタート地点からの合計コスト」
で経路を評価します。
例えば、
通常通路：1
ダークゾーン：10
罠：50
と設定すれば、
歩数が多少増えても安全な道を優先して選ぶようになります。
基本構造はBFSと同じ
前回説明した、
・これから調べる座標のリスト
・どこから来たかの記録
・調査済み座標の記録
という3つの考え方は、ダイクストラでもそのまま使います。
ですが、「コスト」が加わることで、
・調査済み座標の記録
の考え方を変え、
・これから調べる座標のリスト
にも修正を加える必要があります。
visitedの意味が変わる
まず、
・調査済み座標の記録
BFSのvisitedは、
「その座標を調査したか」
を記録するものでした。
一方ダイクストラでは、
「その座標までの最小コストが確定したか」
を記録するものになります。
このため、Visitedに座標を登録するタイミングがBFSとは異なります。
この違いが非常に重要です。
まずは全体像
まずはサンプルコード全体を見てみます。
public class PathNode { public Vector2Int pos; public int cost; public PathNode(Vector2Int pos, int cost) { this.pos = pos; this.cost = cost; } } public List<Vector2Int> FindPathDijkstra( 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) { // queueの中から最小コストを探す 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; queue.Add( new PathNode(next, newCost) ); } } visited[current.x, current.y] = true; } // 経路なし return null; }
今回のサンプルダンジョン
スタート地点は(x3,y5)、ゴール地点は(x10,y10)です。
BFSの時の0と1のサンプルダンジョンとは異なり、
ダイクストラにはコストの概念があります。
今回のサンプルでは、
・99：通行不可
・1：通常通路
・10：ダークゾーン
・50：罠
と言う設定です。
かなり意図的に経路を絞っているダンジョンですね。
『これから調べる座標のリスト』を改造する。
まず、『これから調べる座標のリスト』であるqueueにコストを追加できるようにします。
C#には二つの項目が使える
PriorityQueue<TElement, TPriority>
が用意されています。
unityでこのPriorityQueueを使う場合は、
・unity6以上
・Unity 2022 LTSでApi Compatibility Levelを .NET Frameworkに切り替える
のどちらかで使用可能になります。
ただし、今回はダイクストラの理解のため
PriorityQueueを使わず、あえて馴染み深い普通のListでやってみようと思います。
そのため、まず専用classを定義します。
public class PathNode { public Vector2Int pos;//座標格納用 public int cost;//コスト格納用 public PathNode(Vector2Int pos, int cost) { this.pos = pos; this.cost = cost; } }
そして、queueの設定をこのように変えます。
List<PathNode> queue = new List<PathNode>(); bool[,] visited = new bool[width, height]; Dictionary<Vector2Int, Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>();
コスト記録用の配列を追加する
ダイクストラでは、
・各座標へ到達するための最小コスト
を記録する必要があります。
そのため、
int[,] costSoFar
を追加し、
初期値として理論上最大の値である
int.MaxValue
を入れておきます。
ここまでで、
「あれ？コスト格納用にPathNodeのListでqueueを作ったんじゃないの？」
と思うかもしれません。
queueのコストとcostSoFarの違い
ここは少し混乱しやすいポイントです。
どちらもコストを持っていますが役割が違います。
queue：これから調べる候補
costSoFar：その座標まで到達する最良コストの保存場所
という位置付けになります。
queueは取り出すと消えてしまいます。
そのため、
現在判明している最良コストは
costSoFar
に保存しておく必要があるのです。
探索開始
まずスタート地点を登録します。
スタート地点はコスト0で、それ以下にはなり得ませんから、costSoFarにも登録します。
queue.Add(new PathNode(start, 0)); costSoFar[start.x, start.y] = 0;
BFSではここでvisited登録しましたが、
ダイクストラではまだ登録しません。
「最小コストが確定した」
という時に登録になります
スタート地点に限っていえば、ダイクストラでも今の時点でvisited登録可能です。
ただ、Whileループ内で四方を確認してからvisitedを登録するので、あえてこの段階で登録する必要がないのです。
最小コストを座標を取り出す
BFSと同じくqueueから探索対象の座標を持ってきます。
BFSはqueueに登録した順番に取り出します。
しかしダイクストラでは
・queueの中で最もコストが低い座標
を取り出します。
（同じコストの場合は、先に登録された順）
// queueの中から最小コストを探す 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;
これがダイクストラの最大の特徴です。
無効座標を除外する
BFSの時と同じく、
取り出した座標から四方向に伸ばした隣接座標について
・範囲外？
・通行不能？
・探索済み？
を判定して除外します。
BFSはこれで有効座標と判定してqueueに登録、次の座標へ、、、とWhileループを回していきましたが、
ダイクストラはここからコストの評価に入ります。
合計コストを計算する
まず、
次のマスへ移動するコストを取得します。
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;
で情報を更新し、
queue.Add(new PathNode(next, newCost))
queueにも登録します。
つまり、
調査対象の経路の合計コストが、
記録済みの経路より良くなければ、queueに登録せず、調査対象にもしないという事です。
ここで初めてvisited登録
四方向の確認が終わったら、
visited[current.x, current.y] = true;
を実行します。
これで、現在地までの最小コストが確定しました。
あとは再び、
・queueの中で最もコストが低い座標
を取り出していき、
・queueが空になるか
・ゴールに到達するか
まで探索を続けていきます。
経路復元はBFSと同じ
ゴール到達後は、BFSと同じように、cameFromを逆に辿るだけです。
「あれ？コストを使って復元しないの？」
と思うかもしれません。
しかし、
cameFrom自体が常に最良経路へ更新され続けているため、
最終的に逆順で辿ればそれが最良ルートになります。
実際の動き
では、実際の経路探索の流れを追ってみましょう。
スタート地点に対しての四方の探索が終わった時点で、各記録はこうなっています。
この時点では、まだどこに向かっても同じコストです。
queueに登録されているコストが全て同じの場合、
次に取り出される座標は、先に登録されている座標になりますので
この場合、(x3,y6)になります。
そして(x3,y6)の調査を終えると、こうなります。
ここで上方向に向かっていた経路は
・罠（コスト50）
・ダークゾーン（コスト10）
にぶつかりました。
costSoFarには初期設定で
int.MaxValue
が登録されているため、
罠（コスト50）であってもcostSoFarは更新され、
queueにも登録されます。
しかし、queueからは
・queueの中で最もコストが低い座標
が取り出されていくため、
この経路についての探索の順番はしばらく巡ってこないことになります。
そうやって探索が続き、
(x6,y3)の調査が終わった時点でこのようになっています。
次は(x5,y2)を中心に四方を探索しますが、
（x4,y2) は既にVisitedに登録されていて対象外なので、探索できるのは（x6,y2)のみです。
ところが、
この段階でcostSoFarの（x6,y2)には既に合計コスト6が登録されています。
これは事前に（x6,y3)経由で到達した結果ですが、
（x6,y2)には（x6,y3)経由でも(x5,y2)経由でもコスト6で到達できてしまいます。
この場合、より安いコストに更新されないのであれば、
先に到達した経路が優先されます。
つまり、（x6,y2)への経路は（x6,y3)経由で確定します。
そうやって探索が続いていき、やがてゴールに到達した時、各記録はこんな感じになっているはずです。
ダイクストラの強みと弱み
ダイクストラは、
・ダークゾーンを避ける
・発見済みの罠を避ける
・危険地帯を避ける
といった判断が可能です。
そういう意味では、BFSより賢い探索ができます。
ただし、
ダイクストラも本質的には総当たり探索です。
そのため、
ゴールした時の探索範囲の赤いエリアの様に、
ゴールとは真逆の方向
まで探索してしまいます。
次回はA*へ
ウィザードリィライク程度の広さのダンジョンで、
オート移動用に使うのであれば
・危険地帯を避ける。（罠やダークゾーンを避ける。）
という判断が可能なダイクストラは十分実用的です。
しかし、
・広大なマップ
・リアルタイムで動く敵
などでは無駄な探索による負荷が気になってきます。
そこで次回は、コストの概念に更に
「ゴールの位置を意識する」
という考え方を追加した、
A*（A-star）
について、噛み砕いてみようと思います。
