Unreal 寻路网格

APSchmidt

Agent 的挑选

在项目设置内，Navigation System 内可以配置一些Agents
在寻路过程中，使用移动组件内的配置去匹配所有Agents

具体的函数如下：

1. const ANavigationData*UNavigationSystemV1::GetNavDataForProps(const FNavAgentProperties& AgentProperties)const

复制代码

匹配的规则：

首先判断 Preferred Nav Data 是否匹配：
1. return(PreferredNavData == Other.PreferredNavData || PreferredNavData.IsNull()|| Other.PreferredNavData.IsNull());
复制代码
然后用 AgentRadius 和 AgentHeight 进行匹配（默认-1，表示使用胶囊体），挑出最匹配的那个

单项更优判断：较大的优先（Agent 比目标大，至少不会出现卡住的情况），都比目标大或者小的情况下，较接近的优先若不符合两项都较优或相同，且之前的Agent不合法（两项有一项是小于目标的），则先使用半径判断，若相同再用高度判断，只有有一项是较优则替换所以，Agent的设置和实际的相同或者大一些注意这里两项相同的情况也会替换，而List本身是项目设置内的逆序，所以默认的Agent排在上面

1. ExcessRadius = NavIt.AgentRadius - AgentProperties.AgentRadius;
2. ExcessHeight = bSkipAgentHeightCheckWhenPickingNavData ?0.f:(NavIt.AgentHeight - AgentHeight);constbool bExcessRadiusIsBetter =((ExcessRadius ==0)&&(BestExcessRadius !=0))||((ExcessRadius >0)&&(BestExcessRadius <0))||((ExcessRadius >0)&&(BestExcessRadius >0)&&(ExcessRadius < BestExcessRadius))||((ExcessRadius <0)&&(BestExcessRadius <0)&&(ExcessRadius > BestExcessRadius));constbool bExcessHeightIsBetter =((ExcessHeight ==0)&&(BestExcessHeight !=0))||((ExcessHeight >0)&&(BestExcessHeight <0))||((ExcessHeight >0)&&(BestExcessHeight >0)&&(ExcessHeight < BestExcessHeight))||((ExcessHeight <0)&&(BestExcessHeight <0)&&(ExcessHeight > BestExcessHeight));constbool bBestIsValid =(BestExcessRadius >=0)&&(BestExcessHeight >=0);constbool bRadiusEquals =(ExcessRadius == BestExcessRadius);constbool bHeightEquals =(ExcessHeight == BestExcessHeight);bool bValuesAreBest =((bExcessRadiusIsBetter || bRadiusEquals)&&(bExcessHeightIsBetter || bHeightEquals));if(!bValuesAreBest &&!bBestIsValid){
3.         bValuesAreBest = bExcessRadiusIsBetter ||(bRadiusEquals && bExcessHeightIsBetter);}if(bValuesAreBest){
4.         BestFitNavAgent = NavIt;
5.         BestExcessHeight = ExcessHeight;
6.         BestExcessRadius = ExcessRadius;}
复制代码

Nav Data

在 Build Path 时，World 内会为每一个 Agent 生成一份 NavigationData，用于这种类型角色的寻路。具体流程是：A 在寻路时，根据（PreferredNavData、AgentRadius、AgentHeight）找到最符合的 Agent，然后使用该 Agent 对应的 NavigationData，进行路径搜索，最后找出 N 个点，就是寻找到的路径，然后 AI 就按照这条路径操纵移动组件进行移动（移动流程参考UE4：AI‘s MoveTo——代码分析）
而每个 Agent 有自己的 Nav Data Class，也就是说同样体型不同 Nav Data Class 的情况下需要两个 Agent，以飞行为例，我们需要两个 Agent，一个Walk，一个Fly，当需要进行飞行寻路时，就需要找到 Fly 这个 Agent。而 Fly Agent 生成的 NavigationData，就是用于飞行寻路的基础数据。
NavLinkProxy

