UE4/5 navmesh helper to detect Navmesh boundaries

RTMNavBoundaryComponent.cpp

#include "RTMNavBoundaryComponent.h"
#include "NavigationSystem.h"
#include "NavMesh/RecastHelpers.h"
#include "NavMesh/RecastNavMesh.h"
#include "Navmesh/Public/Detour/DetourNavMesh.h"

const FRTMNavBoundary FRTMNavBoundary::EMPTY = {{}};

DECLARE_LOG_CATEGORY_CLASS(LogRTMNavBoundaryComponent, Log, All)

namespace RTMNavBoundaryComponentStatics
{
	template<typename T>
	void ReverseRange(TArray<T>& array, int min, int max)
	{
		const int num = max - min;
		const int last = max - 1;
		const int numSwaps = num / 2;
		for(int i = 0; i < numSwaps; i++)
			Swap(array[i + min], array[last - i]);
	}
}

#pragma region SceneProxy
FRTMNavBoundarySceneProxy::FRTMNavBoundarySceneProxy(UPrimitiveComponent* inComponent, const TArray<FRTMNavBoundary>& boundaries, bool respectNavmeshVisibility, bool showAABBs)
	: Super(inComponent)
	, bRespectNavmeshVisibility(respectNavmeshVisibility)
{
	// View flags only affect the DebugText because epic have terrible code
	ViewFlagName = bRespectNavmeshVisibility ? "Navigation" : "OnScreenDebug";
	ViewFlagIndex = static_cast<uint32>(FEngineShowFlags::FindIndexByName(*ViewFlagName));

	const FVector& offset = FVector::UpVector * 20.0f;
	constexpr float lineThickness = 4.0f;
	constexpr float normalThickness = 2.0f;
	constexpr float normalLength = 7.5f;
	const FColor color = FColor::White;

	for(int b = 0, nb = boundaries.Num(); b < nb; b++)
	{
		const auto& boundary = boundaries[b];
		for(int i = 0, num = boundary.Verts.Num(); i < num; i++)
		{
			const auto& currVert = boundary.Verts[i];
			const auto& nextVert = boundary.Verts[(i + 1) % num];
			Lines.Add(FDebugLine(currVert.WorldLocation + offset, nextVert.WorldLocation + offset, color, lineThickness));
			Lines.Add(FDebugLine(currVert.WorldLocation + offset, currVert.WorldLocation + offset + FVector(currVert.Normal, 0.0) * normalLength, color, normalThickness));
		}
		const FVector boundaryStart = boundary.Verts[0].WorldLocation + offset;
		const FVector boundaryStartMarker = boundaryStart + FVector::UpVector * 20;
		Lines.Add(FDebugLine(boundaryStart, boundaryStartMarker, color, lineThickness * 0.5));
		Texts.Add({FString::Printf(TEXT("Boundary %03d"), b), boundaryStartMarker, color});

		if(showAABBs)
			Boxes.Add(FDebugBox(boundary.AABB, FColor::White));
	}
}

FPrimitiveViewRelevance FRTMNavBoundarySceneProxy::GetViewRelevance(const FSceneView* view) const
{
	FPrimitiveViewRelevance result;
	const bool bVisible = !!view->Family->EngineShowFlags.Navigation || !bRespectNavmeshVisibility;

	result.bDrawRelevance = bVisible && IsShown(view);
	result.bDynamicRelevance = true;
	result.bSeparateTranslucency = result.bNormalTranslucency = true;
	return result;
}

uint32 FRTMNavBoundarySceneProxy::GetMemoryFootprint() const
{
	return Super::GetMemoryFootprint();
}

#pragma endregion SceneProxy

#pragma region Component
URTMNavBoundaryComponent::URTMNavBoundaryComponent()
	: Super()
{
	bApplyImpulseOnDamage = false;
	bReplicatePhysicsToAutonomousProxy = false;

	SetGenerateOverlapEvents(false);
	BodyInstance.SetCollisionEnabled(ECollisionEnabled::NoCollision);

	bVisibleInReflectionCaptures = false;
	bVisibleInRealTimeSkyCaptures = false;
	bVisibleInRayTracing = false;
	bRenderInDepthPass = false;
	bReceivesDecals = false;
	bHiddenInGame = true;
}

const FRTMNavBoundary& URTMNavBoundaryComponent::K2_GetBoundaryAtTileIndex(int i)
{
	return Boundaries.IsValidIndex(i) ? Boundaries[i] : FRTMNavBoundary::EMPTY;
}

