[UE4] ナビゲーションのパフォーマンス

検証バージョン: UE4.26.0

# 結論
　ナビゲーションに関してはコンテンツに沿ったバランスの良い調整が必要です。バランスを調整するのはメモリ、パフォーマンス、クオリティ（ナビゲーションの精度）の3つについてですが、多く聞くケースとしてはどこかが極端になってしまうということです。これらに注意しながらベストエフォートして落としどころ（結局は何かを犠牲にする必要性に駆られてしまう葛藤がある）を見つけましょう。

**[影響を受ける箇所]**
・メモリ
　ナビメッシュが使用するランタイムのメモリ使用量、など

・パフォーマンス
　ナビメッシュの構築速度、ナビメッシュ構築時のヒッチ、ナビメッシュの変更点監視のパフォーマンス、パスの検索速度、など

・クオリティ
　ナビメッシュのジオメトリの滑らかさ、ナビメッシュの密度、パス検索の自然さ、など

# 覚えておきたいこと
　これらの内容はナビメッシュを制御する上でそこそこ大事なことなので、どのような関係になっているかを覚えておくと非常に便利です。
## Navmesh
**TileとMemoryの関係 (Tile Size, Tile Size UU)**
 ・タイルサイズが大きいほどパフォーマンスは良くなるがメモリが増加する
 ・タイルサイズが小さいほど更新エリアが発生しても少ない範囲の再計算で済むが初期構築コストがかかる
![2020-12-18_01h44_19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/364110/f26a1d2e-7d9e-141f-d668-abb462a4d9c0.png)

**TileとVoxelの関係 (Cell Size, Cell Height)**
　・セルサイズを大きくすることでパフォーマンスは良くなるがナビメッシュの精度が低下
　・セルサイズを小さくすることは精度は向上するがメモリやナビメッシュの構築コストが増加
![2020-12-18_01h41_14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/364110/13690f49-4839-bc24-8e1b-c916b6cab206.png)

## Navigation System
**できるだけ動的なナビメッシュの更新を避ける**
　・コンテンツによってナビメッシュが動的に変更をが発生しない場合はStaticを使う
　・ランタイム生成の設定におけるパフォーマンスは[Static]>[Dynamic Modifiers Only]>[Dynamic]の順でパフォーマンスが良い
　・動的な更新が必要な場合は、出来る限り[Dynamic Modifiers Only]を利用できないか検討する

**（もし動的な更新を利用する場合は）ナビメッシュの更新時の頻度を抑える**
　・更新機会は下がるため即時更新はしないがパフォーマンスは良い
　・Defaultでは1/60秒毎に更新のチェックを行うため、頻度が高い
![2020-12-18_01h39_34.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/364110/38b2f94e-8f93-6d06-7737-0c623133ffd0.png)

## Static Mesh
**Navmesh Dataを保有させない**
・`Has Navigation Data`を無効にすることでNavmeshの生成に必要なCollision Dataを保持しなくなり、メモリを節約できる
・`Can Ever Affect Navigaiton`を無効にすることで上記と同じ効果が得られる
・Navmeshに影響を及ぼさない場合、パス検索の迂回対象外となる (移動の障害となる可能性)ので注意

## Navigation Data
**ナビメッシュ構築に使用するジョブ数を制限する**
・ナビメッシュの更新に必要なThread数の調整を`MaxSimultaneousTileGenerationJobsCount`で設定する
・ナビメッシュを更新するために割り当てるTask Thread数を減らすことで、空いたThreadを別の処理に割り当てることができパフォーマンス向上
・トレードオフとしてジョブ数が少なくなることからナビメッシュの全ての更新に時間が掛かるようになる

# パフォーマンスの具体例
　以下の図は、巨大なシーンのナビメッシュを構築する際によくあるゲームスレッドでヒッチが発生しているような例です。
![asyncbuild-multi.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/364110/2597ea27-1f31-84e9-ed9c-446a45ee09fa.png)

　ナビメッシュの構築はレベルの開始直後に行われます。長いレベルロードがある場合は、そのレベルに加えてナビメッシュのビルドでもブロッキングが発生しているかもしれないため、単純にヒッチが発生しているといってもどこのヒッチであるかは切り分けておきましょう。

まず、ナビメッシュ構築の処理の流れについて簡単に説明しておきます。レベルのオープンが完了したらNavigationSystemはナビメッシュの構築を非同期で開始します。これが「1.Navmeshをビルドするためのタスク生成」に該当する部分です。デフォルト設定の場合、ナビゲーションシステムは出来る限り"最速"かつ"非同期"でナビメッシュを構築しようとします。非同期で構築するための処理が「2.Pool Threadでナビメッシュを生成」に該当する部分です。一番上のGame Threadでタスクを生成した後は、そのバックグラウンドの6つのPool Threadを利用してナビメッシュを生成していることが分かりますね。これがデフォルトの挙動となります。

この時に1.の赤枠の部分で、処理のスパイク（ヒッチ）がGame Threadで発生することが分かります。同時に非同期処理を開始するためのタスク生成に時間が掛かっていることが分かりますね。「ナビメッシュは非同期で構築される」ので「ヒッチが一切発生しない」という思い込みがあるとこのような落とし穴は見落としがちなので、頭の片隅にでもいれておきましょう。

この問題を簡単に対処するためには`MaxSimultaneousTileGenerationJobsCount`を小さくしてしまうのが簡単ではあるのですが、単純に生成するタスクを減らすだけでは、ナビメッシュの構築時間は逆に伸びてしまうだけです。こうした面でバランス調整が必要になってきます。例え少ないタスクで処理しても構築するタイル数が少ない場合は早く処理を終えることができるためです。関連して、RecastNavmeshのCellSizeをできるだけ大きくしておく、RegionPartitioningでWatershedを利用している場合はMonotoneにすることで早くなります（逆にこれらの設定によってナビメッシュのクオリティが低下してしまうという葛藤がまたあるわけですが）。

 あくまで上記は一例としてあげましたが、良いパフォーマンスを得るだけであればクオリティが犠牲になることがあるので、様々なバランスを鑑みながら調整をすることがベストパフォーマンスを得るための近道となります。そのためにも、どのパラメータを設定するとどのようなバランス関係が動くかを把握しておくことが重要になります。

# 補足
ナビメッシュ生成の最適化に関しては以下のドキュメントも追加されたためご覧ください。

https://docs.unrealengine.com/5.0/ja/optimizing-navigation-mesh-generation-speed-in-unreal-engine/