UE NavigationSystem的相关实现

导航数据的构建流程

导航数据的收集

导航系统中绑定了Actor、Component注册完成以及取消时的委托，通过这些委托把数据及时更新到导航系统的八叉树结构中

导航系统的辅助结构DefaultOctreeController、DefaultDirtyAreasController分别承担了空间数据查询和置脏区域重新构建的任务，后者会把置脏数据最终投递到导航数据生成器的待处理结构里最终执行生成操作

开启构建操作（静态构建）

开启导航数据构建有几种情况：开启了动态导航、指令集开启、编辑器模式下的自动构建开启、调整导航偏移导航失效造成的重新构建。构建执行流程大致如下：

1. 当开启导航构建后导航系统首先重置掉待处理区域变更请求以及控制置脏数据的管理器，然后迭代所有的ARecastNavMesh执行同名构建函数RebuildAll

2. ARecastNavMesh首先会检查是否有正在构建操作如果存在操作则取消并重置，构建新的导航数据生成器实例并执行初始化，在初始化中进行有效区域边界更新并置脏所有的边界

3. 把边界数据投递到待处理结构中，然后通过执行构建生成器的EnsureBuildCompletion函数确认所有的构建工作完成，实质上是把所有的待处理结构打包成异步或者同步执行的任务来处理

4. 其中值得提及的是收集碰撞数据的方法：导航系统的辅助结构DefaultOctreeController中的NavOctree与DirtyBound做交叉检测，符合的则做数据收集

5. 使用瓦片生成器结构构建瓦片数据

6. 瓦片导航数据生成完成以后会把生成的数据添加到ARecastNavMesh数据真正的持有者DetourNavMesh（dtNavMesh）中

7. 动态导航数据与静态生成区别：动态导航模式下导航系统中挂载的Actor、Component注册取消委托受场景变更的影响会不断的更新，进而推动整个构建导航逻辑的执行（而且在动态模式下这些具有碰撞数据的实例会及时导出碰撞数据）。

生成瓦片数据的逻辑

当FRecastTileGeneratorTask异步执行或者同步执行一个构建的任务时FRecastTileGenerator::DoWork的调用就开始了，FRecastTileGenerator结构封装了生成单个瓦片的功能逻辑（封装Recast导航数据生成流程），DoWork的执行流程如下：

1. 完成几何模型碰撞数据收集和缓存，其中包括顶点数据、索引数据、可行走斜坡结构数据、修改器、导航连接、瓦片原生几何数据等

2. 构建高度场域数据（rcHeightfield）

3. 计算光栅化遮罩（对导航Modifier进行处理）

4. 光栅化或者说体素化三角形面（其中包括几何Transform数据从UE坐标到Recast的坐标转换）

5. 标记可行走区域

6. 体素边界过滤，防止边界外生成体素数据，通过InclusionBounds边界框判定（ApplyVoxelFilter）

7. Recast的生成过滤（WalkableClimb、walkableHeight）

8. 生成紧缩高度场域（CompactHeightField）

9. 根据walkableRadius剔除边缘（rcErodeWalkableAndLowAreas）

10. 根据选择的算法生成区域数据（rcBuildDistanceField）

11. 生成导航数据保存到瓦片生成器中

12. 回收脚手架结构内存

导航数据的查询

导航系统封装的查询接口

• K2_ProjectPointToNavigation 根据传入的点获取在NavMesh上的投影位置

• K2_GetRandomReachablePointInRadius 获取指定半径内随机的一个导航可达点位

• K2_GetRandomLocationInNavigableRadius 在给定的原点半径内的导航空间中生成一个随机位置

• GetPathCost 获取路径消耗，不推荐使用

• GetPathLength 获取路径长度， 不推荐使用

• FindPathToLocationSynchronously 同步地获取两点间的导航路径

• FindPathToActorSynchronously 同步地获取到达指定Actor的导航路径

以K2_GetRandomReachablePointInRadius为例说明导航数据查询路径