void URTMNavBoundaryComponent::Update()
{
	if(const auto* navmesh = Cast<ARecastNavMesh>(GetOwner()))
	{
		if(const auto* dtMesh = navmesh->GetRecastMesh())
		{
			TArray<FVertexStrip> allVertexStrips;
			TArray<uint16> allVertIndices;

			FindAllTileBoundarySegments(dtMesh, allVertexStrips, allVertIndices);
			CombineMeshBoundaries(dtMesh, allVertexStrips, allVertIndices);
		}
	}

	OnBoundariesUpdated.Broadcast(Boundaries);
	MarkRenderStateDirty();
}

FPrimitiveSceneProxy* URTMNavBoundaryComponent::CreateSceneProxy()
{
	return new FRTMNavBoundarySceneProxy(this, Boundaries, bRespectNavmeshVisibility, bShowAABBs);
}

FBoxSphereBounds URTMNavBoundaryComponent::CalcBounds(const FTransform& LocalToWorld) const
{
	return FBoxSphereBounds(FBox::BuildAABB(FVector::ZeroVector, FVector(1000000.0, 1000000.0, 1000000.0)));
}

void URTMNavBoundaryComponent::PostInitProperties()
{
	Super::PostInitProperties();

	if(const auto* navmesh = Cast<ARecastNavMesh>(GetOwner()))
		WorldInitHandle = FWorldDelegates::OnPostWorldInitialization.AddUObject(this, &ThisClass::OnWorldInitialized);
}

void URTMNavBoundaryComponent::OnWorldInitialized(UWorld* world, UWorld::InitializationValues initializationValues)
{
	if(world == GetWorld())
	{
		FWorldDelegates::OnPostWorldInitialization.Remove(WorldInitHandle);

		if(UNavigationSystemV1* navSystem = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld()))
			navSystem->OnNavigationGenerationFinishedDelegate.AddDynamic(this, &ThisClass::OnNavmeshGenerationComplete);
	}
}

void URTMNavBoundaryComponent::OnNavmeshGenerationComplete(ANavigationData* navData)
{
	if(navData == GetOwner())
		Update();
}

#if WITH_EDITOR
void URTMNavBoundaryComponent::PostEditChangeProperty(FPropertyChangedEvent& propertyChangedEvent)
{
	Super::PostEditChangeProperty(propertyChangedEvent);
	Update();
}
#endif

void URTMNavBoundaryComponent::FindAllTileBoundarySegments(const dtNavMesh* dtMesh, TArray<FVertexStrip>& vertexStrips, TArray<uint16>& vertIndices)
{
	const uint64 cyclesStart = FPlatformTime::Cycles();

	for(int t = 0, nt = dtMesh->getMaxTiles(); t < nt; t++)
	{
		const dtMeshTile* tile = dtMesh->getTile(t);
		if(!tile->header)
			continue;

		FindMeshTileBoundarySegments(tile, t, vertexStrips, vertIndices);
	}

	const uint64 cyclesEnd = FPlatformTime::Cycles();
	UE_LOG(LogRTMNavBoundaryComponent, Log, TEXT("%s() : %.3f miliseconds"), ANSI_TO_TCHAR(__FUNCTION__), FPlatformTime::ToMilliseconds(cyclesEnd-cyclesStart));
}

