ダイクストラマップ
ゴールからマップ全体へ距離を塗り広げておき、どのエージェントも「数字が小さい方へ降りる」だけで移動できるグリッド経路探索の手法。エージェントごとの探索は要らない。
モンスターごとに A* を走らせる代わりに、ゴールのセル(複数でもよい)から幅優先探索かダイクストラ法で一度だけ距離を流し込み、全セルにゴールまでの距離を書き込む。あとは各エージェントが隣接セルを見て、最も小さい値のセルへ進むだけである。マップの符号を反転して再走査すれば、今度は最寄りの出口へ向かって逃げる挙動になる。
この手法はローグライク『Brogue』のBrian Walkerによって広まった。実質的にはグリッド上に事前計算されたフローフィールドであり、多数のエージェントが同じゴールを共有する場面で最も安上がりだ。一度の走査で群れ全体をまかなえる。個別の探索を高速化する近縁の手法には Jump Point Search がある。