
イベント
[SQEXOC 2012]FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか?
![]() |
テーマは,「MMORPGでマップ上を移動する敵NPCの経路をどう決めるのか」である。複雑で広いマップを有するMMORPGでは,移動する経路を賢く選択することも難しい課題になってくる。新生FFXIVで使われている手法の概要を紹介してみよう。
経路テーブルを階層化して軽量化を図る
一昔前のゲームでは,敵NPCが障害物に阻まれて身動きが取れなくなったりすることが普通に見られたものだが,最近はそういうことはあまりなくなってきている。その背景には敵NPCを制御しているAIプログラムの進化がある。
今回のセッションのテーマになっているのは,新生FFXIVにおいて「敵NPCをマップ上で効率的に動かすために,どのようなアルゴリズムを採用しているのか」である。確かに,広いマップや複雑な地形の上で目的の場所にAIがたどり着くのは容易なことではなさそうだ。
解説を担当したのは,Luminous StudioのAI プログラマを務める横山貴規氏と,同プロジェクトでAI リサーチャーを務めるグラヴォ・ファビアン氏の両名だ。
![]() 横山貴規氏(Luminous AI プログラマ) |
![]() グラヴォ・ファビアン氏(Luminous AI リサーチャー) |
新生FFXIVにおけるAI処理の難しさについて,横山氏はまず「非常に敵NPCが多いこと」を挙げる。マップあたり1000体ほどの敵NPCが動き回っているといい,確かに個々に移動経路を計算しているとその負荷は相当なものになりそうではある。
横山氏は,もう一つ「MMORPGでは,“プレイヤーの近くにきたときだけ敵NPCを動かす”手法が取れない」という点も挙げていた。FPSのキャンペーンなどではプレイヤーがエリアに入ったことをトリガーにして敵NPCが動き出すという方法が用いられるが,大勢のプレイヤーがオンラインで接続しているMMORPGだと,当然ながらこのような方法は取れないわけだ。
![]() |
そこで新生FFXIVで採用されたのが「経路テーブル」を使う手法だ。経路テーブルは,目的地まで移動する際の経路をあらかじめ計算して表にしたものだ。これはゲームでは古くから使われている手法である。
![]() |
図のように,あらかじめ,最短で目的地に行くときに通過する直近の地点を表にしておくことで,表を参照するだけで経路を決めることができるため,サーバー側のCPU負荷は極めて低くなる。さらに,実行時のメモリ消費の動的な増減が発生しないという点も横山氏は経路テーブルを使う利点として挙げていたのだが,容易に想像がつくとおり,この方式でのメモリ消費自体は,地点が増えるにつれて急激に大きくなってしまう。
![]() |
広大なマップではテーブルの大きさはGB単位になってしまい,メモリの消費量がバカにならない。また,テーブル参照は軽いといっても,サイズが膨れ上がるとオンメモリでの利用ができなくなる可能性もありそうだ。オンメモリで利用できなければI/Oの負荷が生じるので,非テーブル参照でのCPU負荷以上に問題になるだろう。
というわけで,テーブルの利点を生かしつつメモリ消費を抑える方法として,新生FFXIVではマップを区画(グリッド)に分け,階層的にテーブルを分割する方法を採用したという。
![]() |
具体的には,マップをグリッドに分け,グリッドごとにテーブルを作成する。これで縦横の数が減ってテーブルのサイズはかなり削減できるわけだ。さらにグリッドの経路を表す上位テーブルを用意すると,例えばマップの端から端まで移動するようなケースでも,まず上位テーブルを参照して目的地のグリッドへの経路を得て,下位のテーブルを使ってグリッド内を移動するという形で実行できるようになる。
![]() |
マップをグリッドに分けて上位と下位の階層でテーブルを持たせる効果は劇的で,先の例に挙げられていた2万×2万のメッシュを100×100のグリッドで分けると,1.1GBだったテーブルサイズは,11MBにまで低減できるとのことだ。
ただ,問題はある。上位テーブルでは,次に進むべきグリッドしか分からない。具体的な移動地点が分からないと,下位テーブルで移動しようがないのだ。そこで,各グリッドとグリッドの接合部に「つながりポイント」を用意し,次のグリッドに移動する際には,そのつながりポイント目指して移動を行おうということになる。
しかし,つながりポイントからつながりポイントへ……というふうに移動すると,目的地まで最適なコースが取れないという事態が生じるという。最短距離とは関係のないつながりポイントを経由していくわけだから,これは分かりやすい話だろう。
![]() |
そこで横山氏らが取ったのは,隣接したグリッドをまとめてテーブル化して,より広い範囲のグリッドを参照するという方法だ。新生FFXIVでは,とあるグリッドとその周囲のグリッド合計8個,つまり9個のグリッド分のテーブルを参照して,最適な経路を探索するようにしているそうである。固定されていたつながりポイントの代わりに,仮想的なサブゴールを設定し,そこに向かうような経路を探索していく。
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
上のスライドのようにテーブルを階層化し,さらに隣接化した手法を「Hierarchical Neighborhood lookup‐Table」(HiNT)と呼んでいるそうだ。「階層化近接ルックアップテーブル」の略だが,語呂合わせっぽい感じもある。
いずれにしても,以上のような方法でメモリ消費やCPU負荷を抑え,なおかつ敵NPCが賢くマップを移動する工夫が施されているわけである。グリッドごとのテーブルサイズは9倍になるが,その程度であれば大きな問題にはならないようだ。
実際のテーブルはメッシュから自動で生成
実際のサーバー上で使うテーブルは,どのように生成されているのだろうか。テーブルを作成する方法や,それを用いた敵NPCの移動に関してはファビアン氏から説明があった。
マップ上の移動可能な場所は,ナビゲーション用のポリゴンメッシュ(以下ナビメッシュ)で表現されている。
![]() |
このナビメッシュからテーブルを作成するわけだが,もちろん人手でやっていてはいくら時間があっても足らないだろう。なんとしても自動化する必要があるのだが,HiNTでは「隣接化したテーブルを階層化する」という一捻りが必要になる。
ファビアン氏によると,ナビメッシュから階層を作ることに加えて「コンポーネント」と呼ばれる「内部で移動できることが明確に分かっているポリゴンのグループ」を作っているという。
![]() |
![]() 青い部分が通れるところ,黒い部分は障害物 |
![]() 障害物で直接行けない場所はコンポーネントを分ける |
![]() グリッドの境界でさらに分割 |
![]() 領域内のポリゴン間の最短経路を探る |
![]() 最短経路がほかの色を経由することがあると |
![]() コンポーネントを分割する |
コンポーネントは,経路を探索しているテーブルの先にある本目標に到達するための,仮目標として使うために作成しているそうだ。先の説明のように,この方式でも敵NPCの移動の際に,移動中のグリッドを中心に9個のグリッドを参照して経路を探索するが,本目標がその範囲を超えるときには,目標の方向にあるコンポーネントを仮の目標にするわけだ。仮目標に到達すれば,同一コンポーネント内は自由に移動できるので,問題なく移動の続行ができるという仕組みだ。
実際のテーブルの作成では,コンポーネントから階層を生成する。移動可能なコンポーネント単位で隣接化が実現されているわけだ。
![]() |
![]() |
![]() |
![]() |
![]() |
セッションでは,このようにして生成したテーブルを使った探索の例が紹介されたが,やや込み入っているので,ここは実際の移動のムービーを見てもらったほうがいいだろう。
下のムービーでは,実際にキャラクターがグリッドから次のグリッドへと移動している様子が示されている。ナビメッシュから生成したテーブルを使って経路を得て,途中を滑らかにするアルゴリズム(ファンネルアルゴリズム)を使ってスムーズにしているとのこと。目的地に向かって無駄なく移動している様子が分かるだろう。
ナビメッシュの作成には,「Recast」というオープンソースのツールを用いたという。このツールは,Web上からソースコードとデモがダウンロードでき,実際にデモを動かして試せるので,興味がある読者はリンク先を参照してみてほしい。
![]() |
セッションではナビゲーションメッシュの生成や落下メッシュの生成のアルゴリズムが詳しく説明されたが,やや込み入っているので本稿では割愛したい。落下メッシュは例として動画があるので,それを見てほしい。
メッシュの生成ツールは開発チームが使用するレベルエディタに組込み,レベルエディタからナビメッシュを自動生成できるシステムを開発したという。さらに,MayaなどのDCCツールでナビメッシュを読み込み,手動で修正できるようにもしているそうだ。
ナビメッシュの自動生成で,マップの作成効率は非常に上がったというが,その難しさについても触れていた。とくに問題が生じたのは,通れるか通れないか程度の狭い通路の場合だそうで,新生FFXIVでは,メッシュ生成時に入力するコリジョンデータを修正して直すケースが多かった,とのことである。
![]() |
しかし,自動生成により,例えば28000ポリゴン程度の大きなマップでもメッシュの生成時間は1分30秒,データサイズはトータルで7MB程度と,時間の短縮が実現できたそうである。ちなみに横山氏が,「ナビメッシュを使ってゲーム内で表示するワールドマップを生成している」と説明していたのは興味深かった。
![]() |
確かにナビメッシュからは移動できるマップの画像が生成できるので,ワールドマップを作るには適切な素材になるだろう。ゲームAIの成果が,ゲームを飾る意外な部分でも利用されているのだなと感心させられた。読者も新生FFXIVをプレイするときには,キャラクターの移動を追ってみて,この経路探索の話を思い出してみるとゲームに対する興味がより増すのではないだろうか。
- 関連タイトル:
FINAL FANTASY XIV(旧)
- 関連タイトル:
ファイナルファンタジーXIV:新生エオルゼア
- 関連タイトル:
ファイナルファンタジーXIV
- この記事のURL:
キーワード
- PC
- HARDWARE
- PC:FINAL FANTASY XIV(旧)
- PS3:ファイナルファンタジーXIV:新生エオルゼア
- PS3
- SQEXOC 2012
- SQEXOC
- イベント
- ライター:米田 聡
- PC:ファイナルファンタジーXIV

(c)2010 SQUARE ENIX CO.,LTD. All Rights Reserved.
※SQUARE ENIXおよびSQUARE ENIX ロゴ,ファイナルファンタジー/FINAL FANTASYは,日本およびその他の国における株式会社スクウェア・エニックス・ホールディングスの商標または登録商標です。
※エオルゼア/EORZEAは,日本およびその他の国における株式会社スクウェア・エニックスの商標または登録商標です。
(C)2010-2016 SQUARE ENIX CO., LTD. All Rights Reserved.
© SQUARE ENIX
LOGO & IMAGE ILLUSTRATION:© YOSHITAKA AMANO