経路探索とナビゲーションメッシュ

経路探索は「グラフ探索」と「空間表現」の二層問題

横にスクロール

ゲームのナビゲーションは、突き詰めると2つの独立した問いに分かれます。1つは「どの空間表現の上を探索するか」（グリッド、ウェイポイント、ナビメッシュ）、もう1つは「そのグラフ上でどう最短経路を見つけるか」（ダイクストラ、A*、フロー場）です。この二層を混同すると、A*のヒューリスティックを工夫しても碁盤目状の不自然な経路しか出ない、あるいはナビメッシュを整えても探索が遅い、といった問題の切り分けができません。本稿は上の層（探索アルゴリズム）と下の層（空間表現）を順に解き、多数エージェントと動的障害物という実務の壁まで扱います。基礎となるグラフ探索の理論はアルゴリズムとデータ構造の領域と地続きです。

A*：許容的ヒューリスティックが最適性を保証する

Aは、始点からの実コスト g(n) と、そのノードからゴールまでの推定コスト h(n)（ヒューリスティック）を足した評価値 f(n) = g(n) + h(n) が最小のノードから展開する最良優先探索です。優先度付きキュー（オープンリスト）に未展開ノードを f 値で並べ、取り出しては隣接ノードの g を更新していきます。h を常に 0 にすればダイクストラ法に一致し、g を無視すれば貪欲最良優先探索になります。Aはこの両者の中間で、実コストと推定を釣り合わせることで探索範囲を賢く絞ります。

代表的なヒューリスティックは、障害物を無視した幾何距離です。斜め移動を許さない4方向グリッドではマンハッタン距離、8方向グリッドではチェビシェフ距離（またはオクタイル距離）、連続空間ではユークリッド距離を使います。重要なのは、これらが真の最短距離を上回らないよう移動モデルと整合させることです。斜め移動できないのにユークリッド距離を使うと過大評価が起き、許容性が壊れて最短でない経路を返すことがあります。逆に h を意図的に小さくすると安全側（必ず最適）ですが探索が広がり遅くなる——h の精度が探索の速さと最適性のトレードオフを直接支配します。

ナビゲーションメッシュ：なぜグリッドを捨てるのか

グリッドは実装が容易ですが、セル数が面積に比例して爆発し、経路は8方向に量子化されて不自然に折れ曲がります。実務の標準はナビゲーションメッシュ（ナビメッシュ）、すなわち歩行可能な床面を少数の凸ポリゴンで覆った表現です。凸ポリゴンの内部は直線移動が常に可能なので、1枚のポリゴンが広い領域を1ノードで表せ、探索対象のグラフが劇的に小さくなります。エージェントはポリゴンの隣接関係（どのポリゴンとどの辺を共有するか）が作るグラフ上でA*を走らせ、ポリゴン列を得ます。

ナビメッシュは階段・スロープ・段差を高さ情報つきで表せ、さらにジャンプや梯子といった非連続な移動をオフメッシュ接続（off-mesh link）として明示的に張れます。これにより「崖を飛び降りる」「柵を乗り越える」がグラフの辺として探索に組み込まれます。

経路平滑化：ポリゴン列から滑らかな軌道へ

A*がナビメッシュ上で返すのは「通過すべきポリゴンの列」であって、最終的な移動経路そのものではありません。素朴にポリゴンの重心や辺の中点を繋ぐと、壁沿いをジグザグ歩くギクシャクした経路になります。これを凸ポリゴン列の内部で許される最短の折れ線に直すのがFunnel（漏斗）アルゴリズムです。共有辺の両端（左ポータルと右ポータル）を追いながら、左右の視線がなす「漏斗」を保持し、視線が交差した瞬間にその頂点を経路の角（コーナー）として確定して漏斗を畳み直します。線形時間で、凸ポリゴン列の中を通る厳密な最短折れ線が求まります。

