【UE4】EQSを使ってInfluence Mapを作った

#お知らせ（2020-12-19）
Unreal Engine 4 (UE4) Advent Calendar 2020 にて「Influence Map 再び」と題してバージョンアップしたInfluence Mapについての記事を書きました。

[【UE4】Influence Map 再び～プロジェクト編～](https://paviliondv7.hatenablog.com/entry/2020/12/16/000000)

[【UE4】Influence Map 再び～プログラム編～](https://paviliondv7.hatenablog.com/entry/2020/12/16/000140)

UE C++を用いたInfluence Mapシステムを解説する内容なので今記事と比べるとハードなものとなっていますが、Influence Mapの威力をより強く感じることが出来る内容になっていると思うので、興味のある方は是非覗いてみてください。

#Influence Mapとは？
日本語では影響マップとも呼ばれ、AIの意思決定に用いる知識表現の一つです。
ゲーム世界をグリッド（格子）やウェイポイント等で分割し、それぞれのセルやノードに影響力と呼ばれる数値を埋め込むことでAIに対し様々な情報を与える事ができます。

以下の３つは[The Mechanics of Influence Mapping: Representation, Algorithm & Parameters](http://aigamedev.com/open/tutorial/influence-map-mechanics/#Parameters)で紹介されているInfluence Mapが提供する代表的な情報です。
>- **世界の状況** : 世界が現在どのような状況にあるか、要約した情報を表現出来ます。*「どの国がどれだけの領土を保持しているのか？」「どのあたりに、どれくらいの数の敵がいるのか？」「そのエリアにいる敵の戦力は他の敵戦力と比べて強い？弱い？」*
- **過去から現在** : Influence Mapには時間による影響の減衰も表現出来ます。分かりやすい例えだと**「残り香」「足跡」等**でしょうか。 *「追いかけるべき敵はこの道を通った。そして向こうへ移動した」「足跡がまだ新しい...敵が近いかもしれない...」*
- **未来の予測** : 敵の過去から現在までの影響力の移動方向を見れば自ずと数秒後にはどの位置に敵が来るかを予測できます。リアル系のFPSにある偏差射撃などが良い例です。

もっと詳しく知りたい方は以下のページを見てみてください。
[The Mechanics of Influence Mapping: Representation, Algorithm & Parameters](http://aigamedev.com/open/tutorial/influence-map-mechanics/#Parameters)
[ゲームAI -基礎編- 『知識表現と影響マップ』](http://tech.cygames.co.jp/archives/2272/)

#UE4でInfluence Mapをどうやって表現するか
EQSを使いましょう！あれは非常に良いものです。
ネット上で見られるInfluence Mapのデモは殆どがグリッド状に空間を分割して各グリッドに対し影響力を保持させています。
EQSならばグリッド状にアイテムを生成することの出来る**Simple Grid Generator**、**Pathing Grid Generator**とおあつらえ向きの機能があり、さらにアイテムから指定したアクタや位置までの距離をスコアリング出来る**Distance Test**等も有ります。


#プロジェクトはこちらから！
OneDriveにプロジェクトをアップしています。(解凍には7-zipを使用してください）
使用したバージョンはUE4.15.2です。~~（これを書いている間に4.16がリリースされたので4.16で動かした場合、何かしら不具合が起きる可能性があります）~~ （4.16でも問題なく動作しました！）

https://1drv.ms/u/s!Au-8FqgREBKZhR6gpC3vFvSJ76qW

実行すれば2つのAIが動き回ります。
![InfluenceMapTest.gif](https://qiita-image-store.s3.amazonaws.com/0/104467/ab569081-100c-e0d1-df47-9ad697afd36f.gif)

GIFではかなり小さいですが赤と青のキャラクタがいます。
青はフィールドにある金色の球（別名：金玉）を集め、赤は青を追跡し続けます。
これも見えにくいのですが、床に緑やオレンジ、赤の球体のようなものがあります。これはInfluence Mapを可視化したもので、緑色は安全度が高く、赤色は安全度が低い、というのを表しています。
黒枠はNavMeshModifierComponentを持つアクタを可視化したものです。黒枠のあるエリアは通常のナビゲーションエリアに比べて遥かに高いコストを持ちます。
この黒枠があることによって青は赤を迂回する（不利な場所へは可能な限り通過しない）ような経路を取らせる事が出来ます。

#注意点
OneDriveにアップする際に容量削減のためIntermadiateフォルダとSavedフォルダを削除したのですが、その影響でEQSの中身が見れないようになってしまいました。申し訳ございません。
直し方は**Editor Preference - Experimental - AI**にある**Environment Querying System**のチェックを入れてください。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/348bb12b-340d-9fcc-5d39-feadbcafa33c.png" width = 80%>

このプロジェクトではNavModifierを動的に生成しているため**Navigation Mesh**の**Runtime GenerationをON**にしています。
![2017-06-01_19h40_34.png](https://qiita-image-store.s3.amazonaws.com/0/104467/125db1ff-f5fb-0664-c503-a9187788e8dd.png)



#プロジェクトの中身
このプロジェクトを作るにあたって重要なアセットを紹介していきます。
##InfluenceEnvQuery
このEQSはプロジェクトの肝であるInfluence Map（このプロジェクトでは安全度）を表現するためのものです。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/e56b27f2-b678-576b-77cf-29e73d38da41.png" width = 50%>

###Distance: to EQC_GoldActors
EQSアイテムから各金玉までの距離をスコアリングするテストです。
EQSアイテムから金玉までの距離が**近いほど安全度が高く、遠いほど安全度が低く**なります。
Distance: to EQC_GoldActorsのみを実行してみると以下のようになります。
<img src = "https://qiita-image-store.s3.amazonaws.com/0/104467/db7c127c-41e5-22ba-45ba-33c5db851c86.png" width = 50%>
わかりづらいですが、金玉の下にあるEQSアイテムは緑色をしています。つまり最も安全度が高い位置になります。


次にDistance: to EQC_GoldActorsの詳細設定をお見せします。
<img src = "https://qiita-image-store.s3.amazonaws.com/0/104467/7cebf93d-3488-21b0-3938-0dd49c2c41df.png" width = 50%>
赤枠は注目して欲しい変更点です。
**Clamping**にて**MinとMax**に値を設定しています。これはDistanceテストの実行時に**スコアリングする距離（範囲）を設定する**ものです。
**Score Clamp Min未満の値**は強制的に**0.0**になり、その逆である**Score Clamp Maxより大きい値**は強制的に**1.0**になります。
詳細設定ではMinに50.0を、Maxに100.0を設定していますので、金玉からEQSアイテムまでの**距離が50.0未満であればスコアを0.0**に、**100.0より大きければスコアを1.0**にしています。ですが、このままだとスコアが0.0の位置は金玉に近い距離にあるにも関わらず安全度が低いと判断されてしまいます。
この問題はスコアの**結果を反転**させることで解決します。その反転している部分が**Scoring Equation**です。デフォルトでは**Linear**となっているところを**Inverse Linear**としています。


**Multiple Context Score Op**では**Min Score**に変更しています。デフォルトでは**Average Score**です。何度か実験して見たところ、恐らく**スコアが重なり合うEQSアイテムで、小さいスコアと大きいスコア、または平均のスコアのどちらをスコアとして適用するか？**というのを決めるところだと思います。


例えば以下の緑の円と紫の縁のようにスコアリングする範囲が重なってしまう場面があるとします。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/a3f3bb81-1d78-cb2f-4a36-223f4260f7ab.png" width=50%>

この時重なっている部分のEQSアイテムのスコアは
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/4385b0e8-061e-757c-da73-425df15b4db7.png" width=50%>
図のように2つのスコアが存在することになります。
このような場合にMultiple Context Score Opで小さい方の値をスコアとするか大きい方をスコアとするか、また平均を求めたスコアにするかを決めることが出来ます。

###Distance: to EQC_Pursuer
このテストはEQSアイテムから追跡者までの距離に応じてスコアリングするものです。
追跡者までの距離が**近いほど安全度が低く、遠いほど安全度が高い**というものになっています。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/88eae2d1-2900-8c94-7b96-cfb019afb1a5.png" width=50%>
詳細設定に関してはDistance: to EQC_GoldActorsよりも単純ですね。
Clampingでスコアリング範囲を設定しているだけです。

###Trace: to EQC_Pursuer on Visibility
このテストはC_Pursuerから視線が通るEQSアイテムをスコアリングします。
視線が通れば1.0、通らなければ0.0がスコアとして保存されます。この時C_Pursuerの頭の向きや体の向きは考慮されません。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/d44373ef-5afe-17e4-df84-1502664a442d.png" width=50%>
詳細設定は特に変更していません。Context以外はデフォルトのままです。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/c504d4fa-8372-14a1-94da-0f754f33d781.png" width=50%>


###Dot 2D:[EQC_Pursuer rotation] and [Item - EQC_Pursuer]
このテストに関しては少し複雑なので今回使用している設定にもとづいて説明をします。
Dotテストは文字通り内積（ドット積）を用いてスコアリングします。Dotですから計算には**２つのベクトルが必要**となります。それが下の図にある**LineAとLineB**です。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/bc869e3a-24a6-f6e3-c10c-04127bcfee5f.png" width=50%>
**LineAではModeをRotation**としています。RotationはC_Pursuerから取得します。すなわち**EQC_Pursuerの方向ベクトル**を取得しています。
**LineBでは2つのContextの位置**から向きを求めます。Line FromからToにかけての向きを取得するので、このテストでは**各EQSアイテムからC_Pursuerへの向き**を取得しています。
DotテストのスコアはLine AベクトルとLine Bベクトルが**どれほど似ているか**を表します。1.0であれば**完全に同じ**で0.0であれば**全く違う（完全に逆）**となります。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/a9cf42fb-d3ef-b4ab-d9b6-83aeb1e688f6.png" width=50%>


###それぞれのテスト結果を合成する
最終的なInfluence Mapは上記で挙げたテスト結果を合成することで出力されます。
テスト結果を合成する時、各テストの**係数を設定**することで**どのテスト結果を重要視するか**を設定出来ます。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/ce183add-d085-71b1-508d-eeea1239d834.png" width=50%>
赤枠で囲っている部分が係数です。この値は詳細設定の**Scoring Factor**で設定できます。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/2b30bd70-82c8-ad2d-987f-e1bbcd1c1678.png" width=50%>
今回のEQSでは**Distance: to EQC_GoldActors**の係数が1.5に設定されており、それ以外はデフォルトの1.0のままです。つまり、収集アイテムがどれほど安全であるかを重要視しています。
Scoring Factorの値を弄ることでInfluence Mapの結果を大きく変化させることが出来ます。例えばAIキャラクター分のEQSを用意し、各EQSの各テストのScoring Factorをそれぞれ調整することでAIキャラクターはそれぞれ異なる動きをするでしょう。つまりは**AIに個性を与えることが出来る**ということです。


##A_InfluenceMapGenerator
このアクターはEQSを実行し続け、Influence Mapの更新とAIの経路探索に影響を与えるNav_Modifierを生成しています。
Event Graphにコメントを載せているので見ていただけると何をしているかはすぐに理解出来ると思います。
Event Tickノードにコメントで**Tick Intervalの値を0.0から1.0に変更**と書きましたが、この理由については後ほど説明します。


##A_NavModifier : NavArea_Influence
A_NavModifierは**NavModifierコンポーネント**を持つアクタです。
このアクタはInfluence Mapのスコアがしきい値よりも小さい場合に生成され、AIの経路探索に大きな影響を与える役割を担っています。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/dc1b8c84-d6c2-9eb0-ea33-9f39c2995207.png" width=50%>
NavModifierコンポーネントの詳細は以下のようになっており
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/cad87cd8-6ccf-d725-9e74-f800972dd5c4.png" width=50%>
**Area Class**には新しく作成した**NavArea_Influence**が設定されています。
NavArea_Influenceの移動コストはこのように
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/b234ed7c-0271-89ce-49ec-5e769028ded3.png" width=50%>
かなり大きい値を設定しています。


##NavQueryFilter_Influence
NavQueryFilterはあまり使われない機能だと思いますが、今回のプロジェクトではとても良い働きをしてくれます。
この機能は文字通りナビゲーションをフィルタリングします。**Xアクタはとても低いコストで通過出来るが、Yアクタが通過するには非常に高いコストがかかる**というような使い方です。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/7bdebe84-ee02-ba27-43f6-43432c3dd011.png" width=50%>
上の図はNavQueryFilter_Influenceの設定です。
Area ClassにはNavArea_Influenceが設定されています。NavArea_Influenceの項目にある図の通りNavArea_influenceのコストは10000.0という非常に高いコストを設定しています。
しかし、Area Classの下にある**Travel Cost Override**に**1.0**という低い値を設定していますが、これはOverrideという名前が付いている通りArea Classに指定した**NavAreaのコストを上書き**出来ます。
NavQueryFilter_Influenceですが、これはAIC_Pursuerで使用しています。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/77553124-a716-f6b1-fb3a-01d3d6c9899e.png" width=50%>
追跡者の移動処理に**AI Move To**では無く**Move to Actor**を使用しているのは、Navigation Query Filterを使うためです。
NavQueryFilter_Influenceを経路探索の際に用いることで追跡者はA_NavModifierが持つスコアをNavQueryFilter_influenceのスコアで上書きし、実質A_NavModifierの影響を無効化しています。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/14d849c2-3c84-fc97-f569-7b25ebd70f49.png" width=50%>


#FPSを稼ぐ工夫
このプロジェクトをテストで作成したときは常時30FPS未満しか出ていませんでした。
テストと言えど、このFPSではあまりにもひどいということで物凄く簡易ではありますがFPSを稼ぐために自分がした工夫をまとめます。

##Influence Mapの密度の調整
結論を言えば密度が高いほど処理負荷は高く、低ければ処理負荷も低くなるので皆さんそれぞれでバランスの良い数値を見つけましょうという話です。

ダウンロードしたプロジェクトではPathingGrid Generatorの間隔は200.0です。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/5bd6dce2-3aec-545a-54c9-9dfe9eaba665.png" width=50%>


デフォルトでの間隔は100.0となっており、200.0の場合との差は以下のようになります。

|       間隔200.0       |       間隔100.0       |
|:-----------------:|:------------------:|
| ![2017-05-31_20h17_59.png](https://qiita-image-store.s3.amazonaws.com/0/104467/4a54f363-0153-df43-b276-9422644f045e.png)             |              ![2017-05-31_20h18_15.png](https://qiita-image-store.s3.amazonaws.com/0/104467/f8b44b0d-da69-eb20-3d91-d1423e30b941.png)|        


当然ですが100.0に比べて200.0の方が密度は低いです。
では、この密度の差とはどういったものでしょうか？
それは**地形に対する情報の精度の差**と言えます。

先程の例をステージを替えて載せます。

|       間隔200.0       |       間隔100.0       |
|:-----------------:|:------------------:|
| ![2017-05-31_20h41_16.png](https://qiita-image-store.s3.amazonaws.com/0/104467/d4d2617c-d388-1ba7-d0d9-9c0613ddbe2f.png) | ![2017-05-31_20h40_38.png](https://qiita-image-store.s3.amazonaws.com/0/104467/fa7a2411-7361-b3dc-ed4d-d892f4feab36.png) |

各図の右下に赤枠で囲っている部分（階段）に大きく差が見られます。
間隔100.0では階段に沿ってEQSアイテムが配置されていますが、間隔200.0では配置されていません。これが**密度の差**です。

密度はステージの複雑さや処理負荷によって皆さん自身でしっかりと調整する必要があります。


##Influence Mapの更新間隔
密度によって処理負荷も変化しますが、それ以上に致命的な負荷になる部分は更新部分だと思います。
このプロジェクトで一番負荷が高いところは更新部分でした。
Influence Mapを更新しているアクタは**A_InfluenceMapGenerator**です。
EQSの実行だけでなくデバッグ表示やNavModifierアクタを生成して破壊を繰り返しているため、これを毎フレーム実行すればもうガックガクです。ひどいです。

そこで自分はA_InfluenceMapGeneratorの**更新間隔（Tick Interval）**を0.0（毎フレーム）から1.0（1秒毎に更新）に変更しました。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/5e6a88a1-8ec0-4d51-fad3-1faafa88b770.png" width=50%>
この変更により処理負荷を大きく下げることが出来ました。一つ上の項目で説明したInfluence Mapの密度も同時に調整することで、とりあえず120FPSは確保できました。

ではこの更新間隔がInfluence Mapの何に関わるのか？
それは**情報の鮮度**です。

この情報の鮮度が重要視されるのは**ゲームスピード**だと思います。
極端な例えかもしれませんがターン制ストラテジーとFPSを比べてみると分かりやすいと思います。
ターン制ストラテジーは文字通りターン制なのでユニットの行動が終えた後にInfluence Mapを更新すれば十分にAIが必要としてる情報の鮮度は確保出来ています。プレイヤーのユニットが行動している間はNPCのユニットを動かすことは出来ないため、毎フレーム更新したとしてもNPCのユニットがInfluence Mapを参照するタイミングはプレイヤーのユニットが行動を終えた後で十分なので無駄と言えます。
しかしFPSはターン制ではなくプレイヤーが動いている間もNPCは動くことが可能というリアルタイムなものなので数秒の差でNPCが殺される原因にもなり得ます。Influence Mapの更新は今回のように1.0秒や0.5秒ごと、もしくはそれ以下の更新間隔を設定する必要があるかもしれません。

今回のプロジェクトにおいては追跡者の移動スピードは逃走者の半分です。そこまでゲームスピードが速い訳ではないためA_InfluenceMapGeneratorの更新間隔は1.0秒としました。

#おわりに
Influence Mapは結構面白いテクニックです。収集アイテムに向かって最短経路で移動だけというのは味気ないものですが、Influence Map一つでいい感じのランダム性が加わりプレイヤーに予測されづらい動きが出来るので知っていて損はないものだと思います。

最初の項目に貼ったリンクはInfluence Mapを非常に詳しく説明してくれているため、より理解しやすくなると思います。是非参照してみてください。

では、以上となります。お疲れ様でした。