UE4 动态创建寻路网格

目录

1. 配置

2. 组件种类

3. 导航数据反推

4. UE4 Navmesh寻路

4.1 Recast

4.1.2生成Navmesh的流程

4.2 Detour

6. Recast

7. 导航网格创建（Runtime）

8. 导航网格绘制（Runtime）

8.1源码分析

初始化：

收集数据方式一

收集数据方式二

8.2绘制方法

1. 配置

        项目设置-》引擎-》导航系统（Navigation System）

                自动创建导航数据

项目设置-》引擎-》导航网格体-》生成

        Cell大小

        Cell高度

        Runtime Generation：使用Dynamic

2. 组件种类

3. 导航数据反推

        继承层次：

        ANavigationData

                表示抽象的导航数据(子类为NavMesh, NavGraph等)，用作NavigationSystem处理的所有导航类型的公共接口

4. UE4 Navmesh寻路

参考：UE4 Navmesh寻路（一）Recast基础 - 知乎

目前生成Navmesh数据主要有两种方式：多边形裁剪和体素化。

        （1）多边形裁剪是直接对地形的多边形网格数据进行裁剪及合并，从而生成导航网格。方法比较直观，但难度更高，目前havok引擎使用了此方法。

        （2）体素化是对地形多边形网格进行栅格化，然后用这些“格子”重新生成导航网格，方法更复杂，但难度更低，Recast使用了此方案，而UE4使用了Recast。

4.1 Recast

它可以把地形数据进行抽象和简化，生成人工智能体可理解的导航数据。

Recast是一种优秀的navmesh生成套件

• 自动化，可以处理任意地形数据，输出导航网格
• 快速高效
• 能处理动态碰撞
• 开源，可根据自己游戏内容进行定制
• 自带可视化工具

Recast在运行时，首先会从关卡地形中构建一个体素模型，之后使用体素创建导航网格。

处理过程包括3步：创建体素模型，把模型分割成简单的区域，把这些区域再分割成简单多边形（凸的）

• 通过把输入的三角形mesh进行光栅化，形成一个多层的高度场，就能得到体素模型。之后可以对体素模型做一些简单的过滤，去掉玩家不可达的位置
• 体素模型描述的可行走区域被划分为重叠的2D区域，这些区域只有一个未重叠的等高线，这可以大大简化最后一步处理步骤
• 首先沿着边界划这些区域并进行化简可以剥离出导航多边形。然后把这些导航多边形处理为凸多边形，凸多边形可以更好的用于寻路和对场景进行空间推理。

4.1.2生成Navmesh的流程

配置结构体rcConfig

        Project Config ->Engine->Navigation System：

        cell size：xz平面下体素的大小（所以是正方形）

        cell height：y轴下体素的高度

        walkableSlopeAngle：可行走倾斜角度

        walkableHeight：寻路agent高度

        walkableClimb：寻路agent爬坡高度（楼梯等场景）

        walkableRadius：寻路agent半径（过滤太靠地图边缘地区）

光栅化就是体素化

        rcRasterizeTriangles

过滤可行走表面

        rcFilterLowHangingWalkableObstacles

        rcFilterLedgeSpans

                过滤突起span

                rcFilterWalkableLowHeightSpans

                        过滤可行走的低高度span

分割可走面为简单多边形

                rcBuildCompactHeightfield

                       基于walkableHeight和walkableClimb判断连通，以编码的形式设置con属性

                rcErodeWalkableArea

                        基于walkableRadius裁剪可行走区域。

                                用dist数组去存每个rcCompactSpan与可行走区域边缘的最近距离，得到dist结果后，如果距离小于walkableRadius*2就将chf.areas[i]标记为不可行走。？？？

具体分为3步：

• 初始化，span不可行走或者四周有一个不可行走的点，则dist标记为0；
• 从左下开始扫描一遍，做一次dist紧缩；
• 从右上开始扫描一遍，再做一次dist紧缩。

执行区域划分算法，把离散的Span整合为大的Region。

有三种方法可选：

• Watershed（分水岭） 最经典，最常用，效果最好，慢，一般用于离线处理，适合大地图；
• Monotone 最快且保证生成的是不重叠、没有洞的Region，但生成的Region可能又细又长，不过速度最快；
• Layer：速度、效果介于Watershed和Monotone之间，适用于tiled navmesh，且tile大小偏小

4.2 Detour

        利用导航网格进行寻路；

5. 算法

（1）A*算法