void URTMNavBoundaryComponent::FindMeshTileBoundarySegments(const dtMeshTile* tile, int tileIdx, TArray<FVertexStrip>& vertexStrips, TArray<uint16>& vertIndices)
{
	TArray<TPair<uint16, uint16>> edgeVertexIndices;

	for(int p = 0, np = tile->header->polyCount; p < np; p++)
	{
		const dtPoly& poly = tile->polys[p];

		if(poly.getType() != DT_POLYTYPE_GROUND)	// Skip off-mesh links.
			continue;

		for(int v = 0, nv = poly.vertCount, maxV = nv - 1; v < nv; v++)
		{
			// if the edge has neighbours, continue
			if(poly.neis[v] != 0)
				continue;

			const int nextV = v < maxV ? v + 1 : 0;	// (v+1) % nv
			TPair<uint16, uint16> edgeId(poly.verts[v], poly.verts[nextV]);
			edgeVertexIndices.Add(edgeId);
		}
	}

	while(edgeVertexIndices.Num() > 0)
	{
		const uint16 startCount = vertIndices.Num();
		const auto start = edgeVertexIndices.Pop();

		vertIndices.Add(start.Value);
		vertIndices.Add(start.Key);

		// work backwards from the node we added
		uint16 head = start.Key;
		for(int i = 0; i < edgeVertexIndices.Num(); i++)
		{
			if(edgeVertexIndices[i].Value == head)
			{
				head = edgeVertexIndices[i].Key;
				vertIndices.Add(head);
				edgeVertexIndices.RemoveAtSwap(i);
				i = -1;
			}
		}

		// Flip it to be actually backwards
		RTMNavBoundaryComponentStatics::ReverseRange(vertIndices, startCount, vertIndices.Num());
		ensureAlways(vertIndices.Last() == start.Value);

		/* work forwards from the start node */
		uint16 tail = start.Value;
		for(int i = 0; i < edgeVertexIndices.Num(); i++)
		{
			if(edgeVertexIndices[i].Key == tail)
			{
				tail = edgeVertexIndices[i].Value;
				vertIndices.Add(tail);
				edgeVertexIndices.RemoveAtSwap(i);
				i = -1;
			}
		}

		FVertexStrip& strip = vertexStrips.AddDefaulted_GetRef();

		dtReal* startVertPos = &tile->verts[vertIndices[startCount] * 3];
		FMemory::Memcpy(&strip.StartVertexPos, startVertPos, sizeof(dtReal[3]));
		strip.TileIdx = tileIdx;
		strip.StartVertIdx = startCount;
		strip.EndVertIdx = static_cast<uint16>(vertIndices.Num());
	}
}

void URTMNavBoundaryComponent::CombineMeshBoundaries(const dtNavMesh* dtMesh, TArray<FVertexStrip>& vertexStrips, const TArray<uint16>& vertIndices)
{
	static constexpr auto dtVertCompare = [](const dtReal* const a, const dtReal* const b)
	{
		constexpr dtReal tolerance = 0.001;
		return FMath::IsNearlyEqual(a[0], b[0], tolerance)
			&& FMath::IsNearlyEqual(a[1], b[1], tolerance)
			&& FMath::IsNearlyEqual(a[2], b[2], tolerance);
	};

	const uint64 cyclesStart = FPlatformTime::Cycles();
	Boundaries.Empty();

	while(vertexStrips.Num())
	{
		auto currStrip = vertexStrips.Pop();
		auto& currBoundary = Boundaries.AddDefaulted_GetRef();

		dtReal startDtVert[3];
		FMemory::Memcpy(startDtVert, currStrip.StartVertexPos, sizeof(dtReal) * 3);

		currBoundary.Verts.Add({Recast2UnrealPoint(startDtVert), {}, 0, 0});

		int loopSafety = 128;
		bool finished = false;
		while(!finished && --loopSafety > 0)
		{
			const dtMeshTile* tile = dtMesh->getTile(currStrip.TileIdx);

			dtReal endVert[3];
			FMemory::Memcpy(endVert, &tile->verts[(vertIndices[currStrip.EndVertIdx - 1]) * 3], sizeof(dtReal[3]));

			const bool completesLoop = dtVertCompare(startDtVert, endVert);
			const uint16 vertIDEnd = currStrip.EndVertIdx - (completesLoop ? 1 : 0);
			// skip the start vert - it's a duplicate of the previous end vert
			for(int i = currStrip.StartVertIdx + 1; i < vertIDEnd; i++)
			{
				dtReal* v = &tile->verts[vertIndices[i] * 3];
				currBoundary.Verts.Add({Recast2UnrealPoint(v)});
			}

			finished = true;

			if(completesLoop)
				break;

			for(int i = vertexStrips.Num() - 1; i >= 0; --i)
			{
				auto vertStrip = vertexStrips[i];
				if(dtVertCompare(vertStrip.StartVertexPos, endVert))
				{
					vertexStrips.RemoveAtSwap(i);
					currStrip = vertStrip;
					finished = false;
					break;
				}
			}
		}

		if(!ensureAlways(loopSafety > 0))
		{
			UE_LOG(LogRTMNavBoundaryComponent, Error, TEXT("Too many loops"));
		}
	}

	const uint64 cyclesMetaDataStart = FPlatformTime::Cycles();

	// Run through boundaries and mark up normals, lengths and angles
	for(auto& boundary : Boundaries)
	{
		const auto& firstVertex = boundary.Verts[0];
		const auto& secondVertex = boundary.Verts[1];

		FVector prevEdge = secondVertex.WorldLocation - firstVertex.WorldLocation;
		FVector2D prevEdge2D(prevEdge);
		FVector2D prevEdgeNormal2D = prevEdge2D.GetSafeNormal();

		FVector aabbMin(boundary.Verts[0].WorldLocation), aabbMax(aabbMin);

		for(int i = 0, num = boundary.Verts.Num(), max = num - 1; i < num; i++)
		{
			const int currId = i < max ? i + 1 : 0;				// (i+1) % num
			auto& currVertex = boundary.Verts[currId];

			aabbMin = aabbMin.ComponentMin(currVertex.WorldLocation);
			aabbMax = aabbMax.ComponentMax(currVertex.WorldLocation);

			const int nextId = currId < max ? currId + 1 : 0;	// (currId+1) % num
			const auto& nextVertex = boundary.Verts[nextId];

			const FVector nextEdge = nextVertex.WorldLocation - currVertex.WorldLocation;
			const FVector2D nextEdge2D(nextEdge);
			const FVector2D nextEdgeNormal2D = nextEdge2D.GetSafeNormal();

			currVertex.PrecedingEdgeLength = prevEdge.Size();
			currVertex.AngleRads = FMath::FastAsin(FVector2D::CrossProduct(prevEdgeNormal2D, nextEdgeNormal2D));
			currVertex.Normal = (prevEdgeNormal2D - nextEdgeNormal2D).GetSafeNormal();

			prevEdge = nextEdge;
			prevEdge2D = nextEdge2D;
			prevEdgeNormal2D = nextEdgeNormal2D;
		}
		boundary.AABB = FBox(aabbMin, aabbMax);
	}

	const uint64 cyclesEnd = FPlatformTime::Cycles();
	UE_LOG(LogRTMNavBoundaryComponent, Log, TEXT("%s() : %.3f miliseconds total (incl %.3f miliseconds for metadata)"), ANSI_TO_TCHAR(__FUNCTION__), FPlatformTime::ToMilliseconds(cyclesEnd-cyclesStart), FPlatformTime::ToMilliseconds(cyclesEnd-cyclesMetaDataStart));
}
#pragma endregion Component

