いかにしてサーバーはモンスターを歩かせるのか? 『ファイナルファンタジーXIV: 新生エオルゼア』の経路探索テクニック【SQEXオープンカンファレンス2012】

2012年11月23日と24日、スクウェア・エニックスが公開技術カンファレンス“スクウェア・エニックスオープンカンファレンス2012”を開催した。本稿では、横山貴規氏とFabien Gravot氏による“サーバーサイド経路探索システム”についての講演の内容をお届けする。
assets3/01.jpg

 2012年11月23日と24日、スクウェア・エニックスが東京都のベルサール神田で公開技術カンファレンス“スクウェア・エニックスオープンカンファレンス2012”を開催した。
 その中から本稿では、横山貴規氏とFabien Gravot氏による“サーバーサイド経路探索システム”についての講演の内容をお届けする。

 本講演で扱われたのは、『ファイナルファンタジーXIV: 新生エオルゼア』のモンスターやNPCの経路探索システム“HiNT(Hierarchical Neighborhood lookup Table)”について。
 あるキャラクターがA地点からB地点へと移動していく場合、2点間を結んだ直線を歩けるとは限らない。当然マップ上には通れない部分やらがあるわけで、そこを避けてぐるっと周って行ったり、遠回りな方向がむしろ近道だったりするわけである。
 『ファイナルファンタジーXIV: 新生エオルゼア』では、この“AIキャラクターがどこをどう歩いていけばいいのか”という経路探索のシステムをサーバー側で行なっているのだが、いくつか必要な要件がある。


assets3/TN2_2236.JPG

 まずは、1マップで非常にたくさんの敵が同時に動くということ。オフラインのゲームではないので、プレイヤーの周囲でしか動かないといった軽量化は使えない。
 そしてマップの大きさと複雑さ。マップは最大2キロ四方あり、種類も多い。各マップへの対応を自動的に実行できないといつまでたっても終わらない。さらにはジャンプして飛び上がったり落下したりといったアクションもあり、これらに対応しなければならない。
 『ファイナルファンタジーXIV: 新生エオルゼア』の経路探索システムは、こうした要件を満たした上で、経路探索に使うサーバーの処理コストをできるだけ抑える必要があるのだ。


assets3/TN2_2246.JPG assets3/TN2_2248.JPG assets3-1/TN2_2250.JPG

●1:ナビゲーションメッシュに対して経路テーブルを作る

assets3/TN2_2253.JPG

 経路探索システムを手掛けた横山氏とGravot氏が負荷を減らすために選択したのは、ナビゲーションメッシュに対して経路テーブルを事前の自動計算で用意するという方法。ナビゲーションメッシュというのは、移動可能な場所をポリゴンメッシュで示したものだ。

 経路テーブルは、例えば現在地点とゴールの2点を指定すると、事前計算によってわかっている“まず通るべき場所”を教えてくれる一種の表と考えてもらっていい。地点Aから地点Fに行く際にA→S→D→Fが最適なルートであれば、AとFを元にテーブルを参照すると、まずSと書いてあり、次にSとFでテーブルを見るとDと書いてある……という寸法。


assets3/TN2_2237.JPG assets3/TN2_2238.JPG assets3/TN2_2239.JPG

 新しい方法でこそないが、事前計算によって間違いのないルートがテーブルに記述されているため、リアルタイムに計算する必要はなく、テーブルの参照はプログラム負荷も軽い。すでに全計算結果が格納されているので、サーバー内で使うメモリサイズが決まっているという安定性もメリットだ。
 一方でデメリットもある。先ほど使用メモリのメリットを挙げたが、広大なマップの全ナビゲーションメッシュに対して移動を網羅したテーブルを作ると、巨大なものになるのだ。2万メッシュあるマップでそのまま現在地2万メッシュ×目的地2万メッシュの表を作ると、データ量はそれだけで1.1GBになるという。


●2:グリッドにまとめてテーブルも階層化

 ここで横山氏が行ったのは、2万あるナビゲーションメッシュを100グリッドに分割し、そのグリッドごとに内包されるナビゲーションメッシュの経路テーブルを作成すること。その上でグリッド同士の経路テーブルを作って階層化も行う。これにより容量は一気に11MBへ。

 しかしこれはこれで新たな問題がある。分割したグリッドとグリッド同士の繋がり部分を考えないといけないのだ。隣合うグリッドに向かう際に必ず通るポイントを設定することで、確かに解決はできる。しかし、これが部屋から部屋への移動なら必ず扉(隣合う部屋に行く際に必ず通るポイント)を通るのは当たり前だが、『ファイナルファンタジーXIV: 新生エオルゼア』のような開けたマップではぎこちない経路になり、そぐわない。


assets3-1/TN2_2274.JPG assets3-1/TN2_2277.JPG
assets3-1/TN2_2284.JPG assets3/TN2_2292.JPG

●3:隣接グリッドの隣接部分も内包

