【UE4】Flow Field Pathで大量のエージェントを移動させる
- はじめに
- 結果
- プロジェクトはこちら
- Flow Field とは
- Flow Field の生成
- 巨大なフィールドに対応させる
- グリッドの階層構造
- HPA* アルゴリズム
- Flow Field x HPA*
- おわりに
- 参考資料
はじめに
World of War Z をプレイしていて大量のゾンビをナビゲーションする方法に興味を持ったので調べてみました。
一度のラッシュで襲ってくるゾンビはざっくり200~400体程度かと思います。それだけのゾンビがそれぞれプレイヤーに向かう経路探索をしているとは考えにくく、そもそも大量のゾンビが経路探索をしたとしても求められる経路はほとんど同じです。
一度の経路探索で数百、数千のゾンビが目標への経路を共有できればかなりの負荷を削減出来ることになります。そんな課題に有効な手段である Flow Field Pathfinding を調べて実装してみたのでプロジェクトの解説をしていきます。
結果
Flow Field Path.
— PavilionDV7 (@Dv7Pavilion) May 2, 2020
前回公開したときには上手く生成出来なかったマップでも HPA* のおかげで望ましいFlow Fieldが生成されるようになった。#UE4 #UE4Study pic.twitter.com/u2gR0DqRGh
プロジェクトはこちら
バージョン：UE4.24.3
Flow Field とは
基本的にはグリッドベースで動作するアルゴリズムであり、ゴールへと向かう正規化されたベクトルを格納したデータを生成します。これをFlow Fieldと呼びます。Flow Fieldを可視化すると目的地へ水が流れるような経路を見ることが出来ます。
Flow Fieldは一度生成すると全てのセルがゴールへと向かうベクトルを持つためAIがどのセルでスポーンしようともゴールへと移動出来ます。 グリッドベースなので複雑なレベルであればグリッドの解像度を上げることで詳細なFlow Fieldを得られ、処理負荷が気になるなら解像度を下げれば簡単に解決出来ます。Flow Fieldの詳細度と処理負荷はトレードオフの関係ですがエージェントの移動ベクトルの計算方法を工夫することで高い解像度を必要とせず滑らかな移動を確保することも出来ます。（Bilinear補間による移動ベクトルの計算）
Flow Field の生成
Flow Fieldは単純なステップで生成できます。
- 任意の解像度のグリッドを生成
- グリッドにゴールを与える
- 全てのセルにゴールまでの距離を記録（改変したダイクストラ法を利用）
- ゴールから周囲のセルを取得し最も距離が少ないセルへと向かうベクトルを作成
- ４番を全てのセルがベクトルを作成するまで繰り返す
これらの手順はソースコードの SectorFlowFieldGrid.h/cpp にて実装されています。詳細な実装箇所は以下の通りです。
- FSectorFlowFieldGrid::Initialize
- FSectorFlowFieldGrid::GenerateFlowField
- FSectorFlowFieldGrid::GenerateDijkstraGrid
- FSectorFlowFieldGrid::GenerateFlowField
巨大なフィールドに対応させる
これまでに紹介したFlow Fieldの生成方法でFlow Field Pathfindingは実装出来たことになるのですがいくつか課題があります。
- グリッドの解像度が高くなったとき（500x500や1000x1000等）は無視できない負荷が掛かる
- フィールドが大きくなるにつれ「通る必要の無いエリア」が生まれそれが大部分を占めるようになる
特に２番目の課題は厄介です。どうにかして「確実に通過するエリア」「通過する必要のないエリア」を割り出さなくてはなりません。 この課題に対しては グリッドの階層構造 と HPA*アルゴリズム を取り入れることで解決出来ます。
グリッドの階層構造
大きなグリッドを小さなグリッドに分割し１グリッドあたりの処理負荷を分散します。（100x100 を 10x10x10 に分割する）
プロジェクト中のグリッド階層構造の様子は以下の通りになります。
HPA* アルゴリズム
HPA*は https://www.researchgate.net/publication/228785110_Near_optimal_hierarchical_path-finding_HPA で登場したアルゴリズムであり正しくは Hierarchical Path-Finding A-star と呼びます。
HPA は経路探索そのものは通常のAアルゴリズムと同じですが経路探索に至るまでの準備が工夫されています。
-- ここから準備 --
- 大きなグリッドを小さなグリッドに分割（プロジェクトではセクターと呼ぶ）
- セクター間にリンクを作成する（プロジェクトではポータルと呼ぶ）
- セクター内のポータルネットワークを構築（同セクターのポータル同士で経路探索を行い通行可能かチェックする）
-- ここまで準備 --
-- ここから実行時 --
- スタートとゴールが属するセクターを割り出す
- スタートからゴールへとポータルを使った経路探索を行う
-- ここまで実行時 --
1番から3番は実行前に処理が可能ですのでグリッドやリンクデータを何らかのファイルに保存しておけば実行時には経路探索時の処理のみ行えば良いです。
上記の手順の実装箇所は以下の通りです。
- FWorldCellGrid::Initialize
- FWorldCellGrid::GenerateSectorPortal & FWorldCellGrid::GenerateSectorEdgePortal
- FSectorFlowFieldGrid::AddIntraPortal & FSectorFlowFieldGrid::IsTraversalAllowed
ポータルを生成する
ポータル生成の手順は以下の通りです。
- セクターの辺を取得
- 取得した辺と隣接するセクターの辺を取得
- 辺に障害物が無いかチェック
- 障害物があった場合、障害物が無かったセルの中心にポータルを生成
- 1から繰り返す
実装箇所は以下の通りです。
1番~3番. FWorldCellGrid::GenerateSectorPortal
4番. FWorldCellGrid::GenerateSectorEdgePortal
ポータルネットワークの構築
ポータルネットワークの構築は以下の通りです。
- セクターが持つポータルを取得
- 取り出したポータルと他のポータルとの経路探索を行う
- 経路が存在する場合、接続済みのポータルとして記録
- 経路が存在しなければそのまま
- １から繰り返す
図はネットワーク構築の様子。 1番と2番は通行可能なのでそれぞれ接続しますが1番と3番については完全に分断されており到達は不可能なため接続は行われません。
実装箇所は以下の通りです。
1番~4番. FSectorFlowFieldGrid::AddIntraPortal
2番の経路探索. FSectorFlowFieldGrid::IsTraversalAllowed
Flow Field x HPA*
Flow Fieldの生成とHPA*を組み合わせた際の最終的な手順は以下の通りです。
- 階層構造のグリッドを構築
- ポータルを生成
- ポータルネットワークの構築
- 上位層のグリッドにスタートとゴールを与える
- スタートからゴールまでに通るセクターを求める
- 求めたセクターに対しFlow Fieldを生成
HPA* アルゴリズムの項でも書きましたがポータルネットワークの構築までは前処理として事前に処理を実行して結果を記録することが出来ます。
おわりに
Flow Field と HPA* を組み合わせることで大きなフィールドにも対応でき無駄を大きく省くことが出来ました。実行時には全ての手順を処理する必要はなくいくつかの工程は前処理で省くことが可能です。 配布しているプロジェクトには実装していませんがフィールドの動的な変化についても
- 変化のあったセクターを検知
- ポータルネットワークの再構築
- Flow Fieldの再生成
という手順で実現出来るかなと思います。
プロジェクトの制約として 平面もしくは緩い起伏のある地面 での使用を考慮しているためスロープや螺旋階段といったレベルには対応していません。今後はそのような立体的な構造にも対応していきたいと思います。
参考資料
https://leifnode.com/2013/12/flow-field-pathfinding/
https://howtorts.github.io/2014/01/04/basic-flow-fields.html
