［GDC 2021］ギミックを駆使して複雑な地形を踏破する「DEATH STRANDING」のAI技術

　2021年7月19日，世界最大のゲーム開発者会議であるGame Developers Conferenceが開幕した。新型コロナウイルス感染症の流行により，今年もオンライン開催となった。当初はオンラインとオンサイトのハイブリッドイベントとして計画されていたが，オンサイトのイベントもバーチャルブースという扱いになり，完全オンラインイベントとして開催されている。無料だった昨年とは異なり，通常のGDCと同様の有料イベントに戻っている。

　本稿では，初日に行われた講演の中から，KOJIMA PRODUCTIONSによる「DEATH STRANDING」（PC / PS5 / PS4）のキャラクターAIに関するセッションの概要を紹介してみたい。

　DEATH STRANDINGは，2019年に発売されたPS4用のアクションアドベンチャーだ（PC版は2020年に発売）。小島秀夫氏が率いるKOJIMA PRODUCTIONSの新規IPタイトルということで注目されていたが，ゲームの世界観やシステムの斬新さが大いに驚きを呼んだ。


　講演を行ったKOJIMA PRODUCTIONSのAI ProgrammerであるEric Johnson氏によると，本作は環境の踏破に重点を置いた作品だという。複雑な地形や天候の影響といった条件への対応，さらには「ロープ」「梯子」「橋」といったツールを駆使し，環境を克服していく。本作では，多彩な問題解決手段を講じて目的地に到達することが要求されるのだ。
　このような複雑な条件に対し，プレイヤーは当然として，それを追って荷物を奪いにくるミュール達など，AIで動くNPCにもプレイヤーと同程度に環境への適切な対応が求められる。本作のAIチームはどのように解決したのだろうか。

KOJIMA PRODUCTIONSのAI Programmer Eric Johnson氏

　プレイヤーは膝くらいまでの高さの石ならそのまま乗り越えられる。当然，NPCも同じようにすべきだ。石を乗り越えるときには一定確率で滑ったり躓いたりするのだが，これも同様だ。ということで，普通のプレイヤーならそういったリスクのある石はなるべく踏まないように走るわけだが，NPCに同じことをさせるにはどうしたらいいだろうか。
　配置されている石の周囲には，通れないわけではないが，一定のリスクのあるエリアとして，ハイコストの設定が行われている。リスクを減らすなら，コストの低い部分を走ればよい。「それでは距離（時間）的にリスクがある」と判断するなら，石を踏んでいくのもよい。このようにコストを加味した経路探索が，AIに取り入れられている。

ナビゲーションメッシュにコストが追加されている

　まず，地形とナビゲーションメッシュをどのようにしたのか。複雑な地形のオープンワールドで，このようなコストも加味した手法を取ると，経路探索自体のコストが非常に高くなる。そこで彼らは，ナビゲーションメッシュでの経路探索でよく使われるAIアルゴリズムでの反復を500回に限定したという。DEATH STRANDINGのナビメッシュ生成はランタイムでキャラクターの周囲だけに行われるのだ。


　しかし崖のあるような複雑な地形では，わずか25mを進んだだけで500回の反復を使い切ってしまう。ナビメッシュが細かくなると計算コストは非常に高くなり，目的地に辿り着ける保証もない。


　場合によっては再探索が必要だが，いつそれをするのか。一般的にはレイキャストを使ったり，合間合間で再探索をするという手法があるのだが，レイキャストは近くの前方にしか使えず，遠くで環境が変化しても十分に近づかないと検知できない。
　定期的に探索する手法では，どれくらいの頻度でやればいいのか判断が難しい。適当な値では走っているときには足りず，歩いているときには無駄な演算が増えてしまいがちだという。AIチームが初期実装で採用したのは，1秒間に2回，前方にだけ再探索を行うという手法だった。NPCに対しては，探索頻度を減らすため一定の境界を越えた瞬間に再探索を行うようにしている。


　初期実装では再探索で5つのケースが考えられている。外的な力などでキャラクターがナビメッシュから外れてしまう場合。目標が最終ポリゴンからほかのポリゴンへ移動してしまった場合。ナビメッシュの一部が無効になった場合。目標はナビメッシュが生成されていない場所にあり，移動最中にNPCと目標の間にナビメッシュが追加されたり削除されたりする場合。途中で500回に達するなどで部分経路の端に到達した場合だ。これに対応したバリデータが追加され，それぞれの条件をフレームごとにチェックしており，自動的に再探索が実行されるという。