Funnel（Simple Stupid Funnel）の骨子:

  apex（現在の頂点）と、left / right ポータル頂点を保持
  各ポータルの左右端を順に処理:
    右端を右辺へ狭める向きなら更新、
      左辺を跨いで交差したら → 左頂点を角として確定し
      apex をそこへ移し、漏斗を再初期化
    左端も対称に処理
  → 出力は凸領域内を通る最短の折れ線（コーナー列）

得られた折れ線はまだ角ばっているため、実際のエージェントには曲率制約に応じた仕上げをかけます。角を円弧で丸める、ベジェ／スプラインで補間する、あるいは操舵挙動（steering）で経路に追従させる、といった処理です。ここは移動体の運動学次第で、車両なら最小回転半径、人型なら加減速の自然さを考慮します。

多数エージェント：フロー場で探索を共有する

数百体が同じ目的地（防衛拠点、集合地点）を目指すRTSやタワーディフェンスで、全員が個別にA*を回すのは無駄です。目的地が共通なら、ゴールから逆にダイクストラを1回だけ走らせて各セルの「ゴールまでの距離（積分場）」を作り、その勾配から各セルの進行方向ベクトルを求める——これがフロー場（flow field／ベクトル場）です。各エージェントは自分の位置のセルのベクトルを読むだけで進めるので、1体あたりの経路探索コストがほぼゼロになります。目的地が変わらない限りフロー場は再利用でき、群れが密集しても方向がセル単位で共有されるため自然に隊列が流れます。

階層型経路探索（HPA*）も大規模マップの常套手段です。マップをクラスタに分割し、クラスタ境界のポータル間で粗い経路を先に求め、必要なぶんだけクラスタ内を詳細に解く。粗密二段で、遠距離の探索ノード数を桁で削減します。

動的障害物：グラフの再計算か、局所回避か

静的なナビメッシュは実行時に動く障害物（他エージェント、開閉する扉、破壊された壁）を表せません。対応は大きく2系統です。第1はグラフの動的更新。恒久的な地形変化（橋の崩落、扉の施錠）はナビメッシュに穴を開ける／辺を無効化し、影響を受けた経路だけ再探索します。全面再探索を避けるため、変化した部分だけ差分再計算する D Lite* のような増分探索アルゴリズムが使われます。

第2は局所回避（local avoidance）。他エージェントのように高頻度で動く相手をいちいちグラフへ反映するのは非現実的なので、大域経路はナビメッシュのA*で決めつつ、直近の衝突回避は別レイヤーで処理します。RVO（相互速度障害）／ORCAは、互いに回避することを前提に「今後一定時間で衝突する速度の集合」を各相手について計算し、それらを避ける速度の中から目標方向に最も近いものを線形計画で選びます。これにより、正面から来る相手とすれ違う際に両者が同じ側へ避けて詰まる振動を防げます。

まとめ

ゲームの経路探索は、空間表現の層と探索アルゴリズムの層を分けて設計します。Aは f = g + h の最良優先探索で、h が真の最短距離を過大評価しなければ（許容的）最適解を、三角不等式を満たせば（無矛盾）再展開なしの最適解を保証します。ヒューリスティックは移動モデル（4方向ならマンハッタン、8方向ならオクタイル、連続空間ならユークリッド）と整合させることが最適性の前提です。実務ではグリッドではなく、歩行可能面を凸ポリゴンで覆うナビゲーションメッシュを使い、ボクセル化から領域分割・ポリゴン化に至るRecast方式で自動生成し、Aが返すポリゴン列をFunnel法で最短折れ線へ平滑化してからスプラインや操舵で仕上げます。多数のエージェントが共通目的地を目指すならフロー場でダイクストラ1回を全員が共有し、HPAで遠距離を粗密二段に圧縮します。動的障害物は、地形の恒久変化のみD Liteでグラフに反映し、動くエージェント同士はRVO/ORCAの局所回避で吸収する——この大域と局所の階層分担こそが、詰まらず破綻しないナビゲーションの設計原理です。空間分割の考え方は3DグラフィックスのBVHなど加速構造、探索の起源はAI・機械学習の状態空間探索とも通じます。