モリカトロン株式会社運営「エンターテインメント×AI」の最新情報をお届けするサイトです。

TAG LIST
ディープラーニング機械学習CGCGへの扉安藤幸央GANニューラルネットワーク月刊エンタメAIニュース強化学習三宅陽一郎モリカトロンAIラボインタビュー敵対的生成ネットワーク音楽OpenAIQAスクウェア・エニックスシナリオNVIDIAデバッグCEDEC2019河合律子プロシージャルDeepMind人工知能学会FacebookキャラクターAIルールベースビヘイビア・ツリーGoogleCEDEC2020ゲームAI映画SIGGRAPH遺伝的アルゴリズム不完全情報ゲームメタAIナビゲーションAI畳み込みニューラルネットワーク深層学習マイクロソフトAIと倫理グーグルGDC 2021GDC 2019マルチエージェントVR森川幸人ボードゲーム自然言語処理ロボットStyleGAN自動生成GPT-3CNNVFXモリカトロンゲームプレイAIファッションHTN階層型タスクネットワークJSAI2020Microsoftイベントレポート水野勇太アニメーションガイスターNPCCLIPアートtoio吉本幸記JSAI2021スポーツディープフェイク汎用人工知能TensorFlowGDC SummerテストプレイeSportsBLUE PROTOCOL小説DALL-EStyleGAN2AlphaZeroカメラ環世界中島秀之懐ゲーから辿るゲームAI技術史研究DARPAドローンAI美空ひばり手塚治虫メタデータ通しプレイOpenAI Five本間翔太CM倫理ピクサーAdobe作曲中嶋謙互Amadeus CodeMicrosoft Azureキャリアeスポーツ音声認識PyTorchDQN眞鍋和子バンダイナムコスタジオシーマンUnity齊藤陽介マインクラフトお知らせAIアートサルでもわかる人工知能VAEUbisoftUbisoft La ForgeワークショップGenvid Technologies知識表現ウォッチドッグス レギオンIGDAどうぶつしょうぎジェイ・コウガミ音楽ストリーミングマシンラーニングクラウドコンピューティショナル・フォトグラフィーGPT-2完全情報ゲーム坂本洋典釜屋憲彦ウェイポイントパス検索藤澤仁生物学画像認識NFT長谷洋平鴫原盛之masumi toyota宮路洋一SIGGRAPH ASIAソニーCycleGANフェイクニュースシムピープルGPUALife人工生命オルタナティヴ・マシンサウンドスケープASBSマンガぱいどんTEZUKA2020ナビゲーションメッシュ松井俊浩スパーシャルAIElectronic ArtsマーケティングApex LegendsNinjaゲームTENTUPLAYMARVEL Future Fightタイムラプスバスキアブロックチェーン階層型強化学習WANN竹内将馬淵浩希岡島学映像セリア・ホデントUX認知科学ゲームデザインLUMINOUS ENGINELuminous Productionsパターン・ランゲージちょまどビッグデータアストロノーカ模倣学習ナラティブFPSマルコフ決定過程スタンフォード大学パラメータ設計テニスバランス調整レコメンドシステム対話型エージェント協調フィルタリング人狼知能Amazon軍事AlphaDogfight TrialsエージェントシミュレーションStarCraft IIFuture of Life InstituteIntelロボティクスLAIKARotomationドラゴンクエストライバルズ不確定ゲームDota 2モンテカルロ木探索ソーシャルゲームEmbeddingGTC2020NVIDIA MAXINE淡路滋ビデオ会議グリムノーツゴティエ・ボエダGautier Boeda階層的クラスタリングaiboJuliusSIETPRGバーチャル・ヒューマン・エージェントtoio SDK for Unityクーガー田中章愛石井敦銭起揚茂谷保伯MinecraftGDMC成沢理恵MITメディアラボ著作権マジック・リープMagic Leap OneMagendaノンファンジブルトークンDDSPサッカー里井大輝KaggleバスケットボールAssassin’s Creed OriginsSea of ThievesGEMS COMPANYmonoAI technologyアバター初音ミクOculus転移学習テストBaldur's Gate 3Candy Crush SagaSIGGRAPH ASIA 2020デバッギングBigGANMaterialGANリップシンキングRNNReBeL自動運転車VolvoRival Prakユービーアイソフト北尾まどかHALO将棋メタルギアソリッドVFSMナップサック問題汎用言語モデルSpotifyMITReplica StudioamuseChitrakar巡回セールスマン問題ジョルダン曲線5GMuZeroクラウドゲーミングRival Peak和田洋一リアリティ番組Stadiaジョンソン裕子MILEs対話エンジンインタラクティブ・ストリーミング斎藤由多加インタラクティブ・メディアリトル・コンピュータ・ピープルシーマン人工知能研究所Ludoゴブレット・ゴブラーズTransformerSIGGRAPH 2019ArtEmis絵画ARGROVERFAIRAIりんなチート検出オンラインカジノアップルRealFlowiPhoneシミュレーションDeep FluidsMeInGameAIGraphブレイン・コンピュータ・インタフェースBCILearning from Video予期知能ユクスキュルカント哲学ドラゴンクエストエージェントアーキテクチャPAIROCTOPATH TRAVELER西木康智OCTOPATH TRAVELER 大陸の覇者アルスエレクトロニカ2019StyleCLIPDeNAStyleRig逆転オセロニア奥村エルネスト純いただきストリート齋藤精一大森田不可止高橋智隆ロボユニザナック泉幸典仁井谷正充ロボコレ2019ぎゅわんぶらあ自己中心派Azure Machine Learning意思決定モデル脱出ゲームHybrid Reward ArchitectureウロチョロスSuper Phoenix理化学研究所Project Malmo教育TextWorldProject PaidiaProject LookoutWatch ForBingLEFT ALIVE長谷川誠ジミ・ヘンドリックスBaby Xカート・コバーンロバート・ダウニー・Jr.エイミー・ワインハウスMagentaYouTubeダフト・パンクSFGlenn MarshallThe Age of A.I.Story2HallucinationレコメンデーションJukeboxGTC2021テンセントSIFTDCGANMOBADANNCE人事ハーバード大学研修デューク大学mynet.aiローグライクゲームNetHack人工音声NeurIPS 2021はこだて未来大学プレイ動画ヒップホップサイレント映画NBA環境音現代アートエージェント粒子群最適化法進化差分法群知能下川大樹ウィル・ライト高津芳希シムシティ大石真史BEiTレベルデザインDETRSporeAIボイスアクターデノイズ南カリフォルニア大学画像処理NVIDIA CanvasSentropyCPUDiscordZorkCALMプログラミングソースコード生成GMAIシチズンデベロッパーTRPGGitHubウィザードリィMCN-AI連携モデルAI DungeonMCS-AI動的連携モデル西川善司並木幸介サムライスピリッツ森寅嘉ゼビウスSIGGRAPH 2021ストリートファイター半導体Topaz Video Enhance AI栗原聡DLSS山野辺一記NetEase大里飛鳥DynamixyzモーションキャプチャーU-Net13フェイズ構造アドベンチャーゲームADVXLandAGI手塚眞DEATH STRANDING不気味の谷Eric JohnsonOculus Questコジマプロダクション生体情報デシマエンジンインディーゲーム写真高橋ミレイ照明Maxim PeterJoshua Romoffハイパースケープ山崎陽斗深層強化学習立木創太CEDEC2021バンダイナムコ研究所ミライ小町GameGANパックマンソサエティ5.0SIGGRAPH 2020DIB-R3D広告

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

2021.9.06ゲーム

【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 / 河合律子

RELATED ARTICLE関連記事

サルでもわかる人工知能 Vol.1:遺伝的アルゴリズム

2019.5.31ゲーム

サルでもわかる人工知能 Vol.1:遺伝的アルゴリズム

【CEDEC2019】1キロ四方のマップを舞台に地形表現の工夫で新しいゲーム体験を作る

2019.9.26ゲーム

【CEDEC2019】1キロ四方のマップを舞台に地形表現の工夫で新しいゲーム体験...

【CEDEC2019】DeNAのゲームAI開発に見る”AIを活かす組織”とは?

2019.10.24ゲーム

【CEDEC2019】DeNAのゲームAI開発に見る"AIを活かす組織"とは?

RANKING注目の記事はこちら