assets3/TN2_2306.JPG

 新たな問題を解決するために、今度はグリッド内だけでなく、隣接グリッドも考慮するようにして、その接点を“サブゴール”として設定する。
 こうすることで、必ず通るポイントを作るよりも自然な経路になるのだ。グリッドを移動したらサブゴールを再設定し、これを繰り返していくことでゴールというワケ。


assets3/TN2_2294.JPG assets3/TN2_2300.JPG
assets3/TN2_2301.JPG assets3/TN2_2302.JPG assets3/TN2_2304.JPG

●ナビゲーションメッシュ、グリッド、コンポーネント

assets3/TN2_2315.JPG

 では、階層経路テーブルはどのような構造で作られているのか? 講演では、どのように階層化したテーブルを使って経路を導き出すかが示された。大きく分けて、最小単位であるナビゲーションメッシュであるポリゴンメッシュと、それをまとめたコンポーネント、その上位のグリッドという単位を頭に入れて、下記の図をご確認頂きたい。
 


assets3/TN2_2316.JPG assets3/TN2_2317.JPG assets3/TN2_2318.JPG

▲2グリッドのマップをコンポーネントに分割する例。まず全体から繋がっているナビゲーションメッシュ同士をまとめる。次にグリッドに応じてコンポーネントを分割(続く)。

assets3/TN2_2322.JPG assets3/TN2_2324.JPG

▲さらにコンポーネント内のメッシュ同士で経路を探索してみて、別のコンポーネントを通るか通らないかで分ける。ここでは紫に塗られたコンポーネント内の移動の1メッシュが隣の緑のコンポーネント内を通った方が移動距離が短いので、新たに黄色のコンポーネントに分けられている。

assets3/TN2_2325.JPG assets3/TN2_2326.JPG assets3/TN2_2328.JPG

▲隣接経路テーブルの最小の割り方。自分のいるグリッドから周囲8グリッドまで(紫)は全ポリゴンへの移動を収める。さらに外側の12グリッド(オレンジ)はサブゴールを設定するためのもの。コンポーネントまでの移動となる。

●経路探索の例

assets3/TN2_2346.JPG assets3/TN2_2348.JPG assets3/TN2_2349.JPG

▲最初に自分のいるグリッドを中心にした最小テーブル内を見ても……もちろんゴールがない。そこで上位テーブルを見てみると、ようやく含まれていた。上位層のコンポーネントを調べて、とりあえず目標にすればいいコンポーネントが判明。

assets3/TN2_2351.JPG assets3/TN2_2352.JPG

▲上位層のテーブルに従って移動すればいいコンポーネントが3つまで決まる。

assets3/TN2_2353.JPG assets3/TN2_2354.JPG

▲3つ目は上位層での隣グリッドに入ったところ。なのでテーブルを切り替え。すると今度は紫の圏内にゴールがあった。4つ目も決まったのだが、これは下位層のテーブルの外側。

assets3/TN2_2355.JPG assets3/TN2_2356.JPG assets3/TN2_2357.JPG assets3/TN2_2358.JPG

▲というわけで一個戻って、最初のサブゴールが決定。

▲下位層のテーブルを見ることで、そこまでどういうメッシュを進めばいいかも決まる。

assets3/TN2_2359.JPG assets3/TN2_2360.JPG

▲基本的にはこれをくり返していくことで経路が決まる。

●自動生成に対応

assets3/TN2_2389.JPG

 『ファイナルファンタジーXIV: 新生エオルゼア』におけるナビゲーションメッシュの生成には、Mikko Mononen氏によるオープンソースソフトウェア“Recast Navigation”を使用しているとのこと。このパートでは、どのようにしてジャンプや落下にも対応したナビゲーションメッシュを生成しているかも解説が行われた。

 ナビゲーションメッシュと経路探索テーブルの生成にあたっては、各職からの要望を受けて、レベルエディタから実行可能に。ナビゲーションメッシュの中間データはDCCツール(デジタルコンテンツ作成ツール。この場合は大体3Dデータ作成ソフトなど)で直接調整できるようにしているという。

 ちなみに、自動生成に伴う、実際はうまく通れなかったりする部分があったりするデメリットについては、『ファイナルファンタジーXIV: 新生エオルゼア』ではコリジョン(衝突判定)を修正して対応することが多かったそう。


assets3/TN2_2365.JPG assets3/TN2_2366.JPG
assets3/TN2_2367.JPG assets3/TN2_2369.JPG
assets3/TN2_2385.JPG assets3/TN2_2386.JPG assets3/TN2_2387.JPG assets3/TN2_2388.JPG
assets3/TN2_2413.JPG assets3/TN2_2416.JPG

▲自動生成時間、データ量ともに許容範囲になっているのがよくわかる。

▲冒頭でそれっぽく示されていたワールドマップ、てっきりアーティストが作ったものかと思ったら、元はナビゲーションメッシュのデータを加工したものだとか。

assets3/TN2_2394.JPG assets3/TN2_2403.JPG assets3/TN2_2410.JPG assets3/TN2_2417.JPG

▲来年3月頃発売予定の専門書「AI Game Programing Wisdom 5」に詳細が掲載される予定とのこと。