2012年11月23日と24日、スクウェア・エニックスが東京都のベルサール神田で公開技術カンファレンス“スクウェア・エニックスオープンカンファレンス2012”を開催した。
その中から本稿では、横山貴規氏とFabien Gravot氏による“サーバーサイド経路探索システム”についての講演の内容をお届けする。
本講演で扱われたのは、『ファイナルファンタジーXIV: 新生エオルゼア』のモンスターやNPCの経路探索システム“HiNT（Hierarchical Neighborhood lookup Table）”について。
あるキャラクターがA地点からB地点へと移動していく場合、2点間を結んだ直線を歩けるとは限らない。当然マップ上には通れない部分やらがあるわけで、そこを避けてぐるっと周って行ったり、遠回りな方向がむしろ近道だったりするわけである。
『ファイナルファンタジーXIV: 新生エオルゼア』では、この“AIキャラクターがどこをどう歩いていけばいいのか”という経路探索のシステムをサーバー側で行なっているのだが、いくつか必要な要件がある。
まずは、1マップで非常にたくさんの敵が同時に動くということ。オフラインのゲームではないので、プレイヤーの周囲でしか動かないといった軽量化は使えない。
そしてマップの大きさと複雑さ。マップは最大2キロ四方あり、種類も多い。各マップへの対応を自動的に実行できないといつまでたっても終わらない。さらにはジャンプして飛び上がったり落下したりといったアクションもあり、これらに対応しなければならない。
『ファイナルファンタジーXIV: 新生エオルゼア』の経路探索システムは、こうした要件を満たした上で、経路探索に使うサーバーの処理コストをできるだけ抑える必要があるのだ。
1:ナビゲーションメッシュに対して経路テーブルを作る
経路探索システムを手掛けた横山氏とGravot氏が負荷を減らすために選択したのは、ナビゲーションメッシュに対して経路テーブルを事前の自動計算で用意するという方法。ナビゲーションメッシュというのは、移動可能な場所をポリゴンメッシュで示したものだ。
経路テーブルは、例えば現在地点とゴールの2点を指定すると、事前計算によってわかっている“まず通るべき場所”を教えてくれる一種の表と考えてもらっていい。地点Aから地点Fに行く際にA→S→D→Fが最適なルートであれば、AとFを元にテーブルを参照すると、まずSと書いてあり、次にSとFでテーブルを見るとDと書いてある……という寸法。
新しい方法でこそないが、事前計算によって間違いのないルートがテーブルに記述されているため、リアルタイムに計算する必要はなく、テーブルの参照はプログラム負荷も軽い。すでに全計算結果が格納されているので、サーバー内で使うメモリサイズが決まっているという安定性もメリットだ。
一方でデメリットもある。先ほど使用メモリのメリットを挙げたが、広大なマップの全ナビゲーションメッシュに対して移動を網羅したテーブルを作ると、巨大なものになるのだ。2万メッシュあるマップでそのまま現在地2万メッシュ×目的地2万メッシュの表を作ると、データ量はそれだけで1.1GBになるという。
2:グリッドにまとめてテーブルも階層化
ここで横山氏が行ったのは、2万あるナビゲーションメッシュを100グリッドに分割し、そのグリッドごとに内包されるナビゲーションメッシュの経路テーブルを作成すること。その上でグリッド同士の経路テーブルを作って階層化も行う。これにより容量は一気に11MBへ。
しかしこれはこれで新たな問題がある。分割したグリッドとグリッド同士の繋がり部分を考えないといけないのだ。隣合うグリッドに向かう際に必ず通るポイントを設定することで、確かに解決はできる。しかし、これが部屋から部屋への移動なら必ず扉（隣合う部屋に行く際に必ず通るポイント）を通るのは当たり前だが、『ファイナルファンタジーXIV: 新生エオルゼア』のような開けたマップではぎこちない経路になり、そぐわない。
3:隣接グリッドの隣接部分も内包
新たな問題を解決するために、今度はグリッド内だけでなく、隣接グリッドも考慮するようにして、その接点を“サブゴール”として設定する。
こうすることで、必ず通るポイントを作るよりも自然な経路になるのだ。グリッドを移動したらサブゴールを再設定し、これを繰り返していくことでゴールというワケ。
ナビゲーションメッシュ、グリッド、コンポーネント
では、階層経路テーブルはどのような構造で作られているのか？ 講演では、どのように階層化したテーブルを使って経路を導き出すかが示された。大きく分けて、最小単位であるナビゲーションメッシュであるポリゴンメッシュと、それをまとめたコンポーネント、その上位のグリッドという単位を頭に入れて、下記の図をご確認頂きたい。
経路探索の例
自動生成に対応
『ファイナルファンタジーXIV: 新生エオルゼア』におけるナビゲーションメッシュの生成には、Mikko Mononen氏によるオープンソースソフトウェア“Recast Navigation”を使用しているとのこと。このパートでは、どのようにしてジャンプや落下にも対応したナビゲーションメッシュを生成しているかも解説が行われた。
ナビゲーションメッシュと経路探索テーブルの生成にあたっては、各職からの要望を受けて、レベルエディタから実行可能に。ナビゲーションメッシュの中間データはDCCツール（デジタルコンテンツ作成ツール。この場合は大体3Dデータ作成ソフトなど）で直接調整できるようにしているという。
ちなみに、自動生成に伴う、実際はうまく通れなかったりする部分があったりするデメリットについては、『ファイナルファンタジーXIV: 新生エオルゼア』ではコリジョン（衝突判定）を修正して対応することが多かったそう。
