愛をもってゲームをつくるゴリラのブログ

UE5勉強中のゴリラがいろいろ頑張ります。

3次元の経路探索 - データ作成編

この記事は qiita.comUnreal Engine 4(UE4) #1 Advent Calendar 2020
の23日目の投稿記事です。

ごりです。久々の投稿になります。
3次元の経路探索を何回かに分けて書かせていただきます。
今回はデータの作成編です。

はじめに

この記事は、下記を参考に作成したものになります。
誤っている点などございましたら、連絡いただけると助かります。

http://www.gameaipro.com/GameAIPro3/GameAIPro3_Chapter21_3D_Flight_Navigation_Using_Sparse_Voxel_Octrees.pdf

サンプルプロジェクト

下記で配布しています。
drive.google.com

バージョン

ソースコードも含めていますので、ビルド環境が必要となります。
以下の環境で作成しました。
UE4 Ver.4.25.4
Microsoft Visual Studio Community 2019 Version 16.8.3

使い方

プロジェクトを開くとSVOBoundsVolumeが置かれたレベルが開きます。
詳細タブのカテゴリ【SVO】で階層数を指定し、Generateボタンを押すと、SVOが構築されます。
f:id:m-goolee-y:20201221230436p:plain

カテゴリ【デバッグ】ではそれぞれチェックを入れることで可視化することができます。
f:id:m-goolee-y:20201221231025p:plain

全てにチェックをいれると、このようになります。
f:id:m-goolee-y:20201222210928p:plain

SVO( Sparse Voxel Octrees )

SVOはライティングやレイトレーシングで使用される一般的なデータ構造となっています。
基本的な作りは八分木で、各ツリーのボリュームを8つに階層的に分割することで、
高速な位置検索を可能としています。
SVOはリーフノード、ノード、リンクの３つの要素で構築できます。

リーフノード

SVOでのリーフノードは通常の八分木とは扱いが異なり、
最下層（レイヤー０）のノードのことを指します。
リーフノードは衝突or空き領域だけを考慮しているので、
必要なデータは状態を表す１ビットのみとなります。
リーフノードは通常のノードとは異なり、
64個の場所を表すノードで、サブノードと呼ばれます。
上層のノードはこのリーフノードを元に構築されます。

USTRUCT(BlueprintType)
struct FSVOLeafNode {

	//! サブノードインデックスリスト
	int64 mSubNodeIndices;
};

ノード

ツリーのノードには下記が含まれます。
・空間上の位置を知るための位置情報
・親ノードへのリンク
・最初の子ノードへのリンク
・ノード間を移動できるように隣接ノードへのリンク

子ノードへのリンクが最初の子だけで済むのは、
ノードがモートンコード順に格納されているため、
０～７をオフセットして子ノードへ移動することができます。
子ノードへのリンクが無効の場合、このノードにはボクセルが含まれていないと判断できます。

USTRUCT(BlueprintType)
struct FSVONode {

	//! 位置情報
	FVector mLocation;

	//! 親ノードへのリンク
	FSVOLink mParent;

	//! 最初の子へのリンク
	FSVOLink mFirstChild;

	//! 隣接リンク
	TArray< FSVOLink > mNeighbours;
};

隣接リンク

隣接ノードへのリンクはポインタを使用すると、３２ビットと６４ビットOSで
データサイズが大きく変化してしまうので、メモリ使用量制御のため、
ポインタの代わりに配列へのオフセットが使用されます。
リンクは経路探索でも使用されるので、同じ階層のノードだけでなく、
上下の層を行き来できるように階層番号とノード番号が必要になります。
また、リーフノードは64個の場所を表すノード（サブノードと呼ばれています）で、
サブノード番号もリンクに必要になります。
この3つの情報は32ビットの整数に変換して格納されます。

USTRUCT(BlueprintType)
struct FSVOLink {

	//! レイヤーインデックス( 0 ～ 15 )
	int32 mLayerIndex : 4;

	//! ノードインデックス( 0 ～ 4194303 )
	int32 mNodeIndex : 22;

	//! サブノートインデックス( 0 ～ 63 )
	//! リーフノード内のボクセルインデックスにのみ使用
	int32 mSubNodeIndex : 6;
};

構築手順