1. 调用核心ARecastNavMesh的GetRandomPointInNavigableRadius函数

2. ARecastNavMesh很多时候是空壳逻辑它会把逻辑转交给FPImplRecastNavMesh

3. FPImplRecastNavMesh结构的ProjectPointToNavMesh函数会构建出一个dtNavMeshQuery查询结构来完成Ploy2D的相关查询

导航系统的配置参数说明

属性名字	属性描述
DefaultAgentName	默认的导航代理名字，用于适配、查找默认的导航配置、导航数据,为空的情况下默认会把代理配置中的第一项作为默认配置
CrowdManagerClass	定义导航系统使用的自定义CrowdManager基类，目前不需要修改
bAutoCreateNavigationData	是否自动创建导航数据，通常情况下会在地图加载完成时、导航体积发生变更执行操作
bSpawnNavDataInNavBoundsLevel	是否允许在子关卡中生成导航数据，否则在持久关卡中创建
bAllowClientSideNavigation	是否允许客户端开启导航，默认客户端导航模式是关闭的，关闭的情况下整个导航系统不会创建
bShouldDiscardSubLevelNavData	是否要丢弃子关卡中的导航数据，该操作在地图加载完成后通过委托回调进行检测完成。如果是勾选状态则整个子关卡中的RecastNavMesh会被销毁占用的内存会被释放
bTickWhilePaused	当世界关卡处于Paused状态时是否要停止导航系统的Tick
bInitialBuildingLocked	在导航系统初始化完成或者导航系统重新加载完成的时候是否锁定导航系统的构建，如果为true只有在释放锁定标记后才能进行导航数据构建
bSkipAgentHeightCheckWhenPickingNavData	在通过NavConfigProps进行导航数据匹配时，是否忽略对代理高度的检查
DataGatheringMode	影响导航数据收集，注释说设置在构建碰撞信息时应如何收集导航数据。它的实质是在世界场景下Actor中的组件注册完成后导航系统中的OnComponentRegistered会被调用进而执行RegisterComponentToNavOctree，最终会执行到AddElementToNavOctree该函数会调用FNavigationOctree::AddNode函数，这个函数是最终的调用，它会执行ComponentExportDelegate委托的绑定，而其中绑定的是几何导出的逻辑处理FRecastNavMeshGenerator::ExportComponentGeometry
GeometryExportVertexCountWarningThreshold	当正在执行导出的数据结构中，定点数据容量大于此值时会产生日记记录，可参见ValidateGeometryExport
DirtyAreaWarningSizeThreshold	当该值为正值，向置脏控制器中添加的置脏区域（2D）大于该值时，产生警告日志
GatheringNavModifiersTimeLimitWarning	如果 GatheringNavModifiersWarningLimitTime 为正数，如果调用 GetNavigationData 所花费的时间超过 GatheringNavModifiersWarningLimitTime，它将打印警告
bGenerateNavigationOnlyAroundNavigationInvokers	是否仅在指定的目标对象周围生成导航数据,一旦开启全图可导航,依赖于导航动态生成,依赖于NavigationInvokerComponent
ActiveTilesUpdateInterval	激活的Tiles更新间隔依赖于bGenerateNavigationOnlyAroundNavigationInvokers
SupportedAgents	支持的代理导航配置
SupportedAgentsMask	导航系统对支持的代理控制

导航数据查询规则

通过导航配置FNavAgentProperties结构查询导航数据实例时会发现该结构的IsEquivalent函数起着至关重要的作用，而该函数中起决定因素的值是AgentRadius、AgentHeight，当这两个参数各自的差值小于默认精度5.f则认为这两个导航代理配置是等价的，因此有以下匹配规则：

1. AgentToNavDataMap中通过FNavAgentProperties类型的Key查询到指定的NavData返回

2. 如果无法查询到最佳匹配项则按照最优匹配原则获取指定导航数据配置查询AgentToNavDataMap返回

所有NavData实例都会在AgentToNavDataMap、NavDataSet中注册