　そして初期実装での不具合も紹介された。NPCがパトロールしている時に，本来なら直線で目標まで行けたはずの場所にS字を描いて大きく迂回しているのだ。これは，経路の再探索がリアルタイムで完全に行われているわけではなく，ナビメッシュタイルのエッジの中点を経路が通過した場合に隣のメッシュの更新を行うといった感じで簡略化されていることが原因だったという。本来直線であるべき経路が折れ曲がった形になってしまっている。


　この問題について調べているときに，10年ほど前のBlogで同じ問題について書かれているものを発見したそうだ。同じ問題に悩む質問者に対して執筆者のMikko Mononen氏は，レイキャストを使って直線が通るかテストすることを勧めていた。通るようであればパス廊下を配置し直すのだ。さらに最適になるようにパスも引き直す。Mononen氏はもともと，Mononen氏がパス廊下最適化は前方向へ進んでレイキャストチェックを行うように提案していたが，Eric氏はそのあとさらに後方向にも廊下の最適化チェックを行ったという。


　初期にあった定期的に再探索する実装をやめて再探索をイベント式に移動する結果，パス廊下がいつも正しいことが保証できたが，NPCの旋回半径が大きすぎると最初に廊下に引いたパスにある次の角に到達できない場所へ移動してしまい，廊下から出て再探索しても別のパス角で同じ現象を繰り返し，いつまでも目標に到達できないこともあった。この現象に関して，Mononen氏はパス廊下にパスを引くアルゴリズム（string pulling）が非常に軽いため，パス廊下に確実に次の角を向かっていくのにフレームごとに行うように勧めていた。Mononen氏が提案した通りフレームごとにパス廊下内にパスを引くようにしたら自然な動きができるようになった。


　この実装はテスト地形ではうまく動いたが，ほかの地形ではNPCが突然360度回転して進み出すというバグが発見された。傾斜地などの進入に対するハイコストエリアに到達したときに再探索を行うものの，そちらも距離的なコストでダメだとまた元の道に戻るような動きをするのだ。
　ここで想定されていたコストは移動コストで，主にかかる時間的なものだ。傾斜地などでは移動コストが通常の5倍と高く設定されていた。これを距離の等倍に戻し，代わりに一時的な進入コストを設けている。ハイコストエリアには入りにくくなったが，入ってしまえばそのまま進めるといった感じの挙動が期待できる。これを進めることで地形に対する自然な動きを実現できたという。


　しかし，NPCの周りにナビメッシュのタイルを生成か破壊したり，目的地が移動したりする場合では，依然としてNPCの移動に異常が起こっていた。さらに，複雑な地形では，出口に相当する部分を500ループ以内に発見できないといった最悪のケースもありうる。


　そこでAIチームが利用したのは，ゲームエンジンDecimaの機能の1つである，AI Road Networkだった。これは，完全に通れる道をマップ上で定義して，キャラクターの移動に利用するものだ。この機能とナビメッシュの機能を合わせて使うことで，複雑な経路を手軽に得られるようになる。


　何段もの崖を昇る経路が示された場合は，再探索を繰り返しながら進んでいたが，500回の反復では解決できない状態に陥ることがあった。それが，通れる道をあらかじめ設定しておくことで，それに沿った経路決定が行われ，複雑な崖の道を通り抜けられるようになる。この組み合わせで，あらゆる地形に対応できるようになったという。


　次に語られたのはダイナミックな地形への対応だ。DEATH STRANDINGでは建物などを破壊できるほか，プレイヤー自身が橋や梯子を使って普通には通れない個所を無理やり踏破できる。浮き沈みする地形や置かれた乗り物などで，通れる部分が変化することもある。


　そして，プレイヤーを追いかけるNPCには，プレイヤーと同じ移動ができることが求められた。まず橋は，橋の上に作られたナビメッシュをNPCが利用することで対応できる。問題は梯子である。一般的なゲームに登場する梯子は，垂直に移動する手段を与える動かないオブジェクトであることがほとんどだが，本作の梯子はプレイヤーが斜めに立てかけることも，横に渡して橋の代わりにすることもできる。これをNPCも使えるようにするには，どうすればいいのだろうか。


　一般的な垂直の梯子には4種類の乗り方と5種類の降り方があるという。乗るときは，「下（正面）」「上」「横」「背後」。降りるときは「上」「下（正面）」「上に跳ぶ」「横に跳ぶ」「正面に跳ぶ」といった形で分類されていた。


　横に渡した梯子では同様に，両端から乗る，横から乗るの2種類の乗り方と，両端から降りる，横から降りる，下肢から跳ぶ，横に跳ぶの4種類の降り方がある。