有一些游戏机制（例如传送门），使得我们的路径没法使用单纯自动生成的寻路网格，需要增加一些处理。这种情形下我们会用到NavLinkProxy，将两个点之间联通（可选单向），我们的寻路就会将这两个点联通。
当AI到达点A时，会触发NavLinkProxy的Receive Smart Link Reached，这里我们可以自定义AI所需要触发的函数，例如响应传说。
寻路网格算法

https://zhuanlan.zhihu.com/p/359376662
https://zhuanlan.zhihu.com/p/74537236
Build Path 流程

在Build - Build Path，进入到UNavigationSystemV1::Build()
UNavigationSystemV1::Build()

void UNavigationSystemV1::SpawnMissingNavigationData()void UNavigationSystemV1::RebuildAll(bool bIsLoadTime)FNavDataGenerator::RebuildAll

就是对每个NavData，运行NavDataGenerator的RebuildAll函数
修改寻路网格

将 DirtyArea 塞入 DirtyAreasController 的 TArray<FNavigationDirtyArea> DirtyAreas
然后在 void UNavigationSystemV1::Tick(float DeltaSeconds) 内，调用

RebuildDirtyAreas(DeltaSeconds)DefaultDirtyAreasController.TickNavData->RebuildDirtyAreas(DirtyAreas)

将这些 DirtyArea 传递给 ANavigationData 的 FNavDataGenerator 处理
以Recast为例，就是将与 FNavigationDirtyArea 相交的 Tile 进行重建

---

注意，RebuildDirtyAreas(DeltaSeconds) 有一个前提是 IsNavigationBuildingLocked() == false，而当编辑器设置内的 Update Navigation Automatically 为 False 时，NavBuildingLockFlags 会加上 ENavigationBuildLock::NoUpdateInEditor，所以这种情况下除非主动调用 RebuildAll，也就是 Build - Build Path，否则NavData是不会变化的
动态修改寻路

DynamicModifiersOnly

将ProjectSetting内，NavigationMesh的RuntimeGeneration改为DynamicModifiersOnly
针对会移动的障碍，将障碍的StaticMeshComponent的Can Ever Affect Navigation改为False，并且给障碍加上NavModifierComponent。
注意，由于是障碍物，所以需要把NavModifierComponent的AreaClass改为NavArea_Null。
优化动态修改寻路

https://zhuanlan.zhihu.com/p/566846141
大世界下寻路网格的使用

1 老办法

直接加载所有的块，然后build path，注意，为了避免之后加载块导致的build path，在编辑器设置内关闭自动更新导航

2 只在周围生成

只在Invoker周围动态生成寻路数据
参考：
https://www.youtube.com/watch?v=DMe536X4IT0
https://www.youtube.com/watch?v=Smuy2d7y7mA&list=PLNTm9yU0zou7kKcN7091Rdr322Qge5LNA&index=47
第一个视频 核心是开启这个选项（还是需要寻路体积的）

下面的参数是更新周期
然后给中心物体（Pawn）加上Navigation Invoker Component

这样子就会在这个物体周围生成寻路数据了
内部有两个Tile Generation Radius和Tile Removal Radius，表示当区域进入Generation 范围就会生成，离开Removal 范围就会删除
第二个视频是说，如果目标太远了，就在周围找一个目标方向的点过去，靠这种方式慢慢接近
3 Open World

https://docs.unrealengine.com/5.0/en-US/world-partitioned-navigation-mesh/
https://docs.unrealengine.com/5.1/en-US/world-partition-in-unreal-engine/

Command: UnrealEditor.exe “C:\Users\user.name\Documents\Unreal Projects\MyProject\MyProject.uproject” “/Game/ThirdPersonBP/Maps/OpenWorldTest” -run=WorldPartitionBuilderCommandlet -AllowCommandletRendering -builder=WorldPartitionNavigationDataBuilder -SCCProvider=None