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

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

この辺りの話は過去の記事を読んでいただければと思います。
【UE4】Nav Link Proxy を使ってAIにジャンプをさせる

「どうにか自動で配置できるようにならないかな～」と思っていましたが、偶然Twitterで見かけた
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を開きます。

1. ステージ上部にあるNavMeshBoundsVolumeを降ろします。

1. World OutlinerでAutoSpawnNavLinkNavMeshを選択し、DetailsパネルのRegeneration Nav Linkをクリックします。

1. 自動的にNavLinkProxyが配置されます。

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

1. レッツプレイ！

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

#AUsefulNavLinkProxyクラス
プロジェクト中にあるAUsefulNavLinkProxyクラスは
【UE4】RoboRecallを参考にNavLinkProxyを使いやすくする
をほぼコピペしたものです。
上の記事と異なる点として

1. UBoxComponentの代わりにUSphereComponentを使用
2. StartEditorComp、EndEditorCompのワールド座標を返すGetter関数を追加
3. StartEditorComp、EndEditorCompの新しい座標を設定するSetter関数を追加
   の３つとなります。

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

	static ConstructorHelpers::FObjectFinder<UClass> BPNavLink(TEXT("/Game/BP_UsefulNavLinkProxy.BP_UsefulNavLinkProxy_C"));
	BPNavLinkClass = BPNavLink.Object;

ブループリントクラスをC++側でSpawnActorする際に必要なクラス情報を取得しています。

コメントにも書かれていますが、このFObjectFinderを利用した方法は
UE4: C++ コード から C++ クラスまたは Blueprint のアクターを FindObject して SpawnActor する方法
を参考にしました。

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

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

となります。

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

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

DrawDebugArrowによるデバッグ表示。NavMeshのエッジの位置に黄色の矢印が描画されているのがわかります。
NavMeshのデバッグ情報を取得するテクニックはUNavMeshRenderingComponentクラスのGatherData関数を参考にしました.

---

			const float EdgeSteps = Edge.Size() / EdgeDivisor;
			for (float EdgeStep = EdgeSteps; EdgeStep < Edge.Size(); EdgeStep += EdgeSteps)

このfor文ではエッジ一つ一つ取り出しています。（デバッグ表示の黄色矢印一本分です）
ベクトルEdgeをEdgeDivisorで分割しエッジのどの位置からNavLinkProxyを生成するかを決めています。

黄色矢印の丁度中心から手前側に水色の矢印が出ている事がわかります。これはEdgeDivisorを2とした時の結果です。

EdgeDivisorを3にした時の結果です。一つのエッジが3分割され、分割された位置から水色矢印が伸びているのがわかります。

##NavLinkProxyの生成データを作成する
SpawnNavLinkProxy関数ではNavLinkProxyをレベル上にSpawnするためのデータ作成を行ないます。

SpawnNavLinkProxy関数という関数名は全くもって相応しくない関数名だと記事を書いていて感じました。これは怒られるやつです。
きちんとした関数名を付けるならMakeSpawnDataPerEdgeとでもするのが良いでしょうか。
読んでいる皆様にはご迷惑をお掛けしますが、ここでは自戒を込めて、そのままにしておくことにします。

bool bSuccess = GetWorld()->LineTraceSingleByChannel(Hit, EdgeStepVertex, TraceEnd, ECollisionChannel::ECC_Visibility);

エッジ外側にレイを飛ばす事で**「その場所は崖か？それとも壁か？」を判定しています。
次の画像ではレイの衝突検知の結果が表示されています。

NavLinkProxyは基本的に「崖上から崖下に向けて配置」**しています。このルールにより生成するNavLinkProxyが2重に重なってしまう事を防いでいます。

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

		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軸が向いている回転行列を取得しています。

		FVector ToFloorRayDir = FVector::UpVector.RotateAngleAxis(-SlantDegree, RotateMatrix.TransformPosition(FVector(0, 1, 0)));

上のコードは回転行列を使用して床を検知するために飛ばしたレイを度数指定で傾かせています。度数指定でレイを傾かせたいがために回転行列を作成しました。
変数SlantDegreeはEditAnywhereにしているのでDetailsパネルで編集することが出来ます。

度数指定でレイを傾けた結果。（赤枠部分）

傾けたレイを飛ばし「その地点に床があるかどうか」を調べます。レイの長さは変数JumpHeightで定義されており、Detailsパネルで編集することが出来ます。

デフォルトでJumpHeightには500.0fが設定されている。これは「AIは500cm以上はジャンプしても届かない」ということを意味する。（最も高い手前の崖にはNavLinkProxyが配置されていない）

			NavLinkProxySpawnData.AddUnique(FNavLinkProxySpawnData((EdgeStepVertex - Hit.Location) / 2.0f, EdgeStepVertex, Hit.Location));

レイが床と衝突したらNavLinkProxyを配置するための生成データを作成し配列へと追加します。

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

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

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

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

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

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

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の分類方法
が分かりやすくまとめられています。

#参考資料
REAL-TIME DYNAMIC COVER SYSTEM FOR UNREAL ENGINE 4
UE4: C++ コード から C++ クラスまたは Blueprint のアクターを FindObject して SpawnActor する方法
その47 カメラのようにキャラクタを向かせたい！
【UE4】Nav Link Proxy を使ってAIにジャンプをさせる
【UE4】RoboRecallを参考にNavLinkProxyを使いやすくする