【GDC2021】『DEATH STRANDING』のNPCがプレイヤーを追跡する仕組み

3Dビデオゲームの広大な世界をNPC（ノンプレイヤーキャラクター）が自由に動き回るには、ナビゲーションというゲームAIの仕組みが欠かせません。ナビゲーションはその名が示すとおり、ゲーム世界の地形（Terrain）データに基づいて、エージェントが目標地点まで移動するための最短ルートをリアルタイムで探索するためのシステムです。オープンワールドゲームのような広大かつ複雑な環境では、目的に応じたエージェントの現実的な動作とインタラクションを定義するために必要不可欠な存在です。

7月19日から7月24日までオンラインで開催された「Game Developers Conference」（GDC 2021）にて、コジマプロダクションのAIプログラマー、Eric Johnson氏による「’Death Stranding’: An AI Postmortem（DEATH STRANDINGにおけるAIの事後検証）」というセッションを取材しました。

このセッションでは、雄大な自然環境をオープンワールドで表現したアクションゲーム『DEATH STRANDING』に使われているナビゲーションシステムが紹介されました。同作は、プレイヤーが運び屋としてロープやハシゴを駆使しながら目標地点を目指したり、道路や橋を整備することで物流ルートを確保したりと、地形そのものと向き合う環境トラバーサルに重点を置いたゲーム性が特徴です。

過酷な地形の数々はプレイヤーだけでなく、NPCにとっても行動を著しく制限する高い障壁となります。それに対してNPCがいかに現実的な挙動でアプローチできるかが、ナビゲーションを構築する上での大きな課題です。たとえば、『DEATH STRANDING』に登場する「ミュール」というプレイヤーの追跡と荷物の強奪に特化した敵NPCは、プレイヤーが進入できるすべての地形にアクセス可能で、どんな地形でもプレイヤーの荷物を拾えるという条件を満たすようにデザインされています。

ナビゲーションメッシュをランク付けする仕組み

『DEATH STRANDING』のゲームワールドは、開発チームが2016年8月にアイスランドの溶岩地帯や河川、山の谷間、峡谷、クレバス、洞窟、間欠泉などを実際に調査した地形データをもとに構築されています。こうした地形をゲーム内で再現するにあたって、エージェントが進入および移動可能な領域を定義しているのが、ナビゲーションメッシュ（Navmesh）というデータ構造です。

一般的にナビゲーションメッシュは、ゲームマップを分割するタイル領域と地形オブジェクトの頂点を直線で結んだ2次元ポリゴンの集合として生成されます。これらポリゴンの接点をつなげたグラフが、エージェントの移動経路（以下、パス）として扱われます。その際、目的地（以下、ウェイポイント）までの最短ルートを探すパス検索には、グラフ理論におけるダイクストラ法や、その改良版であるA*探索アルゴリズムが使われています。

たとえナビゲーションメッシュが存在する進入可能な地形であっても、その種類や状態によって異なる移動コストを生じさせるのが一般的なゲームデザインです。『DEATH STRANDING』では、膝までの高さの岩であれば乗り越えられますが、走り抜けようとすると一定の確率でつまづいて転びます。また、河川や湖の水中に進入した際は、移動速度が著しく低下するばかりか、プレイヤーならスタミナゲージを消費します。

ここでプレイヤーは地形や路面状況がおよぼす影響を直感的に判断して最適なルートを決定できますが、エージェントが地形の特性をパス検索の考慮に入れるためには、それぞれの地形に応じてナビゲーションメッシュを改良する必要があります。

『DEATH STRANDING』に使われているデシマエンジンには「Procedural Placement System」（自動配置システム）というナビゲーションメッシュを自動生成する機能があり、すべてのナビゲーションメッシュに移動コストの情報を書き加えています。このプロセスを「Placement Painting」といいます。エージェントはレイキャスト（光線の反射からオブジェクト情報を取得する判定手段）によって、これらの情報を読み取ります。これにより、エージェントは可能な限り足場の悪い地形を避けながら最適なパスを検索できるようになります。

的確なタイミングでパス検索を実行するには

パス検索の計算コストは、ナビゲーションメッシュがきめ細かくなるほど増加していきます。そこで『DEATH STRANDING』では、エージェントを中心に展開したナビゲーションメッシュバブルの範囲内でのみパス検索を実行し、さらに1度のパス検索で検出するノード数（ナビゲーションメッシュポリゴンの数）を500個に制限しているということです。エージェントが移動するたびにナビゲーションメッシュバブル内の情報は更新され、新たなナビゲーションメッシュが生成されるという仕組みです。

このためエージェントは、最終的なウェイポイントに到達するまでパスの再検索を繰り返す必要があります。問題は再検索のタイミングをどうやって判断するかです。一定間隔で常にパス検索を実行すると計算コストが膨れ上がってしまうだけでなく、エージェントの移動中にそれまでとはまったく異なる検索結果が出た際に、極めて不自然な挙動に陥ってしまう可能性もあります。パス検索における最短ルートは開始地点に大きく依存しているからです。そのため、パス検索の再試行は必要最低限の回数に留めることが重要になってきます。

『DEATH STRANDING』のNPCがパス検索を再試行するのは、外的要因や自らの慣性によりNPCが移動中のパスからはみ出した場合、外的要因によりウェイポイントが当初のナビゲーションメッシュポリゴンの外へ移動した場合、オブジェクトの追加や除去によってナビゲーションメッシュが書き換えられてパスを構成するポリゴンの一部が無効になった場合、パス検索で検出するノード数の制限範囲に到達した場合などに限定されています。エージェントはパスの情報を保持したまま再検索の条件を継続的に判定しています。これを「Event-Based Repathing」（イベントに基づいたパス検索）といいます。

挙動不審なNPCや迷子のNPCを出さないために

