【CEDEC2017】「FINAL FANTASY XV におけるキャラクターナビゲーションパイプライン ～パス検索とステアリングとアニメーションの連携～」講演レポート

# 「FINAL FANTASY XV におけるキャラクターナビゲーションパイプライン ～パス検索とステアリングとアニメーションの連携～」講演レポート

## 概要

このセッションはCEDEC2017、8/30の11:20~12:20に行われたものです。SNS公開可能と記載されていたため、本レポートは講演での口頭説明をしていた部分を付け加えつつ、資料と合わせて見返した時、内容がすぐわかるように講演内容をまとめたものとして掲載しています。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/36899/73b31dcf-c450-e3a1-6783-e837cc143b8b.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/36899/1d5392bb-8cdf-cc83-c25e-1d424426655c.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/36899/dd8244aa-3fe0-dc87-a541-246dbe02a48b.png)

## キャラクターナビゲーションパイプライン

これは、キャラクターの移動制御において

パス検索→ステアリング→アニメーション

といった一連の処理をキャラクターナビゲーションパイプラインと呼んでいる。

この処理について現実例を交えつつ解説を進めていく。

### どうやって移動するか？

現実例：ドライブ

自分たちが車を使って移動をする場合。

1. 地図を入手して周辺環境を確認し、目的地までの最短経路を決める。
1. 経路が決まった後は、車で交通ルールに従いつつ他の車を避けながら目的地までパスに追従して移動し、目的地に向かう。
1. 車のアクセルやハンドルを使って運転するという行為自体も必要(車種によっては操縦方法が異なる)。

これをゲームに置き換えると、

1. 地図(**ナビゲーションデータ**)を入手して周辺環境を確認し、目的地までの最短経路を決める(**パス検索**)。
1. 経路が決まった後は、車で交通ルールに従いつつ他の車を避けながら(**センサーによる衝突回避**)目的地までパスに追従して移動し(**パスフォローイング**)、目的地に向かう(**ステアリング**)。
1. ステアリングから与えられた望ましい速度に応じてアニメーションを行う。このアニメーションはキャラクターによっても動かし方が違ってくる。大きいモンスターや小さいモンスターを同じようにアニメーションさせるのは容易ではない。

アニメーションはステアリングに必要なモーションモデルというものを与える。FF15ではアニメーションドリブンの実装になっている。つまり、AIが位置を決めるのではなく、アニメーションによって位置が決まる。これによって、モーションモデルがキャラクターごとに必要となる。

### ゲーム特有のプロセス

先ほどの移動制御はランタイムで処理が行われているが、ゲームの場合は開発時(事前ビルド)にも色んなことができる。

- ナビゲーションメッシュの自動生成。(FF15では毎日ナイトリービルドでナビメッシュを更新していた)
- ステアリングで使われるモーションモデルの処理。ランタイムでのモーションモデルは更新のみを行う。

## ステアリングアルゴリズムの概要

FF15のステアリングの構成は、

- 入力：各エージェントから受け取ったパスなどのデータから目的地にたどり着くまでの望ましい速度を計算する。
- 処理：主に衝突回避を行う。
- 出力：各エージェントで固有の処理が必要な場合に、ここに対応を入れる。

の３つの処理に分けられている。

これら３つの処理はモジュール性の高い設計になっているので、用途に応じて柔軟に入れ替えることができる。

例えば「入力」では、

- パスフォローイングの場合、パスから望ましい速度を計算する。
- ヒートマップの場合、ベクトル場から望ましい速度を計算する。
- ターゲットフォローイングの場合、そのまま受け渡しを行う。

### ステアリングとは？

動的な回避を行いながら目的地までたどり着く。

### アルゴリズムの種類

「RVO」と「ORCA」がゲームで一般的によく使われているアルゴリズム。

今回は「Human Like」に注目する。

### ステアリングアルゴリズムとは？

基本的にはロボットに適用するために開発されたもの。

- 衝突せず安全であることが保証される。
- 数学的な証明もある。
- 不自然にギリギリで避けてしまったり、避けようとして後退する特徴もあるので、ゲームに適していない場合もある。
- 局所解にハマることがある。

### ステアリング：HL

より人間らしい避け方を目指したアルゴリズム。

基本方針としては、その他のエージェントの速度を使って、衝突予測を行い、衝突せずにターゲットに向かって最も進める方法を選択する。

方法としては、２つある。

１つ目。所定の方向(自分を中心とした放射状)とターゲット方向に対して衝突する距離を計算する。ターゲット方向がないと、ターゲットに向かって直接進める場合でも違う方向にしか進めないので不自然な挙動となる。