　梯子には50cm間隔でチェックポイントが設けられ，周辺のナビメッシュとの接続が調べられる。乗る場合はその接続部分を見ればよい。降りる場合は，接続された部分はそのままで降りられる。飛び降りはどこからでもできるのだが，降りた先にナビメッシュがない，もしくはコリジョン判定に失敗しそうな場合は無視しているとのことだ。これらのシチュエーション分けで，NPCもプレイヤーと同様な挙動で梯子を使えるようになる。


　続いて，地形の回避などについての挙動だ。単純な障害物はナビメッシュで自動的に回避できるが，目的地が通れなくもないところ，つまりハイコストエリアにある場合の挙動が怪しい。川の中にプレイヤーがいる場合，それを追うNPCは，まず川岸までやってきて，プレイヤーの向こうの川岸に渡り，続いて元の川岸に戻るといった挙動を繰り返すようになるのだという。
　前述の進入コストを設定することで，ハイコストエリアを選択しないようになったものの，近くに同程度の魅力的なポイントがあるのでそちらに行ってしまうのだ。途中にぬかるみがあるのは仕方なく通るけど，水たまりを目的地にはしないよという感じだろうか。


　本作の空間探査システムではダイクストラ法を使って，コストを加味した最短経路を求めているそうなのだが，そこで使われる移動コストは地形のペナルティと距離コストを合わせたものとなっている。Johnson氏は，そこから距離コストを引いた差分コストを利用することを提唱していた。


　ここは見ていてもよく分からなかった部分なので誤解があるかもしれない。元々地形コストのデータがあって，それとキャラクターからの距離を加味して移動コストの図が得られるはずだが，元データを使わずに距離コストを引いて差分を求めている意味がよく分からなかった。
　NPCがハイコストエリア（川）の外にいる場合，NPCは川の中に入ろうとはしない。最初から川の中にいる場合は，周りがハイコストエリアなのでまったく移動しなくなるという。そこで，必要があればハイコストエリアを通り，ハイコストエリアにずっといることでもコストがかかるように，移動コストと距離コストをいじってやるのだという。これによりNPCに川を渡らせることができる。

※2021年7月26日13:10，上記の不明点などについて，記事掲載後にKOJIMA PRODUCTIONSよりいただいたEric Johnson氏の解説を追記しました

「位置選択時に『空間クエリーシステム』というものがあり，そしてこれがNPCの周りにいくつかの場所を評価する役割があります。NPCの場所からそれぞれの候補位置までのパス距離も，パスコストが計算して目的として適切性を判断できます。なので，パスコストとパス距離の差分を計算することで，NPCの位置から，水の中の場所も，到達するのに水の中を通過する必要のある場所も，差分が大きいため評価を低くできるのです。
　ところが，すでに水の中にいる時，現在地からどこへ移動してもある程度水の中を通過するが，現在地から移動しなかったら厳密にいうと水の中を通過していない（パス距離がゼロ）ことになるので，現地点だけはパス距離とパスコストの差分もゼロとなり，それ以外の場所がすべてより評価が低くなってしまうのです。
　その結果，NPCは“移動しないことが一番適切だ”と判断してしまう現象が発生しました」（KOJIMA PRODUCTIONS・Eric Johnson氏）

　そのほかのAI要素として，地形や障害物を利用したNPCのカバー動作を実現するタイルベースのカバーマネージャや，AIシステムにLoDを設定して負荷を軽くする手法，時間の早回しといったものも解説されていた。


　AI開発での失敗事例としては，双方向探索が挙げられていた。これは2018年のAI SummitでNathan Sturtevant氏が発表したものだそうだが，試しに実装してみると素晴らしい性能を発揮したのだという。ところが，片側からだけジャンプできるリンクを追加すると，探査の対称性が破綻し双方向では扱えなくなる。このゲームでの採用は見送られることになった。

双方向経路探索は最初は素晴らしい性能を発揮していたが……

　再探索が発生しないように，ベジエ曲線がパス廊下を出ないように曲線の形を制限したが，制限するための処理が厳しすぎたため，最終的な曲線が直線とあまり変わらない時が多かったとのことだ。
　最後に，梯子とストランドオブジェクト（タールから出てくる建物などのもの）を乗ったり下りたりするためのジャンプリンクがプロシージャルで自動生成できたが，それ以外のジャンプリンクはすべて手作業で配置されたという。ここは開発スケジュールが間に合わなかったのだそうだ。非常に手間がかかったとのことで，自動化できなかったことは後悔しているという。

　複雑な地形と自由度の非常に高い移動方法という高難度な要素を組み合わせて，なおかつ自然な動きを追求した本作のキャラクターAIは，非常に挑戦的なものといえる。本作で実装できなかった要素も含めて，今後の作品が楽しみに思えるのは私だけではないだろう。今後のさらなる発展に期待したい。

「DEATH STRANDING」公式サイト