WP情况下对导航的影响

WP下多了对区域导航数据的流入流出支持，它的核心实质是根据导航数据构建支持流入的Actor实例ANavigationDataChunkActor，该实例中保存了生成的导航数据URecastNavMeshDataChunk（TArray Tiles）。当该Actor实例被装载时携带的导航数据会替换掉DetourNavMesh中的Tile数据，卸载的时候又从DetourNavMesh移除。

Navigation Mesh参数说明

属性名字	属性描述
CellSize	水平方向上体素尺寸tiles大小应设置为每侧32到128个cells之间。这将在运行时重建tiles时提供最佳性能
CellHeight	垂直方向上体素尺寸
AgentRadius	代理半径
AgentHeight	代理高度
AgentMaxSlope	代理可以移动的最大斜率（角度）
AgentMaxStepHeight	Agent的可攀爬高度
MinRegionArea	允许形成孤岛区域的最小单元数
MergeRegionSize	分水岭算法中跨度计数小于此值的任何区域都将与更大的区域合并
MaxSimplificationError	细节网格表面偏离高度场的最大距离
TileSizeUU	单个tile的大小
TilePoolSize	NavMesh可以容纳的最大图块数
bFixedTilePoolSize	如果为真，NavMesh将为Tile分配固定大小的容量，开启以支持流式传输
MaxSimultaneousTileGenerationJobsCount	设置一次运行的异步瓦片生成器的数量限制，也用于一些同步任务
TileNumberHardLimit	导航网格图块数量的绝对硬性限制。在使用带有navmesh的大地图进行修改时要非常非常小心。一个空的tile需要176个字节，并且空的tile是预先分配的
DefaultMaxSearchNodes	指定执行导航查询时使用的A*节点的默认上限限制
DefaultMaxHierarchicalSearchNodes	指定执行分层导航查询时使用的A*节点的默认上限限制
RegionChunkSplits	用于区域分区的块分割数（沿单轴），仅用于ChunkyMonotone算法
LayerChunkSplits	用于区域分区的层分割数（沿单轴），仅用于ChunkyMonotone算法
bSortNavigationAreasByCost	控制导航区域在导航网格生成期间应用到导航网格之前是否按成本排序。 当区域重叠时，这是相关的，我们也希望区域成本表达区域相关性。 将其设置为 true 将导致区域按成本排序，但它也会增加导航网格生成成本一点
bIsWorldPartitioned	是否是world partitioned map
bPerformVoxelFiltering	是否执行体素过滤
bMarkLowHeightAreas	标记上方自由高度不足的区域，而不是将其切掉（仅适用于使用替换模式的区域修改器）
bUseExtraTopCellWhenMarkingAreas	应用于导航网格时，将区域导航修改器的边界顶部扩展一个单元格高度
bFilterLowSpanSequences	如果跨度上方的间隙小于指定高度，则将可步行跨度标记为不可步行。
bFilterLowSpanFromTileCache	如果设置，只有具有相应区域修改器的低高度跨度将存储在图块缓存中（减少内存，如果没有完整的图块重建就无法修改）
bDoFullyAsyncNavDataGathering	navmesh 数据收集永远不会发生在游戏线程上，只会在后台线程上完成

导航数据的内存占用

NavOctree memory ：导航八叉树的空间占用

ARecastNavMesh memory : DetourNavMesh中的所有瓦片结构内存总和 + 激活路径分配的内存（ActivePaths）+ 支持的区域结构分配的内存（SupportedAreas）+ 查询过滤器分配的内存（QueryFilters）+ 区域映射Map分配的内存（AreaClassToIdMap）+ 导航生成器内存占用（待处理任务数据结构大小 + 生成器结构本身大小 + 运行时任务结构大小 + 瓦片构建器分配的内存总和）

导航数据生成相关验证

多代理下的导航数据验证

支持的代理越多产生的数据容量越大，而且不同的代理配置生成的数据容量也是不同的