この計算は、それぞれ速度を持つエージェント同士の衝突位置を求めるもの。だが、これはもっと簡略化して考えることもできる。

まず自分の半径を相手の半径に足す。これで自分を点として考えることができる。次に、相手から見た自分の相対速度を考えて、相手の方を停止した状態と仮定する。これで最終的には線と円の交差を求める問題に置き換わる。これが計算できれば、求めたい方向に対する衝突距離が求められる。

２つ目。各方向に関して衝突距離を計算し、最終的に、どの方向に進むかを選択する。基準として、ターゲットに最も近い衝突となる方向を選択する。

#### HLの特徴

【良い点】
- ORCAと比べるとより人間らしい、自然な動作になる。
- 機能の追加が容易。
- 衝突予測を行う計算の方法の数を変えることで、処理負荷を調整できる。(9方向のHLの場合、ORCAより早い)

【悪い点】
ライブラリが無いため、自ら実装しなくてはいけない。なので実装コストがかかる。

## 環境認識を利用したステアリングの改善

### 1. パスエッジを使って自由度を高める

ステアリングのステップの最初、「入力」で行なっているパスフォローイングの改善手法。

スタートからゴールまで移動するためにパス検索を行うと、最短経路の情報が得られる。ただし群衆のエージェントコントロールを考えた場合、誰もがこの最短経路に従うと渋滞が起きてしまう。

これがそもそもの問題である。

ここでパス検索で得られるもう１つの情報を使用する。それが、メッシュの境界が持つエッジの情報。これを**パスエッジ**と呼ぶ。

パスエッジの範囲での移動を許可することでエージェントは自由に動けるスペースを得られる。

ここから、パスエッジを使用した場合のパスフォローイングにおいて、各エージェントがどのように経路を決めるのかを解説する。

1. 次のエッジを見つける(まだ交差していないエッジ)。
1. 次のエッジが到達可能かチェックする(ナビメッシュレイキャスト)。
ここでもし何かしらの問題で、使おうとしているパス検索の結果が使えなくなっている場合、再度パス検索をやり直す。再検索の必要がない場合は次のステップへ進む。
1. 進むべきターゲットの位置を決めるていく。この決める手順として以下のようになる。
    1. 一定距離内の前方のエッジからターゲットの候補となるエッジを選択する。
    1. この候補のエッジを、より高い制約条件で評価する(候補の１つ手前のエッジを含むコーン内に入っているか、の判断)。コーンが交差しなかった時、次のエッジに最も近い点と、スタートから最も近い点の中間をターゲットの位置として選択する。手前のエッジを含むコーン内に入っていない場合、手前のエッジを候補に切り替えて、再度候補から１つ手前のエッジを含むコーン内に入っているか確認。

#### なぜパスエッジを使うと渋滞が起きないのか？

先ほどのターゲットの位置の決め方だと、自分の現在の位置によって、目指すターゲットの位置が変わる。これによって経路が分散され、渋滞が起きにくくなる。

### 2. ナビゲーションメッシュを使って動作を制限する

ステアリングのステップの二つ目、「処理」で行なっている衝突回避の改善手法。

HLの衝突予測にナビメッシュのレイキャストを利用して、キャラクターがナビメッシュの外に行かないようにすることができる。

この拡張はHLの衝突予測と相性がいいため、容易に実装できる。

### 3. ジャンプなどの特殊動作への対応

**多目的オフメッシュリンク**という、ポイントとポイントの接続を利用している。

これはゲームでも一般的に普及している技術で、ジャンプや飛び降りなどに使用される。

ガードレールなどの障害物を乗り越える場合は、**ナビメッシュマテリアル**というものが使われている。

スペアリングでは障害物を無視するが、ナビメッシュマテリアルはナビメッシュへの負荷情報を元に、アニメーションへのジャンプするという通知が送り、障害物飛び越えアニメーションが再生される。

## 一般的なステアリングの問題

### 1. 正確に止まれない

実際に同じ命令を出しても、アニメーションによっては止まるキーの長さは違うことがあるため、違う場所で止まってしまう。

### 2. 正確に旋回できない

体が大きいモンスターなどは、急に曲がることができない。大きく旋回して曲がることになるため、ナビゲーションメッシュの外に穴などがあると問題となる。

### 3. ターゲットの周りを旋回してしまう

大きく旋回する動きとなるモンスターはターゲットの位置にうまく辿り着けず、ずっと旋回し続ける現象が起きてしまう。

### 解決方法(モーションモデル)

