お知らせ（2020-12-19）

Unreal Engine 4 (UE4) Advent Calendar 2020 にて「Influence Map 再び」と題してバージョンアップしたInfluence Mapについての記事を書きました。

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

Influence Mapとは？

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

以下の３つはThe Mechanics of Influence Mapping: Representation, Algorithm & Parametersで紹介されているInfluence Mapが提供する代表的な情報です。

世界の状況 : 世界が現在どのような状況にあるか、要約した情報を表現出来ます。「どの国がどれだけの領土を保持しているのか？」「どのあたりに、どれくらいの数の敵がいるのか？」「そのエリアにいる敵の戦力は他の敵戦力と比べて強い？弱い？」

過去から現在 : Influence Mapには時間による影響の減衰も表現出来ます。分かりやすい例えだと「残り香」「足跡」等でしょうか。 「追いかけるべき敵はこの道を通った。そして向こうへ移動した」「足跡がまだ新しい...敵が近いかもしれない...」

未来の予測 : 敵の過去から現在までの影響力の移動方向を見れば自ずと数秒後にはどの位置に敵が来るかを予測できます。リアル系のFPSにある偏差射撃などが良い例です。

もっと詳しく知りたい方は以下のページを見てみてください。
The Mechanics of Influence Mapping: Representation, Algorithm & Parameters
ゲームAI -基礎編- 『知識表現と影響マップ』

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でも問題なく動作しました！）

実行すれば2つのAIが動き回ります。

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

注意点

OneDriveにアップする際に容量削減のためIntermadiateフォルダとSavedフォルダを削除したのですが、その影響でEQSの中身が見れないようになってしまいました。申し訳ございません。
直し方はEditor Preference - Experimental - AIにあるEnvironment Querying Systemのチェックを入れてください。

このプロジェクトではNavModifierを動的に生成しているためNavigation MeshのRuntime GenerationをONにしています。

プロジェクトの中身

このプロジェクトを作るにあたって重要なアセットを紹介していきます。

InfluenceEnvQuery

このEQSはプロジェクトの肝であるInfluence Map（このプロジェクトでは安全度）を表現するためのものです。

Distance: to EQC_GoldActors

EQSアイテムから各金玉までの距離をスコアリングするテストです。
EQSアイテムから金玉までの距離が近いほど安全度が高く、遠いほど安全度が低くなります。
Distance: to EQC_GoldActorsのみを実行してみると以下のようになります。

わかりづらいですが、金玉の下にあるEQSアイテムは緑色をしています。つまり最も安全度が高い位置になります。

次にDistance: to EQC_GoldActorsの詳細設定をお見せします。

赤枠は注目して欲しい変更点です。
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アイテムで、小さいスコアと大きいスコア、または平均のスコアのどちらをスコアとして適用するか？というのを決めるところだと思います。

例えば以下の緑の円と紫の縁のようにスコアリングする範囲が重なってしまう場面があるとします。

この時重なっている部分のEQSアイテムのスコアは

図のように2つのスコアが存在することになります。
このような場合にMultiple Context Score Opで小さい方の値をスコアとするか大きい方をスコアとするか、また平均を求めたスコアにするかを決めることが出来ます。

Distance: to EQC_Pursuer

このテストはEQSアイテムから追跡者までの距離に応じてスコアリングするものです。
追跡者までの距離が近いほど安全度が低く、遠いほど安全度が高いというものになっています。

詳細設定に関してはDistance: to EQC_GoldActorsよりも単純ですね。
Clampingでスコアリング範囲を設定しているだけです。

Trace: to EQC_Pursuer on Visibility

このテストはC_Pursuerから視線が通るEQSアイテムをスコアリングします。
視線が通れば1.0、通らなければ0.0がスコアとして保存されます。この時C_Pursuerの頭の向きや体の向きは考慮されません。

詳細設定は特に変更していません。Context以外はデフォルトのままです。

Dot 2D:[EQC_Pursuer rotation] and [Item - EQC_Pursuer]

このテストに関しては少し複雑なので今回使用している設定にもとづいて説明をします。
Dotテストは文字通り内積（ドット積）を用いてスコアリングします。Dotですから計算には２つのベクトルが必要となります。それが下の図にあるLineAとLineBです。

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であれば全く違う（完全に逆）となります。

それぞれのテスト結果を合成する

最終的なInfluence Mapは上記で挙げたテスト結果を合成することで出力されます。
テスト結果を合成する時、各テストの係数を設定することでどのテスト結果を重要視するかを設定出来ます。

赤枠で囲っている部分が係数です。この値は詳細設定のScoring Factorで設定できます。

今回の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の経路探索に大きな影響を与える役割を担っています。

NavModifierコンポーネントの詳細は以下のようになっており

Area Classには新しく作成したNavArea_Influenceが設定されています。
NavArea_Influenceの移動コストはこのように

かなり大きい値を設定しています。

NavQueryFilter_Influence

NavQueryFilterはあまり使われない機能だと思いますが、今回のプロジェクトではとても良い働きをしてくれます。
この機能は文字通りナビゲーションをフィルタリングします。Xアクタはとても低いコストで通過出来るが、Yアクタが通過するには非常に高いコストがかかるというような使い方です。

上の図は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で使用しています。

追跡者の移動処理にAI Move Toでは無くMove to Actorを使用しているのは、Navigation Query Filterを使うためです。
NavQueryFilter_Influenceを経路探索の際に用いることで追跡者はA_NavModifierが持つスコアをNavQueryFilter_influenceのスコアで上書きし、実質A_NavModifierの影響を無効化しています。

FPSを稼ぐ工夫

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

Influence Mapの密度の調整

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

ダウンロードしたプロジェクトではPathingGrid Generatorの間隔は200.0です。

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

間隔200.0	間隔100.0

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

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

間隔200.0	間隔100.0

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

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

Influence Mapの更新間隔

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

そこで自分はA_InfluenceMapGeneratorの更新間隔（Tick Interval）を0.0（毎フレーム）から1.0（1秒毎に更新）に変更しました。

この変更により処理負荷を大きく下げることが出来ました。一つ上の項目で説明した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を非常に詳しく説明してくれているため、より理解しやすくなると思います。是非参照してみてください。

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

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