前述した「Placement Painting」によってナビゲーションメッシュごとの移動コストを定義したからこそ起こりうる問題もあります。NPCが高コストの地形に進入した際、突如として直進を諦めて来た道を戻るという奇妙な挙動を見せる場合があります。これはエージェントが高コストの地形に入った瞬間にパス検索を再試行した時に起こりえます。高コストの地形を避けつつ、やむを得ず進入した場合も最短ルートを維持するためには、移動コストに加えて地形に応じた進入コストの概念を導入する必要があるということです。

たとえば、岩場における移動コストを平地と同等に設定する一方で、進入コストは遥かに高く設定します。こうすることでNPCは岩場の外側からは高コストの地形と認識して可能な限り最短ルートから除外しますが、ほかに選択肢がなく仕方なく岩場の内側に進入した場合は、岩場を平地と同じ移動コストのナビゲーションメッシュとして扱ってくれるというわけです。

パス検索範囲内の大部分が進入不可の地形や障害物に阻まれているようなケースでは、ウェイポイントへ向かう最短ルートの再検索が無限ループに陥るような問題も起こりえます。NPCが障壁に近づくにつれて更新されるナビゲーションメッシュバブルには、障壁の向こう側のナビゲーションメッシュもふくまれるからです。もしNPCが再検索により迂回ルートへ移動した際に、再び障壁の向こう側がふくまれていないナビゲーションメッシュバブルへ更新されてしまうと、NPCは最短ルートとして障壁側へ逆戻りしてしまうというわけです。あとは延々と同じことの繰り返しです。

こうした挙動は、広く深い岩の裂け目が大地を分断しているような地形で、裂け目の内部や反対側にいるプレイヤーを追跡するNPCにとって死活問題となり得ます。たとえ迂回ルートを見つけ出してNPCが上手く裂け目内へ入れたとしても、内部のナビゲーションメッシュがバブル範囲内に完全に収まってしまうような狭い空間だった場合、ナビゲーションメッシュバブルを更新できなくなったNPCは永久に閉じ込められてしまうでしょう。結果、プレイヤーの追跡中に迷子になって本拠地へ帰還できなくなるNPCが続出します。

この問題を解決するために、デシマエンジンには「AIロードネットワーク」という機能が搭載されています。これは文字通り、広大なマップにあらかじめ移動ルートの指標となるネットワークをパス検索のレイヤーとして用意しておくことで、ナビゲーションメッシュバブルの範囲より遥か遠くの座標を目指すNPCが、わざわざ道なき道を進まなくてもいいようにするという仕組みです。複数のエリアをつなぐ見えない幹線道路と考えれば分かりやすいでしょう。どんなに遠くへ赴く際も、とりあえず幹線道路にさえ沿って移動すれば、無限ループというAIの煉獄に囚われることはないというわけです。

動的地形におけるナビゲーションメッシュ

『DEATH STRANDING』では、「キャッチャー」と呼ばれるプレイヤーの捕食を目的とした敵が出現した際に、建物や車両、コンクリート塊がタール状の地面から湧き出る「座礁」（Stranding）という同作の世界観特有の現象が起きます。この時、周辺のナビゲーションメッシュも座礁オブジェクトをふくめた状態へ自動的に書き換えられ、プレイヤーのみならず「キャッチャー」もオブジェクト上へ進入できるようになります。戦闘中に座礁オブジェクトが再び地面へ沈んだ際も同様です。

こうした動的ナビゲーションメッシュ（Dynamic Navmesh）の仕組みは、フェンスやバリケードといった破壊可能なオブジェクトに加えて、プレイヤーがフィールドに設置できるアイテムにも適用されています。たとえば、同作のハシゴはプレイヤーがあらゆる地形に任意の角度で設置できるようにデザインされています。この時、ハシゴを45度以上の角度で設置した場合は両手両足を使って登降する通常のハシゴとして、45度未満で設置した際は手放しで渡れる橋として機能するような仕様で実装されています。

プレイヤーが設置したハシゴをNPCも利用できるようにするためには、ハシゴの設置状態や接地面の地形に応じたナビゲーションメッシュとジャンプリンクを適宜生成する必要があります。ジャンプリンクとは、高低差によって直接隣接していないナビゲーションメッシュ同士を接続する仕組みです。ハシゴを橋として利用する場合は、ハシゴへ足を踏み入れるエントリーポイントと、ハシゴから飛び降りるジャンプポイントの候補が必然的に多くなるため、ナビゲーションメッシュの生成プロセスも複雑になります。

同作では、ハシゴ上に50センチメートル間隔でサンプルポイントを定義し、それぞれのポイントに隣接した進入あるいは脱出可能なナビゲーションメッシュを検出しているということでした。この時、接続先のナビゲーションメッシュが重複しているサンプルポイントは、ひとつのグループとして扱っています。グループ内のポイントごとにコリジョン判定を行い、接続先のナビゲーションメッシュが無効だった場合は候補から除外します。こうすることで進入可能なナビゲーションメッシュが存在する地形でのみ、ハシゴへ登ったりハシゴから降りたりできるようになるというわけです。

ちなみに、これら座礁オブジェクトとハシゴにおけるジャンプリンクは「Procedural Placement System」によって自動生成されていますが、2000箇所におよぶその他のジャンプリンクはすべて手動で設置したとのこと。しかし、ジャンプリンクは地形やアニメーションに変更が加えられるたびに調整が必要になるので、これらを自動生成できるシステムの構築が今後の課題だということでした。また、パス検索にA*探索アルゴリズムの代わりに双方向探索を採用する計画もあったとのことですが、ジャンプリンクによる一方通行箇所や進入コストの導入がボトルネックとなり、結果的に見送ったということです。

Writer：Ritsuko Kawai / 河合律子