上記問題点を解決するのにはいくつか方法がある。アニメーションのレギュレーションや、アニメーションの実際の位置を制御したり。

FF15では、あまり使われていない、モーションモデルの方法を使っている。

モーションモデルとは

- アニメーションの制約条件(止まるのに必要な距離や最高の減速度など)を分析すること。
- アニメーションのデータの整合性チェック(自動QA可能)

また、特徴としてキャラクター毎の設定がほとんど必要がない。ただし、メンテナンスコストが高くなる。シミュレーションのコストも少し高い。

### モーションモデルの生成プロセス

順番的には事前ビルドの段階で作られている。

#### モーションシミュレーション

テスト環境で実際にゲームを動かしてデータを記録する。

まず、命令データベースを使用。命令に沿った望ましい速度を計算する。ここで収束のチェックも行う。例えばセンサーから得た速度の数値が安定状態になったら次の命令を出して欲しいなど。センサーから得た実際の位置、実際の速度を集める用のデータのダンプも使用。データ収集後は別のプロセスでデータ分析を行う。この時、判明する範囲でエラーの報告も行うようにする。

### モーションモデルの使用例

整合性をチェックする。
→最低/最高速度を測る。

問題を解決する。
→正確に止まる
→正確に旋回する
→ターゲットの周りを旋回しない

#### 最低/最高速度を測る。

計算結果である望ましい速度と、実際の速度の測定値を比較する。

比較した結果、異なっていれば、一定速度の命令を出し、安定させるためにアニメーションを待つ。

この時、QAとして、以下の状態になっている場合にはエラーを報告するようにしている。

- 減速命令に対して加速してしまう
- ２つの有効範囲が選択可能

#### 正確に止まる

実際に出す命令としては

1. 一定速度にする。
1. 停止する。
1. 距離を評価する。

速度によって別のアニメーションクリップが割り当てられている想定。

例えば距離dで停止するようにしたい場合は、現在の速度からどの速度モデルを使用するか選択。

#### 正確に旋回する

AIとしては望ましい速度で望ましい旋回をしたいが、アニメーションによっては、その望ましい速度の状態だと大きい旋回が必要となり、オーバーシュート(行き過ぎ)距離が発生する。

これは、速度を緩やかにすると改善が可能。運転と一緒。

この場合の命令リストは以下のようになる。

1. 一定の速度Vにする。
1. 速度Vで角度a回転する。
1. オーバーシュートを評価する。

ここで鋭角な旋回をするために、パスフォローイング時に、まずターゲットを見つけ、その次のターゲットも見つけておく。そうすると最短のパスはわかる。そのパスの反対側、エッジの境界も見つけられる。反対側からパスの間はオーバーシュート距離となる。ここまで求めたら最高速度の計算もできる。これで減速が可能。

二番目の使い方は旋回スペースの確認。
現在の速度状態で、ナビゲーションメッシュのレイキャストを出す。ぶつかったレイキャストでオーバーシュート距離を計算できる。このオーバーシュート距離以上だとナビゲーションメッシュの外へ行ってしまうため、できるだけオーバーシュート距離内で旋回を行いたい。ここで、レイに対する最高速度を計算できる。

このようにすると、体が大きいモンスターは、狭い場所だと速度を落として旋回し、広い場所だと速度を落とさず旋回する自然な動きとなる。

#### ターゲットの周りを旋回しない

問題だったのは、命令が現在の速度から90度回転だった時、すぐにはその角度に曲がれない場合、ターゲットポイントに到達できず、命令が繰り返されて結果的にターゲットの周りを円状に旋回していたこと。

なので各フレームへの命令を以下とする。

1. 現在の速度に対して、90度方向に速度Vにする。
1. 円とその半径を評価する。
1. 速度から関数を抽出する。

最終的なターゲットまでのパスフォローイングとしては以下のようになる。

1. 現在の速度から旋回半径を計算する。
1. もしターゲットが半径の外側なら、特に問題ないため、そのまま進む。もしターゲットが半径の内側なら、
    1. ターゲットに接する半径を見る。
    1. この半径に対応する速度があれば減速する(FF15にはこの実装はなかった)。なければ距離が最も小さくなったところで移動を停止(こっちはある)。

## 感想

FF15での具体的なパス検索処理に関して聴くことができたのは大変勉強になりました。また、ステアリングという技術自体も今回初めて知ったため、なかなか難しくは感じましたが丁寧な説明と図によってなんとか少しだけ理解をすることができました。今後FF15を再プレイする際には仲間やモンスターたちの動きももっと観察してみようと思います。