A*算法详解 一看就会 手把手推导 完整代码注释 - 知乎

        是一种静态路网中求解最短路最有效的直接搜索方法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。

特点为在Dijkstra算法基础上引入了启发因子；

（2）曼哈顿距离算法

https://zhuanlan.zhihu.com/p/507719888

        曼哈顿距离也叫出租车距离，用来标明两个点在标准坐标系上的绝对轴距总和。简单来说，对比一下欧氏距离。

欧氏距离：

曼哈顿距离：

/* 曼哈顿距离和欧氏距离的意义相近，也是为了描述两个点之间的距离，不同的是曼哈顿距离只需要做加减法，这使得计算机在大量的计算过程中代价更低，而且会消除在开平方过程中取近似值而带来的误差。 */

        Detour中使用了欧几里得距离作为启发函数，即两个坐标之间的三维距离。

6. Recast

SoloMesh::handleBuild()

（1）获取导航网格盒体信息（最大/小盒体、顶点、顶点数量、三角、三角数量）；

（2）初始化编译配置信息；

//cellSize、cellHeight、可行走斜坡角度agentMaxSlope、、、、：
	m_cfg.cs = m_cellSize;
	m_cfg.ch = m_cellHeight;
	m_cfg.walkableSlopeAngle = m_agentMaxSlope;
	m_cfg.walkableHeight = (int)ceilf(m_agentHeight / m_cfg.ch);
	m_cfg.walkableClimb = (int)floorf(m_agentMaxClimb / m_cfg.ch);
	m_cfg.walkableRadius = (int)ceilf(m_agentRadius / m_cfg.cs);
	m_cfg.maxEdgeLen = (int)(m_edgeMaxLen / m_cellSize);
	m_cfg.maxSimplificationError = m_edgeMaxError;
	m_cfg.minRegionArea = (int)rcSqr(m_regionMinSize);// Note: area = size*size
	m_cfg.mergeRegionArea = (int)rcSqr(m_regionMergeSize);// Note: area = size*size
	m_cfg.maxVertsPerPoly = (int)m_vertsPerPoly;
	m_cfg.detailSampleDist = m_detailSampleDist < 0.9f ? 0 : m_cellSize * m_detailSampleDist;
	m_cfg.detailSampleMaxError = m_cellHeight * m_detailSampleMaxError;

（3）场景模型体素化（Voxelization），或者叫光栅化（Rasterization）。

//分配我们栅格化输入数据的体素高度场。
m_solid = rcAllocHeightfield();
//创建高度场。
rcCreateHeightfield(m_ctx, *m_solid, m_cfg.width, m_cfg.height, m_cfg.bmin, m_cfg.bmax, m_cfg.cs, m_cfg.ch)
//分配可以保存三角形区域类型的数组。
//如果你有多个网格需要处理，分配和数组可以容纳你需要处理的最大数量的三角形。
m_triareas = new unsigned char[ntris];
// 根据它们的坡度找到适合行走的三角形，并栅格化它们。
// 如果你的输入数据是多个网格，你可以在这里转换它们，计算每个网格的类型并栅格化它们。
rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, verts, nverts, tris, ntris, m_triareas);
rcRasterizeTriangles(m_ctx, verts, nverts, tris, m_triareas, ntris, *m_solid, m_cfg.walkableClimb)

（4）过滤可行走表面（Walkable Suface）