１層分のSVOの構築手順は下図のようになっており、
リーフノードを生成し、それをもとに上層のノードを生成、
最後に均一なノードを削除してSVOが構築されます。
f:id:m-goolee-y:20201222212109p:plain

リーフノードの生成

リーフノードは最下層から更に２階層細かくボリュームを分割し、ボリューム内に
コリジョンボクセルが含まれているかどうかを６４ビットの値に格納していきます。
ここで、使用しているUSVOSystemLibrary::BoxOverlapActors は
UKismetSystemLibrary::BoxOverlapActorsを、
回転値をオーバーラップ判定に用いれるように変更しています。

void ASVOBoundsVolume::GenerateLeafNodes(){

	/** リーフノード数を計算 **/
	int32 NodeNum = GetNodeNum(SVO::LAYER_LEAF);

	/** リーフノードのボクセルサイズを取得 **/
	FVector VoxelSize = GetVoxelSizeInLayer(SVO::LAYER_LEAF);

	/** 障害物判定 **/
	TArray<TEnumAsByte<EObjectTypeQuery>> ObjectTypes = {
		EObjectTypeQuery::ObjectTypeQuery1,	//! WorldStatic
	};
	TArray<AActor*> IgnoreActors = { this };
	TArray<AActor*> OverlapActors;
	for (int32 i = 0; i < NodeNum; i++) {

		int32 LeafNodeIndex = i >> SVO::BIT_LEAFLAYER;
		if (!mLeafNodes.Contains(LeafNodeIndex)) {
			mLeafNodes.Add(LeafNodeIndex, FSVOLeafNode());
		}

		/** 指定階層のノード座標を取得 **/
		FVector Location = GetNodeLocationInLayer(SVO::LAYER_LEAF, i);
		/** コリジョンがノード内に存在するか判定 **/
		if (USVOSystemLibrary::BoxOverlapActors(
			this,
			Location,
			VoxelSize * 0.5f,
			GetActorRotation(),
			ObjectTypes,
			nullptr,
			IgnoreActors,
			OverlapActors
		)) {
			mLeafNodes[LeafNodeIndex].SetBlock(i & SVO::BIT_LEAFNODEINDEX);
		}
	}
}
各層のノードの生成

各層のノードは先程生成したリーフノードをもとに
下層から上層に向けて、生成していきます。
リーフノードの値が０以外の場合、リーフノードには
コリジョンが含まれているということがわかります。
このときに、上層のノードへリンクづけを行います。

void ASVOBoundsVolume::GenerateLayerNodes() {
	/** 指定層分の領域確保 **/
	mNodeList.SetNum(mNumOfLayers+1);
	for (auto LeafNode : mLeafNodes) {
		int32 CurrentLayer = 0;
		while (CurrentLayer <= mNumOfLayers) {

			/** 子の階層とインデックスを計算 **/
			int32 ChildLayer = FMath::Max(0, CurrentLayer - 1);
			int32 ChildIndex = LeafNode.Key >> (SVO::BIT_LAYER * ChildLayer);

			if (CurrentLayer != 0) {
				/** 最下層でない場合は自身へのリンクを子ノードに設定する **/
				int32 ParentIndex = LeafNode.Key >> (SVO::BIT_LAYER * CurrentLayer);
				mNodeList[CurrentLayer - 1][ChildIndex].SetParent(FSVOLink(CurrentLayer, ParentIndex));
			}

			int32 NodeIndex = LeafNode.Key >> (SVO::BIT_LAYER * CurrentLayer);
			if (!mNodeList[CurrentLayer].Contains(NodeIndex)) {
				FSVONode Node;
				Node.SetLocation(GetNodeLocationInLayer(CurrentLayer, NodeIndex));
				mNodeList[CurrentLayer].Add(NodeIndex, Node);
			}

			if (!mNodeList[CurrentLayer][NodeIndex].HasAnyChildren()) {
				if (!LeafNode.Value.IsOpen()) {
					FSVOLink Child(ChildLayer, ChildIndex);
					if (CurrentLayer == 0) {
						/** 最下層のノードが均一でない場合はリーフノードの最初のサブノートインデックスを最初の子に設定 **/
						int32 SubNodeIndex = LeafNode.Key << SVO::BIT_LEAFNODEINDEX;
						Child.SetSubNodeIndex(SubNodeIndex);
					}
					mNodeList[CurrentLayer][NodeIndex].SetFirstChild(Child);
				}
			}
			CurrentLayer++;
		}
	}
}
隣接ノードのリンクづけ

