NavMesh・A*・フローフィールドで200体のAIエージェントを詰まらせない経路探索
200体のエージェントが押し寄せる攻城シーンで経路探索が詰まる理由、NavMeshが黙って嘘をつく場所、そしてA*とフローフィールドを使い分ける境界線がどこにあるのかを、プロファイラの実測値だけを頼りに順を追って整理します。ボトルネックは探索そのものではなく、毎フレームの処理の側にありました。
一つの門の前で止まった200体のエージェント
昨年の暮れ、攻城シーンの作業をしていた。城門は一つ、そこへ向かって走るNavMeshAgentが200体。ゲームAIのナビゲーションは、まさにこの手のシーンで破綻する。QAがナイトリービルドに添付してきた録画は、いつも同じ場所で止まっていた。門の手前十五メートル、六十体ほどが互いに擦れ合って震え、何体かは後ろ向きに歩いている。最初の十秒で門の奥の中庭に入れたのは、四十体ほどだった。
フレーム時間はエージェントが遠くにいる間は11 msで、門に近づくにつれて26 msまで上がった。最初はA*が爆発したのだろうと考えた。プロファイラの答えは違った。NavMesh.CalculatePathの合計は3.2 ms、一方でNavMeshAgent自身の内部更新が9.8 msを占めていた。つまりボトルネックは探索ではなく、各エージェントが毎フレーム行う処理の中にあった。
別々の問題が同時に表面化し、一つのものとして扱われていた。グローバルな経路を計算するコストと、エージェント同士の相対的な振る舞いである。この二つを同じ見出しの下にまとめた議論は必ず行き詰まる。直すべき場所がまったく異なるからだ。分離しない限り、どのつまみがどの数字を動かしたのかは永久に分からない。我々の場合、切り分けは一つの習慣から始まった。プロファイラ上で探索の行とエージェント更新の行を別々に追うことだ。
A*のコストと階層型経路探索
A*経路探索のコストは、展開するノード数に比例して膨らむ。41,000ポリゴンのNavMeshでは、マップの端から端までの一回のリクエストに0.35 msかかっていた。200体が同じフレームで要求すれば70 msになる計算だが、そんなカクつきが見えることはない。Unityはリクエストをキューに積み、経路は三、四フレーム遅れて届き、その間エージェントは古い進行方向のまま走り続ける。症状は停止ではなく、曲がるのが遅れることとして現れる。
階層型経路探索はこのコストを二重に削る。マップを領域に分割し、その間の遷移をポータルグラフとして書き出す。探索はまず30〜40ノードの粗いグラフ上で走り(0.02 ms)、次のポータルまでの範囲にだけ詳細なA*を走らせる。平均リクエストは0.35 msから0.06 msに下がり、エージェントの完全な経路を一度に計算することは二度となくなった。粗いグラフはベイク時に一度だけ構築され、実行時には動的な障害物がポータルを塞いだときだけ更新される。
試して捨てた代替案は、共有の経路キャッシュだった。目的地を4 mのセルに丸め、同じセルへ向かうエージェント全員に一本の経路を渡す。静止した目標に対するヒット率は70%だったが、プレイヤーを追跡している間は18%まで落ち、無効化のロジックがキャッシュの節約分以上を食い潰した。コードは削除した。経路の共有が割に合うのは、目的地が数十フレームにわたって動かない場合だけだ。
群衆全体を一枚のフローフィールドで動かす
200体が同じ目的地を共有しているなら、200回の探索を別々に走らせる意味はない。フローフィールドはゴールから後ろ向きにコストの伝播を一度だけ走らせ、各セルに最も安い隣接セルを指す方向ベクトルを書き込む。我々のものは128x128のグリッドでセルは0.5 m、完全な再構築に4.1 msかかった。伝播は一度の走査ですべてのセルを埋めるので、コストはエージェントの数と完全に無関係になる。
重要なのは、この4.1 msを毎フレームではなく、ゴールのセルが変わったときにだけ支払う点だ。プレイヤーが走っている間はそれが毎秒三、四回起きたので、およそ毎秒14 msということになる。一方でエージェント一体あたりのコストはバイリニア補間二回にまで縮む。0.004 ms、200体でも合計0.8 msだ。同じ群衆が階層型A*では12 msかかっていた。
限界ははっきりしている。目的地が別々になれば、そのぶんフィールドも増える。ゴールが三つ四つを超えると、メモリと再構築のコストがA*を追い越す。だから我々はハイブリッドのままにした。名前付きのNPCとボス級のエージェントはA*、群衆シミュレーションはフローフィールドで動く。どちらも同じNavMeshの三角形の上に立っていて、違うのは進行方向の供給元だけだ。この切り替えはコード上ではbool一つで、デザイナーがprefab側で反転できる。
local avoidanceはグローバルなナビゲーションではない
RVOと、そこから派生したORCAがやっているのは一つのことだ。各エージェントが近傍の位置と速度を読み、衝突につながる速度を半平面で切り落とし、残った集合の中から希望速度に最も近いものを選ぶ。その視野は一、二秒ぶんしかなく、レベルの形状については何も知らない。これは進行方向の補正であって、ナビゲーションではない。エージェントをこれだけに任せれば、RVOがゴールまで連れて行くことは決してない。
だからlocal avoidanceにグローバルな解決を期待するのは、初めから間違っている。U字型の中庭の壁に対しては、RVOはエージェントを壁に貼り付け、正面から出会った二体はデッドロックする。obstacleAvoidanceTypeをHighQualityにしても直らない。200体で9.8 msのうち6.2 msを食うだけだ。Goodまで落とすと3.9 msになり、カメラ距離では違いが見えなかった。
本当に効いたのはavoidancePriorityというフィールドだった。全エージェントが既定値の50のままだと状況は対称のままで、誰も道を譲らない。スポーン時に0から99の乱数で優先度を配ったところ、門前の詰まりは4.2秒から1.1秒に縮んだ。一行の変更だった。
動的障害物とpath requestの予算
動的な障害物にはNavMeshObstacleとcarvingを使うが、carvingは移動のたびにタイルをベイクし直す。転がる樽が12個あるシーンでは、5.8 msのスパイクが規則的に出ていた。carvingMoveThresholdを0.5 mまで上げ、carveOnlyStationaryを有効にしたところ、同じシーンが0.9 msまで下がった。動き続けるものを障害物にしてはいけない。それはlocal avoidanceの担当だ。
予算の話は単純で、1フレームあたりに許す完全な経路リクエストの本数を固定する。我々の場合は12本。エージェントは0.45秒の間隔に0から0.15秒の乱数を足したタイミングで要求する。このジッタがないと、スポーンの波がすべてのリクエストを同じフレームに落としてしまうからだ。予算が埋まってもリクエストは破棄されず次のフレームへ滑るだけで、その間エージェントは既存の経路を歩き続けるので誰も気づかない。この予算は必ず実機で測ること。コンソールで12だった値が、デスクトップでは余裕で30になる。
このシーンでは合計フレーム時間が26 msから13.4 msへ、経路探索の取り分が13 msから2.1 msへ下がった。その中で最も安上がりだったのは、一行の優先度の変更である。作業はこの順で並べるとよい。まず自分の目でNavMeshの形状を確認し、次にフレームあたりのリクエスト予算を敷き、それから群衆をフローフィールドに移し、local avoidanceの設定には最後に触れる。逆から行けば、0.6 mの出入口がそのまま残っているのに何時間もORCAのパラメータに溶ける。測っていない設定は変えないこと。ここに並べた数字はすべてプロファイラから出てきたもので、推測から来たものは一つもない。