［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？

　スクウェア・エニックスが2012年11月23日と24日の両日開催した「スクウェア・エニックス オープンカンファレンス」の最後には「AIセッション」が用意されていた。AIセッションは前半と後半に分かれ，前半は「ファイナルファンタジーXIV: 新生エオルゼア」（以下，新生FFXIV）における経路探索の実装に関する実践的な解説，後半はゲームAIの第一人者とも評される三宅陽一郎氏による，Luminous Studio用AIエンジンのやや概念的な話という構成だった。本稿では，まず前半の，より実践的なセッションから紹介してみたい。
　テーマは，「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だと，当然ながらこのような方法は取れないわけだ。

A＊のような一般的な経路探索アルゴリズムで個々の敵NPCの移動を計算するのは，サーバー側の負荷が大きすぎて無理だという

　新生FFXIVではサーバー側で敵NPCを動かしているが，これらの理由から「A＊（エースター）のような一般的なアルゴリズムは使えなかった」という。A＊というのはポピュラーな最短経路を探索するアルゴリズムの一つで，目標に向かう途中で逐次直近の目標位置を検索していくような手法だ。ほかにもいくつかの経路探索アルゴリズムはあるが，いずれも個々の敵NPCごとにそのような計算をするとサーバーに負荷がかかりすぎるのである。

　そこで新生FFXIVで採用されたのが「経路テーブル」を使う手法だ。経路テーブルは，目的地まで移動する際の経路をあらかじめ計算して表にしたものだ。これはゲームでは古くから使われている手法である。

経路テーブルの例。左側の丸数字は地点と考えてほしい。矢印についている数字は，地点間の距離だ。一方，右表の横軸は，いま敵NPCがいる地点，縦軸は目的の地点だ。例えば1から5にいくのなら，まず3に行くのが最短距離と分かる。そこで，1→5のテーブルには3を入れておく。続いて，3から5に行く場合の経路を見ると，次は4に移動し，以下，2，5と移動するのが最短となる。このようにテーブルには，次に移動すべきマスの番号を格納しておく

表を引く手順：1から5に行きたいとき，現在地点を横軸，目的地を縦軸にして表を引くと，次に移動すべき場所を得られる。ここでは3なので，3を起点として目的地5への表を引く……といった操作を目的地に達するまで繰り返していく

　図のように，あらかじめ，最短で目的地に行くときに通過する直近の地点を表にしておくことで，表を参照するだけで経路を決めることができるため，サーバー側のCPU負荷は極めて低くなる。さらに，実行時のメモリ消費の動的な増減が発生しないという点も横山氏は経路テーブルを使う利点として挙げていたのだが，容易に想像がつくとおり，この方式でのメモリ消費自体は，地点が増えるにつれて急激に大きくなってしまう。

2万×2万のメッシュ（※形状メッシュではなくて，ナビゲーション用のメッシュ。マップ上の移動可能地点と考えてほしい）でのテーブルのサイズは，なんと1.1GBにもなる。マップ1個でこれだと，いくら高性能なゲームサーバーでもMMORPGの全マップを扱うのはメモリ的に厳しい

　広大なマップではテーブルの大きさはGB単位になってしまい，メモリの消費量がバカにならない。また，テーブル参照は軽いといっても，サイズが膨れ上がるとオンメモリでの利用ができなくなる可能性もありそうだ。オンメモリで利用できなければI/Oの負荷が生じるので，非テーブル参照でのCPU負荷以上に問題になるだろう。
　というわけで，テーブルの利点を生かしつつメモリ消費を抑える方法として，新生FFXIVではマップを区画（グリッド）に分け，階層的にテーブルを分割する方法を採用したという。

新生FFXIVでは広いマップをグリッドに分け，グリッドごとにテーブルを作ることでメモリ消費を抑えている。テーブルが対称形でないのは，一方通行の通路（飛び降りるなど）に対応しているため