RTMNavBoundaryComponent.h

#pragma once

#include "CoreMinimal.h"
#include "DebugRenderSceneProxy.h"
#if ENGINE_MAJOR_VERSION >= 5
#include "Detour/DetourLargeWorldCoordinates.h"
#else
using dtReal = float;
#endif

#include "RTMNavBoundaryComponent.generated.h"

class ANavigationData;
class dtNavMesh;
struct dtMeshTile;

USTRUCT(BlueprintType)
struct FRTMNavBoundaryVert
{
	GENERATED_BODY()

	/* Vertex world location */
	UPROPERTY(BlueprintReadOnly)
	FVector WorldLocation;

	/* Vertex normal projected onto 2D horizontal plane */
	UPROPERTY(BlueprintReadOnly)
	FVector2D Normal;

	/* Angle in Radians between the two adjacent edges, projected onto 2D horizontal plane
	 * Negative values indicate a concave boundary vertex */
	UPROPERTY(BlueprintReadOnly)
	float AngleRads;

	/* Length of the preceding edge */
	UPROPERTY(BlueprintReadOnly)
	float PrecedingEdgeLength;
};

USTRUCT(BlueprintType)
struct FRTMNavBoundary
{
	GENERATED_BODY()

	UPROPERTY(BlueprintReadOnly)
	TArray<FRTMNavBoundaryVert> Verts;

	UPROPERTY(BlueprintReadOnly)
	FBox AABB;

	// TODO Possibly add: TArray<FIntPoint> Tiles; OR put that in each of the edge segments
	// Would allow for some filtering of boundaries or edges by tile when searching for relevance?

	static const FRTMNavBoundary EMPTY;
};

class RTMEXAMPLESNAVBOUNDARY_API FRTMNavBoundarySceneProxy : public FDebugRenderSceneProxy
{
public:
	FRTMNavBoundarySceneProxy(UPrimitiveComponent* inComponent, const TArray<FRTMNavBoundary>& boundaries, bool respectNavmeshVisibility = true, bool showAABBs = false);

protected:
	virtual FPrimitiveViewRelevance GetViewRelevance(const FSceneView* view) const override;
	virtual uint32 GetMemoryFootprint() const override;

private:
	bool bRespectNavmeshVisibility;

	using Super = FDebugRenderSceneProxy;
};

