黒夢画像倉庫

いろんな事書いてます

スポンサーサイト

Posted by くろむ on

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[SQEXOC 2012]FFXIVで使われているAI技術~敵NPCはどうやって経路を探索しているのか について明らかになりました

Posted by くろむ on   0 comments   0 trackback

以下転載です




経路テーブルを階層化して軽量化を図る

 一昔前のゲームでは,敵NPCが障害物に阻まれて身動きが取れなくなったりすることが普通に見られたものだが,最近はそういうことはあまりなくなってきている。その背景には敵NPCを制御しているAIプログラムの進化がある。
 今回のセッションのテーマになっているのは,新生FFXIVにおいて敵NPCがマップ上を効率的に動くために,どのようなアルゴリズムを採用しているのか,という話である。確かに,広いマップや複雑な地形の上で目的の場所にAIがたどり着くのは容易なことではなさそうだ。

 新生FFXIVにおけるAI処理の難しさについて,横山氏はまず「非常に敵NPCが多いこと」を挙げる。マップあたり1000体ほどの敵NPCが動き回っているといい,確かに個々に移動経路を計算しているとその負荷は相当なものになりそうではある。
 横山氏は,もう一つ「MMORPGでは,“プレイヤーの近くにきたときだけ敵NPCを動かす”手法が取れない」という点も挙げていた。FPSのキャンペーンなどではプレイヤーが敵NPCがいるエリアに入ったことをトリガーにして敵NPCが動き出すという方法が用いられるが,大勢のプレイヤーがオンラインで接続しているMMORPGだと,当然ながらこのような方法は取れないわけだ。


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





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

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

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


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


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

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






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

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

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

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


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

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

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

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

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

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


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

Post comment

管理者にだけ表示を許可する

Trackback

trackbackURL:http://basket193.blog.fc2.com/tb.php/1071-d97ac856
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。