// 一旦所有的几何图形都栅格化了，我们就会进行初始的滤波，以消除由保守栅格化引起的多余的悬垂，以及角色不可能站立的滤波跨度。
rcFilterLowHangingWalkableObstacles(m_ctx, m_cfg.walkableClimb, *m_solid);
rcFilterLedgeSpans(m_ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid);
rcFilterWalkableLowHeightSpans(m_ctx, m_cfg.walkableHeight, *m_solid);
（5）区域生成（Region）
// 压缩高度字段，以便从现在开始更快地处理。
// 这将导致更多的缓存一致数据，以及可行走单元之间的邻居将被计算。
rcAllocCompactHeightfield();
rcBuildCompactHeightfield(m_ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid, *m_chf)
// 通过代理半径削减可行走区域Erode the walkable area by agent radius.
rcErodeWalkableArea(m_ctx, m_cfg.walkableRadius, *m_chf)
// (可选)标记区域。
rcMarkConvexPolyArea(m_ctx, vols[i].verts, vols[i].nverts, vols[i].hmin, vols[i].hmax, (unsigned char)vols[i].area, *m_chf);
//划分高度场，以便我们稍后可以使用简单的算法对可行走区域进行三角测量。
// 有3种分区方法，每种方法各有优缺点:流域划分(慢但精确)；单调划分(快单不精确；层划分(速度适中))
//流域划分
// 准备区域划分，通过计算沿可行走表面的距离场。
rcBuildDistanceField(m_ctx, *m_chf)
// 将可行走的表面划分为没有孔洞的简单区域。
rcBuildRegions(m_ctx, *m_chf, 0, m_cfg.minRegionArea, m_cfg.mergeRegionArea)
//单调划分
//将可行走的表面划分为没有孔洞的简单区域。单调划分不需要距离场。
rcBuildRegionsMonotone(m_ctx, *m_chf, 0, m_cfg.minRegionArea, m_cfg.mergeRegionArea)
//层划分
//将可行走的表面划分为没有孔洞的简单区域。
rcBuildLayerRegions(m_ctx, *m_chf, 0, m_cfg.minRegionArea)
（6）轮廓生成（Contour边缘）
// 创建轮廓
m_cset = rcAllocContourSet();
rcBuildContours(m_ctx, *m_chf, m_cfg.maxSimplificationError, m_cfg.maxEdgeLen, *m_cset)
（7）轮廓网格生成（Poly Mesh）
//从轮廓集合构建多边形导航网格。
m_pmesh = rcAllocPolyMesh();
rcBuildPolyMesh(m_ctx, *m_cset, m_cfg.maxVertsPerPoly, *m_pmesh)
（8）三角形化（Triangulation）生成细节网格（Detailed Mesh）
//创建细节网格，允许访问每个多边形的近似高度。
m_dmesh = rcAllocPolyMeshDetail();
rcBuildPolyMeshDetail(m_ctx, *m_pmesh, *m_chf, m_cfg.detailSampleDist, m_cfg.detailSampleMaxError, *m_dmesh)
rcFreeCompactHeightfield(m_chf);
rcFreeContourSet(m_cset);
// 此时导航网格数据已经准备好了，你可以从m_pmesh访问它。
// 参见duDebugDrawPolyMesh或dtCreateNavMeshData作为如何访问数据的示例。

（9）从重铸多边形网格中创建绕行数据。
dtCreateNavMeshData(&params, &navData, &navDataSize)
m_navMesh = dtAllocNavMesh();

7. 导航网格创建（Runtime）

FRecastNavMeshGenerator
TArray<FBox> SupportedBounds;
		NavSys->GetNavigationBoundsForNavData(*DestNavMesh, SupportedBounds);


 UNavigationSystemV1::GetNavigationBoundsForNavData
	RegisteredNavBounds

UNavigationSystemV1::RegisteredNavBounds
	UNavigationSystemV1::PerformNavigationBoundsUpdate
	UNavigationSystemV1::GatherNavigationBounds()
			UNavigationSystemV1::AddNavigationBounds
			

ANavMeshBoundsVolume* V = (*It);
V->GetComponentsBoundingBox(true);
	AActor::GetComponentsBoundingBox
			UPrimitiveComponent* InPrimComp
			InPrimComp->Bounds.GetBox();

重写GetComponentsBoundingBox接口

//~ Begin Actor Interface

    virtual FBox GetComponentsBoundingBox(bool bNonColliding = false, bool bIncludeFromChildActors = false) const override;

//~ End Actor Interface

8. 导航网格绘制（Runtime）

8.1源码分析

初始化：

FNavigationSystem::AddNavigationSystemToWorld(*PlayWorld, LocalPlayers.Num() > 0 ? FNavigationSystemRunMode::PIEMode : FNavigationSystemRunMode::SimulationMode);
UNavigationSystemV1::OnWorldInitDone(FNavigationSystemRunMode Mode)
UNavigationSystemV1::DoInitialSetup()
UNavigationSystemV1::UpdateAbstractNavData()
UNavigationSystemV1::CreateNavigationDataInstanceInLevel(const FNavDataConfig& NavConfig, ULevel* SpawnLevel)
	ANavigationData* Instance = World->SpawnActor<ANavigationData>(*NavConfig.GetNavDataClass<ANavigationData>(), SpawnInfo);
			ANavigationData::PostInitProperties()
				ANavigationData::RequestRegistration()
				UNavigationSystemV1::RequestRegistrationDeferred(ANavigationData& NavData)

关联BP的UI