　具体的には，マップをグリッドに分け，グリッドごとにテーブルを作成する。これで縦横の数が減ってテーブルのサイズはかなり削減できるわけだ。さらにグリッドの経路を表す上位テーブルを用意すると，例えばマップの端から端まで移動するようなケースでも，まず上位テーブルを参照して目的地のグリッドへの経路を得て，下位のテーブルを使ってグリッド内を移動するという形で実行できるようになる。

この例では，A，B，C，Dという四つのグリッドに分け，グリッドごとのテーブルを作っている。さらにA，B，C，Dの経路を記録した上位テーブルを用意する。これでマップの端から端までの移動のような長い移動の経路もテーブルをたどるだけで得られるようになる

　マップをグリッドに分けて上位と下位の階層でテーブルを持たせる効果は劇的で，先の例に挙げられていた2万×2万のメッシュを100×100のグリッドで分けると，1.1GBだったテーブルサイズは，11MBにまで低減できるとのことだ。
　ただ，問題はある。上位テーブルでは，次に進むべきグリッドしか分からない。具体的な移動地点が分からないと，下位テーブルで移動しようがないのだ。そこで，各グリッドとグリッドの接合部に「つながりポイント」を用意し，次のグリッドに移動する際には，そのつながりポイント目指して移動を行おうということになる。
　しかし，つながりポイントからつながりポイントへ……というふうに移動すると，目的地まで最適なコースが取れないという事態が生じるという。最短距離とは関係のないつながりポイントを経由していくわけだから，これは分かりやすい話だろう。

グリッドの外に目標地点がある場合，つながりポイントを設定して，そこを経由する形で移動すると，スライド右側のようにクネって移動しなければならなくなる。あまり賢い移動とはいえない印象だ

　そこで横山氏らが取ったのは，隣接したグリッドをまとめてテーブル化して，より広い範囲のグリッドを参照するという方法だ。新生FFXIVでは，とあるグリッドとその周囲のグリッド合計8個，つまり9個のグリッド分のテーブルを参照して，最適な経路を探索するようにしているそうである。固定されていたつながりポイントの代わりに，仮想的なサブゴールを設定し，そこに向かうような経路を探索していく。

「敵NPCがいる位置の周囲を含む9個のグリッドで作られたテーブル」を参照して，より広い範囲の経路の探索を行うようにしているという

1グリッド分の範囲を越えて移動したら，テーブルを次のグリッドのものに切り替えていく。これで比較的，自然な経路が取れるようになったそうだ

　上のスライドのようにテーブルを階層化し，さらに隣接化した手法を「Hierarchical Neighborhood lookup‐Table」（HiNT）と呼んでいるそうだ。「階層化近接ルックアップテーブル」の略だが，語呂合わせっぽい感じもある。
　いずれにしても，以上のような方法でメモリ消費やCPU負荷を抑え，なおかつ敵NPCが賢くマップを移動する工夫が施されているわけである。グリッドごとのテーブルサイズは9倍になるが，その程度であれば大きな問題にはならないようだ。

実際のテーブルはメッシュから自動で生成

　実際のサーバー上で使うテーブルは，どのように生成されているのだろうか。テーブルを作成する方法や，それを用いた敵NPCの移動に関してはファビアン氏から説明があった。

　マップ上の移動可能な場所は，ナビゲーション用のポリゴンメッシュ（以下ナビメッシュ）で表現されている。

移動可能な場所をポリゴンメッシュで表現し，移動できる通路をグラフ化する

　このナビメッシュからテーブルを作成するわけだが，もちろん人手でやっていてはいくら時間があっても足らないだろう。なんとしても自動化する必要があるのだが，HiNTでは「隣接化したテーブルを階層化する」という一捻りが必要になる。
　ファビアン氏によると，ナビメッシュから階層を作ることに加えて「コンポーネント」と呼ばれる「内部で移動できることが明確に分かっているポリゴンのグループ」を作っているという。

ナビメッシュをグリッドに分け，さらにグリッドを集めて上位層を作成する