UCLASS(ClassGroup=(Custom), meta=(BlueprintSpawnableComponent, DisplayName="RTM Navmesh Boundary Component"), HideCategories=("HLOD", "Physics", "Collision", "Lighting", "Navigation", "Sockets", "Tags", "ComponentTick", "ComponentReplication", "Activation", "LOD", "TextureStreaming", "Mobile", "RayTracing"))
class RTMEXAMPLESNAVBOUNDARY_API URTMNavBoundaryComponent : public UPrimitiveComponent
{
	GENERATED_BODY()

public:
	URTMNavBoundaryComponent();

	DECLARE_EVENT_OneParam(ThisClass, FUpdateEvent, const TArray<FRTMNavBoundary>& boundaries);
	FUpdateEvent OnBoundariesUpdated;

	const TArray<FRTMNavBoundary>& GetNavmeshBoundaries() const { return Boundaries; }

	UFUNCTION(BlueprintCallable, CallInEditor, Category="Update")
	void Update();

protected:
	struct FVertexStrip
	{
		uint32 TileIdx;
		uint16 StartVertIdx;
		uint16 EndVertIdx;
		dtReal StartVertexPos[3];
	};

	/* Shows edge lengths and vertex angles in the debug display */
	UPROPERTY(EditAnywhere, Category="Rendering", meta=(DisplayAfter="bHiddenInGame", EditCondition="bVisible"))
	bool bShowAngleAndDistanceValues = false;

	/* Shows an axis-aligned bounding box for each boundary */
	UPROPERTY(EditAnywhere, Category="Rendering", meta=(DisplayAfter="bHiddenInGame", EditCondition="bVisible"))
	bool bShowAABBs = false;

	/* If true will respect the editor navmesh flag (typically toggled by hitting P in editor) */
	UPROPERTY(EditAnywhere, Category="Rendering", meta=(DisplayAfter="bHiddenInGame", EditCondition="bVisible"))
	bool bRespectNavmeshVisibility = true;

	UFUNCTION(BlueprintCallable, Category="Boundary", meta=(EditCondition="bVisible"))
	const FRTMNavBoundary& K2_GetBoundaryAtTileIndex(int i);

	UPROPERTY(BlueprintReadOnly, Category="Boundary")
	TArray<FRTMNavBoundary> Boundaries;

	virtual FPrimitiveSceneProxy* CreateSceneProxy() override;
	virtual FBoxSphereBounds CalcBounds(const FTransform& LocalToWorld) const override;
	virtual void PostInitProperties() override;

#if WITH_EDITOR
	virtual void PostEditChangeProperty(FPropertyChangedEvent& propertyChangedEvent) override;
#endif

	void FindAllTileBoundarySegments(const dtNavMesh* dtMesh, TArray<FVertexStrip>& vertexStrips, TArray<uint16>& vertIndices);
	void FindMeshTileBoundarySegments(const dtMeshTile* tile, int tileIdx, TArray<FVertexStrip>& vertexStrips, TArray<uint16>& vertIndices);
	void CombineMeshBoundaries(const dtNavMesh* dtMesh, TArray<FVertexStrip>& vertexStrips, const TArray<uint16>& vertIndices);

private:
	FDelegateHandle WorldInitHandle;

	UFUNCTION()
	void OnNavmeshGenerationComplete(ANavigationData* navData);

	void OnWorldInitialized(UWorld* world, UWorld::InitializationValues initializationValues);
};

Proof-of-concept for a system to process UE4/5 Navmesh data and detect boundaries.

This is currently implemented as a component that gets attached to the ARecastNavmesh actor in scene. This is probably not the best solution, but for proof of concept it works fine.

Usage

• Add the files into a code module in your project
• Update the RTMEXAMPLESNAVBOUNDARY_API to your module API macro in the header file
• Add the following to you module's Build.cs:

PrivateDependencyModuleNames.AddRange(
	new string[]
	{
		"Navmesh",
		"NavigationSystem",
		"RHI",
	});

• In editor, add an RTM Navmesh Boundary Component to you navmesh actor
• In the component details panel, click the Update button

By default, the component will visualise the navmesh boundaries when the navmesh is visualised in editor. See additional settings under Rendering on the Component Details for some extra render options

Updating the Boundary Data

The boundary tries to update whenever the navmesh updates, though this is slightly unreliable, especially with undos. You can always force an update using the update button. Some additional integration may be required to make the boundaries update reliably at runtime.

Accessing Boundary Data

Boundary data can be obtained via the public function GetNavmeshBoundaries() in cpp or getting the Boundary variable in blueprints