bDrawFilledPolys
bDrawNavMeshEdges	
		//override UActorComponent Interface
    + UPrimitiveComponent::CreateRenderState_Concurrent
    + FScene::UpdatePrimitiveTransform(UPrimitiveComponent* Primitive)
        // FSceneInterface interface.
        + FScene::AddPrimitive(UPrimitiveComponent* Primitive)
            //override UPrimitiveComponent Interface
            + UNavMeshRenderingComponent::CreateSceneProxy()
            //限制打包版本不可用
            #if WITH_RECAST && !UE_BUILD_SHIPPING && !UE_BUILD_TEST
                # UNavMeshRenderingComponent::GatherData()
                #if WITH_RECAST
                + FNavMeshSceneProxyData::GetDetailFlags(const ARecastNavMesh* NavMesh) 
                + FNavMeshSceneProxyData::GatherData
                    + ARecastNavMesh::GetDebugGeometry
                        + FPImplRecastNavMesh::GetDebugGeometry
                        	# FPImplRecastNavMesh::GetTilesDebugGeometry
                            + FPImplRecastNavMesh::GetDebugPolyEdges

收集数据方式一

方式一：ARecastNavMesh::GetDebugGeometry

FRecastDebugGeometry
TArray<FVector> MeshVerts;// add all the poly verts and detail verts
TArray<FVector> NavMeshEdges;// tile edges and navmesh edges
TArray<int32> AreaIndices
TArray<int32> BuiltMeshIndices;
//TArray<FVector> PolyEdges;

dtMeshTile
float* verts;///< The tile vertices. [Size: dtMeshHeader::vertCount]
float* detailVerts;	/// The detail mesh's unique vertices. [(x, y, z) * dtMeshHeader::detailVertCount]


ARecastNavMesh::UpdateNavMeshDrawing()
NavMeshRenderComp->GetVisibleFlag()
bool IsForcingUpdate() const { return bForceUpdate; }
bool UNavMeshRenderingComponent::IsNavigationShowFlagSet(const UWorld* World)


ANavigationData::bEnableDrawing
FNavigationSystemExec::Exec(UWorld* InWorld, const TCHAR* Cmd, FOutputDevice& Ar)
	  Cmd: CYCLENAVDRAWN / CountNavMem / RebuildNavigation / RedrawNav(RedrawNavigation)
UNavigationSystemV1::HandleCycleNavDrawnCommand(const TCHAR* Cmd, FOutputDevice& Ar)
UNavigationSystemV1::CycleNavigationDataDrawn()
	ANavigationData::SetNavRenderingEnabled(bool bEnable)
		AActor::MarkComponentsRenderStateDirty()
				UActorComponent::MarkRenderStateDirty()


TArray<ANavigationData*> UNavigationSystemV1::NavDataRegistrationQueue;
ANavigationData::PostInitProperties()
ANavigationData::RequestRegistration()
	UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
	UNavigationSystemV1::RequestRegistrationDeferred(ANavigationData& NavData)


SupportedAgents
TArray<FNavDataConfig> UNavigationSystemV1::SupportedAgents	
	UNavigationSystemV1::ApplySupportedAgentsFilter()
			FNavigationSystem::GetFallbackNavDataConfig()
				FNavDataConfig::FNavDataConfig(const FNavDataConfig& Other)
	
	UNavigationSystemV1::PostEditChangeChainProperty
			UNavigationSystemV1::SetSupportedAgentsNavigationClass
				SetNavDataClass

	FNavigationSystem::GetDefaultNavDataClass()
			Delegates.GetDefaultNavDataClass.Execute();	
	UNavigationSystemBase::GetDefaultNavDataClassDelegate()
		//---------可配置就好了	
		return ARecastNavMesh::StaticClass();

ARecastNavMesh 
	class ARecastNavMesh : public ANavigationData

NavDataSet
	TArray<ANavigationData*> UNavigationSystemV1::NavDataSet;

ANavigationData
ANavigationData::RenderingComp
	ANavigationData::ConstructRenderingComponent
				//---------可配置就好了
				return NewObject<UNavMeshRenderingComponent>(this, TEXT("NavRenderingComp"), RF_Transient);
UNavMeshRenderingComponent


//支持运行时动态生成判断--------工程配置:Runtime Generation
virtual bool SupportsRuntimeGeneration() const;
	return (RuntimeGeneration != ERuntimeGenerationType::Static);


UNavigationSystemV1::PerformNavigationBoundsUpdate