青い部分が通れるところ，黒い部分は障害物	障害物で直接行けない場所はコンポーネントを分ける	グリッドの境界でさらに分割
領域内のポリゴン間の最短経路を探る	最短経路がほかの色を経由することがあると	コンポーネントを分割する

　コンポーネントは，経路を探索しているテーブルの先にある本目標に到達するための，仮目標として使うために作成しているそうだ。先の説明のように，この方式でも敵NPCの移動の際に，移動中のグリッドを中心に9個のグリッドを参照して経路を探索するが，本目標がその範囲を超えるときには，目標の方向にあるコンポーネントを仮の目標にするわけだ。仮目標に到達すれば，同一コンポーネント内は自由に移動できるので，問題なく移動の続行ができるという仕組みだ。

　実際のテーブルの作成では，コンポーネントから階層を生成する。移動可能なコンポーネント単位で隣接化が実現されているわけだ。

敵NPCがいまいるグリッドを囲む合計9個のグリッドの，さらに先のコンポーネントにも，経路テーブルで移動が可能だ。その際には，隣接するコンポーネントを仮目標として利用する

テーブルを生成するアルゴリズム。グリッドごとにテーブルを作り，コンポーネントを作り，コンポーネントから階層を作る。そして，それを繰り返してマップ全体のテーブルを作成する

　セッションでは，このようにして生成したテーブルを使った探索の例が紹介されたが，やや込み入っているので，ここは実際の移動のムービーを見てもらったほうがいいだろう。

　下のムービーでは，実際にキャラクターがグリッドから次のグリッドへと移動している様子が示されている。ナビメッシュから生成したテーブルを使って経路を得て，途中を滑らかにするアルゴリズム（ファンネルアルゴリズム）を使ってスムーズにしているとのこと。目的地に向かって無駄なく移動している様子が分かるだろう。


　ナビメッシュの作成には，「Recast」というオープンソースのツールを用いたという。このツールは，Web上からソースコードとデモがダウンロードでき，実際にデモを動かして試せるので，興味がある読者はリンク先を参照してみてほしい。

　また，新生FFXIVでは「落下メッシュ」という落ちることができるメッシュが設定されている。落下できる点と着地点，さらに登れるところを探し，落下する部分を落下メッシュとし，キャラクターが落ちて，さらに移動するといった動きができるようになっている。
　セッションではナビゲーションメッシュの生成や落下メッシュの生成のアルゴリズムが詳しく説明されたが，やや込み入っているので本稿では割愛したい。落下メッシュは例として動画があるので，それを見てほしい。


　メッシュの生成ツールは開発チームが使用するレベルエディタに組込み，レベルエディタからナビメッシュを自動生成できるシステムを開発したという。さらに，MayaなどのDCCツールでナビメッシュを読み込み，手動で修正できるようにもしているそうだ。

　ナビメッシュの自動生成で，マップの作成効率は非常に上がったというが，その難しさについても触れていた。とくに問題が生じたのは，通れるか通れないか程度の狭い通路の場合だそうで，新生FFXIVでは，メッシュ生成時に入力するコリジョンデータを修正して直すケースが多かった，とのことである。

ナビメッシュの自動生成では，狭い通路のような部分でナビメッシュがうまく作られないという問題が生じやすかったそうだ。新生FFXIVでは，問題解消のためにコリジョンデータを修正してナビメッシュを作り直すケースが多かったとのこと

　しかし，自動生成により，例えば28000ポリゴン程度の大きなマップでもメッシュの生成時間は1分30秒，データサイズはトータルで7MB程度と，時間の短縮が実現できたそうである。ちなみに横山氏が，「ナビメッシュを使ってゲーム内で表示するワールドマップを生成している」と説明していたのは興味深かった。


　確かにナビメッシュからは移動できるマップの画像が生成できるので，ワールドマップを作るには適切な素材になるだろう。ゲームAIの成果が，ゲームを飾る意外な部分でも利用されているのだなと感心させられた。読者も新生FFXIVをプレイするときには，キャラクターの移動を追ってみて，この経路探索の話を思い出してみるとゲームに対する興味がより増すのではないだろうか。