上層までノードが生成されたので、次は上層から下層の順に
隣接ノードのリンクづけをしていきます。
この時点では均一なノードは削除していないので、ノードリストに含まれていない
モートンコードはボリューム外として、処理をスキップします。
均一なノード（子を持たないノード）だった場合は上層も均一かどうか判定し、
均一だった場合は上層のノードを隣接ノードとしてリンクを生成していきます。

void ASVOBoundsVolume::GenerateNeighbourLink() {

	int32 CurrentLayer = mNumOfLayers;
	while ( CurrentLayer >= 0 ) {
		for (auto& Node : mNodeList[CurrentLayer]) {
			/** モートンコードを1度座標に戻す **/
			FVector Location = Morton::Decode( Node.Key );
			for (int32 i = 0; i < SVO::Directions.Num(); i++) {
				/** 上下左右前後の6方向の座標でモートンコードに変換 **/
				int32 NeighborIndex = Morton::Code( Location + SVO::Directions[i] );
				FSVOLink Neighbour;
				if (FindNeighbour(CurrentLayer, NeighborIndex, Neighbour )) {
					Node.Value.AddNeighbour( Neighbour );
				}
			}
		}
		CurrentLayer--;
	}
}

bool ASVOBoundsVolume::FindNeighbour(int32 CurrentLayer, int32 NeighbourIndex, FSVOLink& Neighbour) {

	/** 隣接ノード情報をクリア **/
	Neighbour.Clear();

	if (!mNodeList[CurrentLayer].Contains(NeighbourIndex)) {
		/** 領域外の場合スキップ **/
		return false;
	}

	Neighbour.SetLayerIndex(CurrentLayer);
	Neighbour.SetNodeIndex(NeighbourIndex);
	if (mNodeList[CurrentLayer][NeighbourIndex].HasAnyChildren()) {
		if (CurrentLayer == 0 && mLeafNodes[NeighbourIndex].IsClosed()) {
			return false;
		}
		/** ノードが均一でない場合は、ここでストップ **/
		return true;
	}
	
	/** 均一な場合、均一な上層ノードを探索 **/
	int32 Layer = CurrentLayer+1;
	int32 Index = NeighbourIndex >> SVO::BIT_LAYER;
	while ( Layer <= mNumOfLayers ) {
		if (!mNodeList[CurrentLayer][Index].HasAnyChildren()) {
			Neighbour.SetLayerIndex(Layer);
			Neighbour.SetNodeIndex(Index);
		}
		Layer++;
		Index = Index >> SVO::BIT_LAYER;
	}
	return true;
}
均一ノードの削除

隣接ノードへのリンクを生成したら、最後に下層から上層に向けて
均一なノードの子ノードを削除していきます。

void ASVOBoundsVolume::Rasterize() {
	int32 CurrentLayer = 1;
	while ( CurrentLayer <= mNumOfLayers) {
		for ( auto Node : mNodeList[CurrentLayer] ) {
			if ( Node.Value.HasAnyChildren()) {
				continue;
			}
			/** 均一なノードの場合、子ノードは不要なので削除 **/
			for (int32 i = 0; i < SVO::NUM_CHILDREN; i++) {
				int32 RemoveNodeIndex = Node.Key << SVO::BIT_LAYER | i;
				mNodeList[CurrentLayer-1].Remove(RemoveNodeIndex);
				if (CurrentLayer-1 == 0) {
					/** 最下層の場合はリーフノードも削除 **/
					mLeafNodes.Remove(RemoveNodeIndex);
				}
			}
		}
		CurrentLayer++;
	}
}

参考

その15 8分木空間分割を最適化する！
空を優雅に飛ぶキャラクターのための3次元パス検索とステアリング

まとめ

ここまで見ていただきありがとうございました。
昔に作ったプロジェクトを引っ張り出してきて確認してみたら、
リーフノードの部分完全に抜けており、
「あれ？これ全然違うな。」となり、大慌てで作り直してました。

続編については年内に投稿予定です。

明日は @nokonoko_08 さんの記事になります。
果たして上司に脅されずに済んだのでしょうか。