ANavigationData::OnNavigationBoundsChanged()
	ARecastNavMesh::ConditionalConstructGenerator()
		ARecastNavMesh::CreateGeneratorInstance()
			new FRecastNavMeshGenerator(*this);
		NavDataGenerator = MakeShareable((FNavDataGenerator*)Generator);
		ARecastNavMesh::RestrictBuildingToActiveTiles
			FRecastNavMeshGenerator::RestrictBuildingToActiveTiles
				TArray<FIntPoint> FRecastNavMeshGenerator::ActiveTiles;
					FRecastNavMeshGenerator::IsInActiveSet
	UNavigationSystemV1::AddDirtyAreas(const TArray<FBox>& NewAreas, int32 Flags)
		UNavigationSystemV1::AddDirtyArea(const FBox& NewArea, int32 Flags)
			FNavigationDirtyAreasController::AddArea

dtNavMesh
dtMeshTile* m_tiles;				///< List of tiles.
int m_maxTiles;					///< Max number of tiles.
	/// The maximum number of tiles supported by the navigation mesh.
	/// @return The maximum number of tiles supported by the navigation mesh.
	int getMaxTiles() const;	
	/// Gets the tile at the specified index.
	///  @param[in]	i		The tile index. [Limit: 0 >= index < #getMaxTiles()]
	/// @return The tile at the specified index.
	const dtMeshTile* getTile(int i) const;

FRecastNavMeshGenerator
/** Navigation mesh that owns this generator */
	ARecastNavMesh*	DestNavMesh;
const ARecastNavMesh* GetOwner() const { return DestNavMesh; }

	TSharedPtr<FNavDataGenerator, ESPMode::ThreadSafe> ARecastNavMesh::NavDataGenerator
			FNavDataGenerator* GetGenerator() { return NavDataGenerator.Get(); }



//在整个帧中存储标记为脏的区域，在Tick函数中每帧处理一次
TArray<FNavigationDirtyArea> FNavigationDirtyAreasController::DirtyAreas;
	FNavigationDirtyAreasController::Tick
			ANavigationData::RebuildDirtyAreas(const TArray<FNavigationDirtyArea>& DirtyAreas)
				FRecastNavMeshGenerator::RebuildDirtyAreas(const TArray<FNavigationDirtyArea>& InDirtyAreas)
	
	
	UNavigationSystemV1::ConditionalPopulateNavOctree()
			UNavigationSystemV1::AddLevelToOctree(ULevel& Level)
				FNavigationDataHandler::AddLevelCollisionToOctree(ULevel& Level)
					FRecastNavMeshGenerator::ExportVertexSoupGeometry
						OctreeController
						DirtyAreasController

收集数据方式二

方式二：FNavMeshSceneProxyData::GatherData

//测试拥代理方式获取网格数据：FNavMeshSceneProxyData
void UNavMeshRenderingComponent::GatherData(const ARecastNavMesh& NavMesh, FNavMeshSceneProxyData& OutProxyData) const
{
	const int32 DetailFlags = OutProxyData.GetDetailFlags(&NavMesh);
	TArray<int32> EmptyTileSet;
	OutProxyData.GatherData(&NavMesh, DetailFlags, EmptyTileSet);
}

TArray<FDebugMeshData> FNavMeshSceneProxyData::MeshBuilders;
	struct FDebugMeshData
	{
		TArray<FDynamicMeshVertex> Vertices;		//顶点
		TArray<uint32> Indices;					//索引
		FColor ClusterColor;						//颜色
	};

8.2绘制方法

参考：DrawDebugHelpers.h文章来源地址https://www.toymoban.com/news/detail-834078.html

/** Flush persistent lines */
		ENGINE_API void FlushPersistentDebugLines(const UWorld* InWorld);
	ENGINE_API void DrawDebugMesh(const UWorld* InWorld, TArray<FVector> const& Verts, TArray<int32> const& Indices, FColor const& Color, bool bPersistent=false, float LifeTime=-1.f, uint8 DepthPriority = 0);
/** Draw a debug box */
ENGINE_API void DrawDebugBox(const UWorld* InWorld, FVector const& Center, FVector const& Extent, FColor const& Color, bool bPersistentLines = false, float LifeTime=-1.f, uint8 DepthPriority = 0, float Thickness = 0.f);
	ENGINE_API void DrawDebugLine(const UWorld* InWorld, FVector const& LineStart, FVector const& LineEnd, FColor const& Color, bool bPersistentLines = false, float LifeTime=-1.f, uint8 DepthPriority = 0, float Thickness = 0.f);

到了这里，关于UE4 动态创建寻路网格的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！