はじめに

Unreal Engine (UE) Advent Calendar 2023の記事です。

過去、書いた記事で紹介したREエンジンの講演に「迂回する経路を取るためにWaypointで大まかな経路を探索し、NavMeshで詳細な経路を探索する」方法が紹介されていた。迂回する経路を取るための手法として非常に実装しやすい内容だったのでUnreal Engineで実験的に実装してみた。

REエンジンの講演ビデオ

RE:2023 ナビゲーションAIシステム概要とタイトル活用事例 - YouTube

迂回する経路の箇所はこちら

過去に書いた記事

【Unreal Engine】ナビメッシュのランタイム生成のコストを抑える実験 - PavilionDV7の雑多なやつ

動作の様子

youtu.be

プロジェクトはこちら

1drv.ms

プロジェクトの紹介

プロジェクトを開くと色々セットアップされたマップが開く。この状態で実行すると、左下に見える「WALKER」から中央にある「TARGET」に向かって移動を開始する。

レベルに配置されている黒や白の球体はウェイポイントを表している。このウェイポイントは交差点となる地点に配置している。画像右上には少し複雑な道に見えるが、実際は１本道なのでウェイポイントは配置されない。

実行したときに画面に色々なデバッグ表示が現れる。

赤の球体：今回の実験で得られた経路を表示
緑の球体：標準機能であるFind Path to Actor Synchronouslyノードを利用して得られた経路を表示
青のライン：各ウェイポイントがどのウェイポイントと接続しているかを表す

標準の経路探索を使った経路よりも実験で得られた経路のほうは大きく遠回りするものであることがわかる。

TARGETの右下と左にあるウェイポイントが黒になっているが、これは「死んでいるウェイポイント」を表している。死んでいるウェイポイントは他のウェイポイントとの接続が切れているとみなされ経路探索では無視される。

ウェイポイントの死んでいる/生きているのフラグは次の画像のように公開されたBoolean型パラメータの「Active」でスイッチできる。チェックが外れていればそのノードは死んでいるウェイポイントということになる。

TARGETの左にあるウェイポイントを「生きている」にスイッチすると、経路探索の結果は次のように変化する。

アセットの紹介

注意：ウェイポイントとノード

今回の記事やプロジェクト中ではウェイポイントとノードという単語が混ざって使われてしまっているが、ここではウェイポイントもノードも経路上の地点という意味で使用している。

実際のところ「ノード」はグラフ理論で用いられる単語で「頂点・節点」を表す。この場合、ノードには人・モノ・行動といった様々な情報を割り当てることができる。

https://algo-method.com/descriptions/105

グラフ理論と経路探索するアルゴリズムの紹介｜Tajima Robotics

それに対し「ウェイポイント」は「座標」を表すもので緯度・経度・高度の組の情報が割り当てられる。

ウェイポイント - Wikipedia

BP_Waypoint

BP_Waypointはウェイポイントを表すアクターで生きているか死んでいるかを制御するBoolean型の変数と他ウェイポイントの接続を示す隣接リストを持つ。

隣接リストへの他ウェイポイントの追加は手作業であることに注意。

BP_PathFinder

レベル上に配置され、経路探索を実行するアクターはこのアクターへの参照を取得して経路探索実行を命令する。

外部のアクターは「FindPath関数」を呼び出して経路を得ることができる。FindPath関数では受け取ったスタート位置とゴール位置に最も近いウェイポイントを検索し、スタート・ゴール間の経路探索を実行する。得られたウェイポイントの経路から更にナビメッシュを用いた経路探索を実行し、最終的な経路情報を出力する。

「FindPath_Internal関数」は経路探索アルゴリズムが実装されている。ここでの処理の流れは次に紹介するページを副読本として並列して読みながら見ていけば理解しやすいかもしれない。

A* - Wikipedia

その６ A*アルゴリズム

ちなみにブループリントでの実装はEpic Developer Communityに投稿されていたものを丸コピしたもの。一部、ウェイポイントアクターが持つフラグに対応させるためにノードを追加した。

Simple A* (A-Star) Navigation - Blueprint Implementation | Unreal engine Code Snippet

「Construct Path Points関数」ではウェイポイントの配列に対しナビメッシュを用いた経路探索を実行し、より詳細な経路を取得してVector型の配列として返す。

やることは色々あります...

この内容をもっと実用的にするならやらなければいけないことがいくつかある。

ウェイポイント同士の接続作業をもっと簡単にする
- ウェイポイントを複製すると自動で接続リストに加える
- ウェイポイント同士を選択してコマンドを選択すると接続リストに加える(Editor Utility Widgetでできそう)
String-Pullingの仕組みを作る
- 経路に含まれるが実際には移動する必要のないウェイポイントを削除する
C++化
- 経路探索は呼び出し回数が非常に多く、結果として負荷が増大してしまうため、C++に移行して呼び出しコストを抑える必要がある
標準のナビゲーションを使った移動との統合
- 標準のナビゲーション移動では速度の調整や移動方向に合わせた回転など色々なことをやってくれているので、経路探索は自作のもので移動は標準のものを使いたい