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

TAG LIST
CG機械学習ディープラーニングCGへの扉安藤幸央GAN月刊エンタメAIニュース河合律子ニューラルネットワークOpenAINVIDIA強化学習三宅陽一郎音楽FacebookQAスクウェア・エニックス森川幸人モリカトロンAIラボインタビュー敵対的生成ネットワークDeepMindルールベースキャラクターAIシナリオGPT-3自然言語処理NFTGoogleグーグル自動生成映画デバッグCEDEC2019吉本幸記StyleGANプロシージャル人工知能学会遺伝的アルゴリズムメタAI深層学習マイクロソフトアートビヘイビア・ツリーCEDEC2021大内孝子CEDEC2020ゲームAISIGGRAPH不完全情報ゲームゲームプレイAIVRナビゲーションAI畳み込みニューラルネットワークDALL-ECLIPロボットAIと倫理ディープフェイクGDC 2021VFXメタバースGDC 2019マルチエージェントボードゲームNPCCNNデジタルツインモリカトロンUnityAIアートファッションHTN階層型タスクネットワークDALL-E2JSAI2020TensorFlowMicrosoftイベントレポートテストプレイ水野勇太小説アニメーションガイスターStyleGAN2懐ゲーから辿るゲームAI技術史toioソニーJSAI2021スポーツ研究シムピープル汎用人工知能GDC Summerバーチャルヒューマンブロックチェーン倫理BERTAdobeアストロノーカNVIDIA Omniverseeスポーツ対話型エージェントAmazoneSportsBLUE PROTOCOLシーマンUbisoft画像生成テキスト画像生成AlphaZeroTransformerGPT-2カメラ環世界中島秀之鴫原盛之DARPAドローンシムシティAI美空ひばり手塚治虫Electronic ArtsメタデータLEFT 4 DEADインタビュー通しプレイOpenAI Five本間翔太CMピクサープラチナエッグイーサリアム作曲ビッグデータ中嶋謙互Amadeus CodeMicrosoft AzureキャリアナラティブOmniverse ReplicatorレコメンドシステムNVIDIA DRIVE SimNVIDIA Isaac Simサイバーエージェント音声認識ロボティクスPyTorchDQN眞鍋和子バンダイナムコスタジオaibo合成音声Minecraft齊藤陽介マインクラフトお知らせチャットボットアバターサルでもわかる人工知能VAEOmniverseUbisoft La Forge自動運転車ワークショップGenvid Technologiesメタ知識表現ウォッチドッグス レギオンIGDAどうぶつしょうぎEpic Gamesジェイ・コウガミ音楽ストリーミング徳井直生マシンラーニングクラウド対話エンジン斎藤由多加リトル・コンピュータ・ピープルコンピューティショナル・フォトグラフィーゴブレット・ゴブラーズ絵画AIりんなシミュレーション完全情報ゲーム坂本洋典釜屋憲彦ウェイポイントパス検索対談藤澤仁生物学GTC 2022画像認識GTC2022StyleCLIPDeNA長谷洋平masumi toyota宮路洋一OpenSeaGDC 2022教育TextWorldSIGGRAPH ASIAGTC2021CycleGANNetHackフェイクニュースエージェントAIボイスアクターNVIDIA CanvasImagenGPUALifeZork人工生命オルタナティヴ・マシンサウンドスケープMCS-AI動的連携モデルASBSマンガモーションキャプチャーぱいどんTEZUKA2020ナビゲーションメッシュ松井俊浩バンダイナムコ研究所スパーシャルAIELYZAELYZA DIGEST3D音声合成マーケティングApex LegendsELIZANinjaコンピュータRPGアップルタウン物語KELDICメロディ言語ゲームTENTUPLAYMARVEL Future FightAstroタイムラプスEgo4Dバスキア日経イノベーション・ラボ敵対的強化学習階層型強化学習GOSU Data LabWANNGOSU Voice Assistant竹内将SenpAI.GGMobalytics馬淵浩希Cygames岡島学AWS Sagemaker映像セリア・ホデント形態素解析UXAWS Lambda誤字検出認知科学ゲームデザインSentencePieceLUMINOUS ENGINELuminous Productionsパターン・ランゲージ竹村也哉ちょまどボエダ・ゴティエGOAPAdobe MAX 2021模倣学習Omniverse AvatarFPSNVIDIA Rivaマルコフ決定過程NVIDIA MegatronNVIDIA Merlinスタンフォード大学NVIDIA Metropolisパラメータ設計テニスバランス調整協調フィルタリング人狼知能テキサス大学軍事AlphaDogfight TrialsAI Messenger VoicebotエージェントシミュレーションOpenAI CodexStarCraft IIHyperStyleFuture of Life InstituteRendering with StyleIntelDisneyLAIKADisneyリサーチRotomationGauGANGauGAN2ドラゴンクエストライバルズ画像言語表現モデル不確定ゲームSIGGRAPH ASIA 2021Dota 2モンテカルロ木探索ディズニーリサーチMitsuba2ソーシャルゲームEmbeddingワイツマン科学研究所GTC2020CG衣装NVIDIA MAXINEVRファッション淡路滋ビデオ会議ArtflowグリムノーツEponymゴティエ・ボエダ音声クローニングGautier Boeda階層的クラスタリングGopherJuliusSIE鑑定TPRGOxia Palusバーチャル・ヒューマン・エージェントtoio SDK for UnityArt Recognitionクーガー田中章愛Meta石井敦銭起揚NHC 2021茂谷保伯池田利夫GDMC新刊案内マーベル・シネマティック・ユニバース成沢理恵MITメディアラボMCU著作権アベンジャーズマジック・リープDigital DomainMagic Leap OneMagendaMasquerade2.0ノンファンジブルトークンDDSPフェイシャルキャプチャーサッカーモリカトロン開発者インタビュー里井大輝Kaggle宮本茂則バスケットボール山田暉Assassin’s Creed OriginsAI会話ジェネレーターSea of ThievesGEMS COMPANYmonoAI technologyLSTMモリカトロンAIソリューション初音ミクOculusコード生成AI転移学習テストAlphaCodeBaldur's Gate 3CodeforcesCandy Crush Saga自己増強型AISIGGRAPH ASIA 2020COLMAPADOPデバッギングBigGANGANverse3DMaterialGANリップシンキングRNNグランツーリスモSPORTReBeLグランツーリスモ・ソフィーGTソフィーVolvoFIAグランツーリスモチャンピオンシップRival PrakDGX A100VTuberユービーアイソフトWebcam VTuber星新一賞北尾まどかHALO市場分析将棋メタルギアソリッドVフォートナイトFSMRobloxナップサック問題Live Nation汎用言語モデルWeb3.0AIOpsSpotifyMITスマートコントラクトReplica StudioAWSamuseChitrakarQosmo巡回セールスマン問題ジョルダン曲線メディア5GMuZero政治クラウドゲーミングRival Peakがんばれ森川君2号和田洋一リアリティ番組Stadiaジョンソン裕子MILEsNightCafeインタラクティブ・ストリーミングLuis Ruizインタラクティブ・メディアポケモンCodexシーマン人工知能研究所東京工業大学Ludo博報堂ラップSIGGRAPH 2019ArtEmisZ世代AIラッパーシステムARrinnaGROVERプラスリンクス ~キミと繋がる想い~FAIRSTCチート検出Style Transfer ConversationオンラインカジノRCPアップルRealFlowRinna Character PlatformiPhoneデジタルヒューマンDeep FluidsSoul MachinesMeInGameAmeliaAIGraphブレイン・コンピュータ・インタフェースバーチャルキャラクターBCIGateboxLearning from VideoANIMAK予期知能逢妻ヒカリセコムユクスキュルバーチャル警備システムカント損保ジャパン哲学上原利之ドラゴンクエストエージェントアーキテクチャアッパーグラウンドPAIROCTOPATH TRAVELER西木康智OCTOPATH TRAVELER 大陸の覇者Siemensアルスエレクトロニカ2019品質保証StyleRigAutodesk逆転オセロニアBentley Systemsワールドシミュレーター奥村エルネスト純いただきストリートH100齋藤精一大森田不可止COBOL高橋智隆DGX H100ロボユニザナックDGX SuperPOD泉幸典仁井谷正充クラウドコンピューティングロボコレ2019Instant NeRFartonomousbitGANsぎゅわんぶらあ自己中心派Azure Machine Learning意思決定モデル脱出ゲームHybrid Reward Architectureコミュニティ管理ウロチョロスSuper PhoenixSNS理化学研究所Project Malmoオンラインゲーム気候変動Project PaidiaEarth-2Project Lookoutマックス・プランク気象研究所Watch Forビョルン・スティーブンスBing気象モデルLEFT ALIVE気象シミュレーション長谷川誠ジミ・ヘンドリックス環境問題Baby Xカート・コバーンエコロジーロバート・ダウニー・Jr.エイミー・ワインハウスSDGsMagentaYouTubeダフト・パンクメモリスタSFGlenn MarshallELYZA PencilThe Age of A.I.Story2Hallucination音声変換レコメンデーションJukebox松尾豊Veap JapanEAPテンセントSIFT福井千春DCGAN医療MOBADANNCEメンタルケア人事ハーバード大学Edgar Handy研修デューク大学Netflixデータマイニングmynet.aiローグライクゲーム東京大学東京理科大学人工音声NeurIPS 2021産業技術総合研究所はこだて未来大学リザバーコンピューティングプレイ動画ヒップホップキャラクターモーションソニーマーケティングサイレント映画もじぱNBA環境音暗号通貨現代アートFUZZLEAlteration粒子群最適化法RPG進化差分法オープンワールド群知能下川大樹AIFAウィル・ライト高津芳希P2E大石真史SIGGRAPH 2022BEiTStyleGAN-NADAレベルデザインDETRゲームエンジンSporeUnreal Engineデノイズ南カリフォルニア大学Unity for Industry画像処理SentropyGLIDECPUDiscordAvatarCLIPSynthetic DataCALMバイアスプログラミングサム・アルトマンソースコード生成LaMDAGMAIシチズンデベロッパーSonanticTRPGGitHubCohereウィザードリィMCN-AI連携モデルマジック:ザ・ギャザリングAI DungeonUrzas.ai介護西川善司並木幸介Kikiサムライスピリッツ森寅嘉Zoetic AIゼビウスSIGGRAPH 2021ペットストリートファイター半導体Digital Dream LabsTopaz Video Enhance AICozmo栗原聡DLSSタカラトミー山野辺一記NetEaseLOVOT大里飛鳥DynamixyzMOFLINRomiU-Netミクシィ13フェイズ構造アドベンチャーゲームユニロボットADVユニボXLandGatoAGIテキスト生成手塚眞DEATH STRANDINGマルチモーダル不気味の谷Eric Johnson汎用強化学習AIOculus Questコジマプロダクション生体情報デシマエンジンインディーゲーム写真高橋ミレイ照明Maxim PeterJoshua Romoffハイパースケープ山崎陽斗深層強化学習立木創太ミライ小町テスラGameGANパックマンTesla BotTesla AI Dayソサエティ5.0SIGGRAPH 2020バズグラフニュースタンテキ東芝DIB-R倉田宜典韻律射影広告韻律転移

【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関連記事

【CEDEC2021】NPCとのインタラクティブな対話を実現するGOAPと感情生成パイプライン

2021.11.12ゲーム

【CEDEC2021】NPCとのインタラクティブな対話を実現するGOAPと感情生...

サルでもわかる人工知能 Vol.2:遺伝的アルゴリズムその2「ナップサック問題」

2019.7.02ゲーム

サルでもわかる人工知能 Vol.2:遺伝的アルゴリズムその2「ナップサック問題」

【GDC 2019】AIは感動的な物語体験をゲームで表現できるか? GDCに見る最新トレンド

2019.4.17ゲーム

【GDC 2019】AIは感動的な物語体験をゲームで表現できるか? GDCに見る...

RANKING注目の記事はこちら