【UE4】RecastNavMeshを拡張してNavLinkProxyを自動で配置させる.

#はじめに
UE4でAIに障害物を飛び越えたり高い所にジャンプさせたりするためには**NavLinkProxy**アクタをレベルに配置する必要があります。
しかしNavLinkProxyをきちんと動作させるには**レベルの配置作業**に加えて**SmartLink等のプロパティの値調整**の２工程が必須となり、レベルに50個配置するとなった場合は非常に面倒ですしプロパティの調整忘れが発覚した際には調整忘れしたNavLinkProxyの特定にも大きく時間を取られます。

>この辺りの話は過去の記事を読んでいただければと思います。
[【UE4】Nav Link Proxy を使ってAIにジャンプをさせる](https://qiita.com/Dv7Pavilion/items/0250474f93934caf1815#nav-link-proxyの罠)

「どうにか自動で配置できるようにならないかな～」と思っていましたが、偶然Twitterで見かけた
[REAL-TIME DYNAMIC COVER SYSTEM FOR UNREAL ENGINE 4](https://horugame.com/real-time-dynamic-cover-system-for-unreal-engine-4/)
というチュートリアルにバッチリ適用できそうなテクニックが紹介されていたので「これなら自動配置いける！」と思い、実装してみた次第です。


#プロジェクトはこちらから！
https://1drv.ms/u/s!Au-8FqgREBKZhTVlqwBx1FjFJFIA
UE4バージョン：4.19.1


#NavLinkProxyの自動配置を試してみる
1. ダウンロードしたプロジェクトを開いたらContent BrowserのExampleを開きます。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/cce7bb4c-707d-9d90-7086-53d006b38cc9.png" width=30%>

2. ステージ上部にある**NavMeshBoundsVolume**を降ろします。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/e7cc2ca6-7de7-b5cc-01ab-22b065d58e17.png" width=30%>

3. World Outlinerで**AutoSpawnNavLinkNavMesh**を選択し、Detailsパネルの**Regeneration Nav Link**をクリックします。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/743624bc-948c-eb15-5f95-f05f82335d4f.png" width=30%>

4. 自動的にNavLinkProxyが配置されます。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/75c14a90-e62a-b79b-9a6a-6f7d8a26aaeb.png" width=30%>

**※NavMeshBoundsVolumeを移動後、Regeneration Nav Linkを押してもNavLinkProxyが変に残ってしまったりNavMeshBoundsVolume外に生成されてしまった場合はもう一度Regeneration Nav Linkを押してください。正常に配置されます。**

5. レッツプレイ！


#プロジェクトの解説
この記事では今回実現した機能のほとんどを実装している**AAutoSpawnNavLinkNavMeshクラス**を重点的に解説していきます。

#AUsefulNavLinkProxyクラス
プロジェクト中にある**AUsefulNavLinkProxyクラス**は
[【UE4】RoboRecallを参考にNavLinkProxyを使いやすくする](https://qiita.com/Dv7Pavilion/items/f35ebc9ace203c6a7141)
をほぼコピペしたものです。
上の記事と異なる点として
1. UBoxComponentの代わりに**USphereComponent**を使用
2. StartEditorComp、EndEditorCompのワールド座標を返すGetter関数を追加
3. StartEditorComp、EndEditorCompの新しい座標を設定するSetter関数を追加
の３つとなります。

#AAutoSpawnNavLinkNavMeshクラス
##コンストラクタ（AAutoSpawnNavLinkNavMesh）

```cpp
	static ConstructorHelpers::FObjectFinder<UClass> BPNavLink(TEXT("/Game/BP_UsefulNavLinkProxy.BP_UsefulNavLinkProxy_C"));
	BPNavLinkClass = BPNavLink.Object;
```
ブループリントクラスをC++側でSpawnActorする際に必要な**クラス情報を取得**しています。

>コメントにも書かれていますが、このFObjectFinderを利用した方法は
[UE4: C++ コード から C++ クラスまたは Blueprint のアクターを FindObject して SpawnActor する方法](http://usagi.hatenablog.jp/entry/2017/10/17/123000)
を参考にしました。

配布したプロジェクトではBP_UsefulNavLinkProxyは**Content直下**に格納されていますが、AIフォルダに格納した場合は

```cpp
BPNavLink(TEXT("/Game/AI/BP_UsefulNavLinkProxy.BP_UsefulNavLinkProxy_C"));
```

となります。

##NavMeshのエッジ（縁）を取得する
NavLinkProxyの自動配置するための処理は**OnNavMeshTilesUpdated関数**から始まります。
この関数は**FRecastNavMeshGeneratorクラス**から呼び出され、引数には**更新対象となるNavMeshのタイルインデックス**が渡されています。

ProcessNavMeshEdge関数では**GetDebugGeometry関数**を利用してNavMeshのデバッグ情報を取得しています。
取得したデバッグ情報から**エッジの始点・終点、エッジベクトル、エッジの方向ベクトル**を求められます。

> <img src="https://qiita-image-store.s3.amazonaws.com/0/104467/459fcce5-97f0-2f2f-83a7-f3181c998b66.png" width=50%>
DrawDebugArrowによるデバッグ表示。NavMeshのエッジの位置に黄色の矢印が描画されているのがわかります。
NavMeshのデバッグ情報を取得するテクニックは**UNavMeshRenderingComponentクラスのGatherData関数**を参考にしました.

---

```cpp
			const float EdgeSteps = Edge.Size() / EdgeDivisor;
			for (float EdgeStep = EdgeSteps; EdgeStep < Edge.Size(); EdgeStep += EdgeSteps)
```
このfor文ではエッジ一つ一つ取り出しています。（デバッグ表示の黄色矢印一本分です）
ベクトルEdgeをEdgeDivisorで分割し**エッジのどの位置からNavLinkProxyを生成するか**を決めています。

> <img src="https://qiita-image-store.s3.amazonaws.com/0/104467/459fcce5-97f0-2f2f-83a7-f3181c998b66.png" width=50%>
黄色矢印の**丁度中心から**手前側に水色の矢印が出ている事がわかります。これはEdgeDivisorを**2**とした時の結果です。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/7f3a8b68-fade-f153-f215-3782d583fbd8.png" width=50%>
EdgeDivisorを**3**にした時の結果です。一つのエッジが3分割され、分割された位置から水色矢印が伸びているのがわかります。


##NavLinkProxyの生成データを作成する
SpawnNavLinkProxy関数では**NavLinkProxyをレベル上にSpawnするためのデータ作成**を行ないます。
>**SpawnNavLinkProxy関数**という関数名は**全くもって相応しくない関数名**だと記事を書いていて感じました。これは怒られるやつです。
きちんとした関数名を付けるなら**MakeSpawnDataPerEdge**とでもするのが良いでしょうか。
読んでいる皆様にはご迷惑をお掛けしますが、ここでは自戒を込めて、そのままにしておくことにします。

```cpp
bool bSuccess = GetWorld()->LineTraceSingleByChannel(Hit, EdgeStepVertex, TraceEnd, ECollisionChannel::ECC_Visibility);
```
エッジ外側にレイを飛ばす事で**「その場所は崖か？それとも壁か？」**を判定しています。
次の画像ではレイの衝突検知の結果が表示されています。
<img src="https://qiita-image-store.s3.amazonaws.com/0/104467/67cd8585-9c7e-9a7d-7437-71f39a1738eb.png" width=50%>
NavLinkProxyは基本的に**「崖上から崖下に向けて配置」**しています。このルールにより生成するNavLinkProxyが2重に重なってしまう事を防いでいます。

レイが衝突しなかった（つまり崖）と判定されると次のステップへ進みます。

```cpp
		FVector EdgeToOutside = (TraceEnd - EdgeStepVertex).GetSafeNormal();

		FVector YDir = FVector::CrossProduct(FVector(0, 0, 1), EdgeToOutside);
		FVector ZDir = FVector::CrossProduct(EdgeToOutside, YDir);
		FMatrix RotateMatrix = FMatrix(EdgeToOutside, YDir, ZDir, FVector4(0, 0, 0, 1));
```
エッジの外側へと向かう方向ベクトルから**常に正面にX軸が向いている**回転行列を取得しています。

```cpp
		FVector ToFloorRayDir = FVector::UpVector.RotateAngleAxis(-SlantDegree, RotateMatrix.TransformPosition(FVector(0, 1, 0)));
```
上のコードは回転行列を使用して床を検知するために飛ばしたレイを**度数指定で傾かせて**います。度数指定でレイを傾かせたいがために回転行列を作成しました。
変数SlantDegreeはEditAnywhereにしているのでDetailsパネルで編集することが出来ます。

> <img src="https://qiita-image-store.s3.amazonaws.com/0/104467/cb01e922-e0b2-2f7c-4f7c-30e1bc560145.png" width=50%>
度数指定でレイを傾けた結果。（赤枠部分）

傾けたレイを飛ばし「その地点に床があるかどうか」を調べます。レイの長さは**変数JumpHeight**で定義されており、Detailsパネルで編集することが出来ます。
> <img src="https://qiita-image-store.s3.amazonaws.com/0/104467/47db9899-bba6-b67d-8a47-ef701ec937eb.png" width=50%>
デフォルトでJumpHeightには**500.0f**が設定されている。これは「AIは500cm以上はジャンプしても届かない」ということを意味する。（最も高い手前の崖にはNavLinkProxyが配置されていない）

```cpp
			NavLinkProxySpawnData.AddUnique(FNavLinkProxySpawnData((EdgeStepVertex - Hit.Location) / 2.0f, EdgeStepVertex, Hit.Location));
```
レイが床と衝突したらNavLinkProxyを配置するための生成データを作成し配列へと追加します。


##生成データを基にNavLinkProxyをレベルへSpawnする
実際のNavLinkProxyをレベル上に自動配置する処理はDetailsパネルにある**RegenerateNavLink**を操作することで実行されます。

Detailsパネルで公開されている編集可能なプロパティを変更すると**PostEditChangePropery関数**が実行されます。

```cpp
void AAutoSpawnNavLinkNavMesh::PostEditChangeProperty(FPropertyChangedEvent & PropertyChangedEvent)
{
	if (RegenerateNavLink)
	{
		DeleteAllNavLinks();
		RegenerateNavLinks();
		NavLinkProxySpawnData.Empty();

		// RenerateNavLinkを即座にFalseに戻すことで「ボタン」のような動作が出来る.
		RegenerateNavLink = false;
	}
}
```

DeleteAllNavLinks関数ではレベル上のNavLinkProxyアクタを**GetAllActorsOfClass**で取得しDestroyActor関数で削除しています。
GetAllActorsOfClass関数を使用した理由は
「ランタイムで実行されるわけじゃないし、これで良いかな～」
という単純な理由です。

RegenerateNavLinks関数は実装を見て分かる通り非常に単純な作りです。

```cpp
void AAutoSpawnNavLinkNavMesh::RegenerateNavLinks()
{
	for (FNavLinkProxySpawnData data : NavLinkProxySpawnData)
	{
		auto NavLink = GetWorld()->SpawnActor<AUsefulNavLinkProxy>(BPNavLinkClass, FTransform(data.SpawnLocation));
		NavLink->SetEditorCompLocation(data.StartLocation, data.EndLocation);
		// スポーンしたオブジェクトをアウトライナーのフォルダーに突っ込みたい時は次の関数を使う.
		NavLink->SetFolderPath("/NavLinkProxys");
	}
}
```
OnNavMeshTilesUpdated関数から続く処理で得られたNavLinkProxy生成データを一つずつ取り出しSpawnActorでレベルにSpawnします。
SetEditorCompLocation関数でSmart Linkプロパティを崖上と崖下に設定します。
>Smart LinkプロパティのLink Relative **Start**が**崖上**となりLink Relative **End**が**崖下**となります。

以上でレベル上にはNavLinkProxyが生成され自動で配置されます。


#なぜ生成データを配列に格納するのか？
SpawnNavLinkProxy関数では実際にSpawnActorせずに**SpawnActorする際に渡す生成データを配列に格納**していました。

この方法を取ったのには理由があります。

OnNavMeshTilesUpdated関数はNavMeshが生成される際に呼び出されます。
NavMeshが生成される瞬間とは
1. NavMeshBoundsVolumeを動かした
2. 障害物がNavMesh上に配置された
3. NavLinkProxyがNavMesh上に配置された
等々があります。

NavLinkProxyが配置されたときにもOnNavMeshTilesUpdated関数が呼び出されてしまうため
もしもSpawnNavLinkProxy関数で実際にSpawnActorをしてしまうと。

**OnNavMeshTilesUpdated関数が呼ばれNavLinkProxyを生成し配置する。→NavMeshの変更を検知しFRecastNavMeshGeneratorクラスがOnNavMeshTilesUpdated関数を呼び出す。→OnNavMeshTilesUpdated関数が呼ばれNavLinkProxyを生成し配置する。**

とループしてしまい、NavLinkProxyは永遠にレベル上にSpawnされ続けます。

この問題を回避するために、OnNavMeshTilesUpdated関数では生成データを作成し配列に格納するだけに留めておき、RegenerateNavLinkプロパティが操作された時に一気にSpawnするという、今まで紹介してきた手法になりました。


#自作したRecastNavMeshを使うために
自作したRecastNavMeshクラスを使うためにはProject SettingsでSupported Agentsの設定をする必要があります。
設定方法に関しては
[【UE4】継承を用いた複数NavMeshの分類方法](https://qiita.com/4_mio_11/items/c8c0c4b9767fcaf5219e#確認事項)
が分かりやすくまとめられています。


#参考資料
[REAL-TIME DYNAMIC COVER SYSTEM FOR UNREAL ENGINE 4](https://horugame.com/real-time-dynamic-cover-system-for-unreal-engine-4/)
[UE4: C++ コード から C++ クラスまたは Blueprint のアクターを FindObject して SpawnActor する方法](http://usagi.hatenablog.jp/entry/2017/10/17/123000)
[その47 カメラのようにキャラクタを向かせたい！](http://marupeke296.com/DXG_No47_CharacterDirectionMatrix.html)
[【UE4】Nav Link Proxy を使ってAIにジャンプをさせる](https://qiita.com/Dv7Pavilion/items/0250474f93934caf1815#nav-link-proxyの罠)
[【UE4】RoboRecallを参考にNavLinkProxyを使いやすくする](https://qiita.com/Dv7Pavilion/items/f35ebc9ace203c6a7141)