This explanation is currently available in Japanese.
ひとことで
スタートから、累積コストが小さい順にノードを確定させていくことで、そこから全部の場所への最短距離を求める方法です。A* のように特定のゴールへ向かうのではなく、同心円のように全方向へ広がっていきます。そのぶん 1 か所への経路だけなら遅いのですが、「ここから行ける範囲」「全員が 1 つの目的地へ向かうときの道しるべ」のように、たくさんの場所の距離が一度に欲しいときに力を発揮します。
ゲームでの使いどころ
- タクティクスの移動範囲：移動力 7 で行けるマスを光らせる。地形ごとのコストに合わせて、範囲がゆがむ。
- フローフィールド（距離の場）：ゴールから逆向きにダイクストラ法を 1 回だけ行い、各マスの「ゴールまでの距離」を求める。RTS やタワーディフェンスで、何百体のユニットがそれぞれ距離が下がる方へ進むだけでゴールへ着く（流れ場の追従）。
- AI の評価：「どの場所が自分から近いか」「どの敵に一番早く着けるか」を一度に調べる（環境クエリの経路の長さのテスト）。
- 影響マップ：複数の敵の位置を始点にして距離を求め、危険度の地図を作る。
しくみ
- 始点の距離を 0、それ以外を無限大にし、始点を優先度付きキューに入れます。
- キューから距離が最小のノードを取り出し、確定させます。
- 隣のノードへの距離 が、今までの より小さければ更新してキューに入れます。
- キューが空になるまで（または距離が上限を超えるまで）くり返します。
辺のコストが負でない限り、取り出した時点のノードの距離は確定しています。取り出す順番が「距離の小さい順」なので、ある距離より近いノードはすべて先に確定しているからです。これは の A* と同じ動きです。
複数の始点：始点を複数入れておくと、「いちばん近い始点までの距離」が求まります。出口が 3 つある部屋で、各マスから最寄りの出口への道しるべを作る、といった使い方ができます。
実装のポイント
- 経路も一緒に残す：「どこから来たか」を記録しておけば、範囲内のどのマスへの経路もすぐ取り出せます。カーソルを乗せたマスまでの道を表示するのに使います。
- フローフィールドの向き：隣のマスの距離の差から、各マスに「進む向き」を前もって計算しておくと、ユニットは向きを読むだけで済みます。なめらかにしたいなら、距離の場を補間して勾配を取ります。
- 更新の頻度：ゴールが動かない限り、距離の場は作り直す必要がありません。ゴールが動く場合も、毎フレームではなく数フレームに 1 回にします。
- すべての辺のコストが同じなら：優先度付きキューの代わりに、ただのキュー（幅優先探索）で同じ結果が速く得られます。
つまずきやすい点
- 1 か所だけに行きたいのに使う：ゴールが 1 つなら、A* の方がずっと少ない手間で済みます。
- 負のコスト：「この道を通るとコストが減る」ような負の辺があると、確定したはずの距離が後から小さくなり、正しく求まりません。コストは 0 以上にします。
- フローフィールドの谷：距離の場を下るだけのユニットは、同じマスに集まって押し合います。ORCA などの回避と組み合わせます。
デモで試すこと
- 「移動範囲」では、キャラクターの周りに、累積コストが小さい順にセルが広がっていきます。林（2）や沼（4）では広がりが遅れ、範囲がゆがみます。
- 範囲内のセルにカーソルを乗せると、そこまでの最短経路とコストが表示されます。クリックすると、キャラクターがその経路で移動し、新しい位置から範囲を計算し直します。
- 「移動力」を変えて、範囲の形がどう変わるか確かめてください。
- 「距離の場で大勢を誘導」では、ゴールから 1 回だけ探索して、全体の距離を色で表します。140 体のユニットが、隣のより近いセルへ進むだけで、壁を回り込んでゴールへ集まります。クリックでゴールを動かせます。