UE的寻路系统

1. Navigation System简介

寻路系统，用于给AI或者自动寻路使用，目前没有测试过它针对大地图的效果如何，但是在小范围内的巡逻是没有问题的。
本小记是对官方文档简单的归纳。

2. 构建基础的寻路网格

把NavMeshBoundsVolume拖到场景中，并修改缩放。

按P可以可视化寻路网格

发现楼梯上的NavMesh绘制有点穿模，可以选择RecastNavMesh-Default Actor，在Display小节把Draw Offset设置成50或大于0的值。

勾选Draw Tile Bounds，可以显示网格的Tile。

在Generation小节，可以修改生成配置。

3. 如何修改寻路Mesh

使用Navigation Modifier Volumes, Navigation Proxy Links修改寻路Mesh。

3.1 Nav Modifier Volume

• 镂空

把Nav Modifier Volume拖到场景中，并修改缩放即可

• 修改权重

Nav Modifier Volume的Area Class，选择NavArea_Obstacle。

Area Class	Description
NavArea_Default	Volume区域内具有相同的寻路开销
NavArea_LowHeight	Represents an area that matches the conditions for traversal with a low height that prevents an Agent from traversing it. The Navigation Mesh will not generate navigation data inside this volume.
NavArea_Null	该volume里面，不能寻路
NavArea_Obstacle	在volume里面，寻路的开销很高

3.2 Navigation Link Proxies，可用于跳台/悬崖

把Nav Link Proxy Actor拖到场景。

选中场景中的Nav Link Proxy，把PointLinks[0].Left和PointLinks[0].Right拖到合适的位置

可以在它的Direction修改方向：Left to Right、Right to Left

3.3 运行时生成寻路网格

Unreal Engine有三种寻路网格的生成模式

Generation Mode	Description
Static	离线生成，存储在Level中，运行时不能修改
Dynamic	离线生成，存储在Level中。运行时，寻路相关的数据，可以以Tile为单位更新
Dynamic Modifiers Only	离线生成，存储在Level中。运行时，只有Navigation Modifiers，例如Navigation Areas, Navigation Links, 和动态物体，可以修改已存在的寻路网格的开销，或者阻挡区域。不能运行时生成新的寻路网格表现。该方法，因为可以缓存collision data，相对于影响Tile的方案，有50%的速度提升。建议高级用户使用该方案，并评估其优劣。

3.3.1 使用运行时生成（Dynamic Modifiers Only）

• 项目配置
  在Project Settings | Navigation Mesh | Runtime里面修改
  
  
• 给放到场景里面的Actor添加NavModifier后，它的运动，即可影响Nav Mesh

4. 自定义Area Class和Query Filters

4.1 自定义Area Class

主要作用：设定Nav Modifier Volume区域的寻路网格权重

创建Blueprint，派生成NavArea：

打开刚刚创建的蓝图类，可以修改Default Cost，可以修改Draw Color：

然后把场景中的Nav Modifier Volume的Area Class改成刚刚创建的NavArea蓝图类：

效果展示：

4.2 创建Area ClassQuery Filters

主要作用：让某个Actor，可以针对某种寻路区域AreaClass，有不同的开销。（如飞行的，优先空路开销低。船类，陆地有很大开销）
新建派生自NavigationQueryFilter的蓝图类：

为NavigationQueryFilter=蓝图类配置针对不同Area的Travel Cost：

选中场景中的Actor，给它的Filter Class，选择刚刚新建的NavigationQueryFilter：

5. 寻路系统中的避让

5.1 简介

避让，能够让寻路的对象，互相避让，避免卡住。
两种主要的避让算法是Reciprocal Velocity Obstacles (RVO)和Detour Crowd。

5.2 Reciprocal Velocity Obstacles (RVO)

RVO计算相邻的Agent的速度来避免碰撞。该系统会查找相邻的agent，并且在一个time step中认为agent都是常量速度。最佳的速度选择是是最匹配agent目标方向的最佳速度。

UE实现的RVO的优化，包括减少帧率的影响。也包括避免常量路径的重新计算，和包括一个优先级系统来解决潜在的碰撞问题。RVO没有使用Navigation Mesh来避让，所以它可以与Navigation分开使用。该系统包含在Character Movement Component里面。

5.3 Detour Crowd

Detour Crowd Manager系统处理避让，是通过使用自适应的ROV采样。它计算粗略的，有些偏移的，朝Agent的方向的速度采样，相对于传统的RVO有明显的提升。该系统还使用了可见性和拓扑路径来进一步改进避让。

Detour Crowd Manager系统是高度可配置化的，包含的选项有：采样模式、Agent最大数目，Agent的半径。该系统包含在DetourCrowd AI Controller类里面，并且可以给任意的Pawn类使用。

方法	描述	局限性
Reciprocal Velocity Obstacles（RVO)	– 带半径的Agents使用速度向量。 – 在Character Movement Component中。	1.相对于Detour Crowd Manager，配置化少很多。2. 只能在Character类使用。 3.没有使用Navigation Mesh来避让，所以可能会超过边界，
Detour Crowd Manager	带半径的Agents通过使用路径优化和速度向量来避障。-在DetourCrowd AI Controller类里面。 – 在Project Settings里面有固定最大数量的Agent。	在Project Setting中，agent数量有个最大固定值。

5.4 RVO的使用方法

在Character Movement上，选择Use RVOAvoidance，并配置参数：

5.5 Detour Crowd Avoidance的使用方法

在Actor上搜索 AI Controller：

把AI Controller换成DetourCrowdAIContrller：

配置参数的方法，在Settings > Project Settings > Crowd Manager：

6. Navigation Invoker，运行时在Agent附近生成Navigation Mesh

6.1 简介

在一些大的Level上，生成全地图的Navigation Mesh比较大，所以可以使用Navigation Invoker来运行时生成。
其生成只生成在Agent附近，并且可以限定Tile的数量

6.1 开启方式：Project Setting配置

Settings > Project Settings > Navigation System > Generate Navigation Only Around Navigation Invokers：

Navigation Mesh category > Runtime > Generation => select Dynamic：

给Actor添加Navigation Invoke Component：

可以配置参数，到Navigation Section上，配置Tile:

7. 优化

https://docs.unrealengine.com/5.1/en-US/optimizing-navigation-mesh-generation-speed-in-unreal-engine/

7.1 尽可能用更大的Cell Size和Cell Height

配置Cell的尺寸（尺寸越大越好，但是寻路精度可能会越差）:
Settings > Project Settings > Navigation Mesh > Generation（全局配置）：

局部配置方法，找到RecastNavMesh-Default Actor：

7.2 限制Tile Size

在运行时重建，以Tile为单位重建，Tile越大，重建的开销越高。

7.3 Mesh使用Simplified Collision

寻路系统使用每一个对象的collision data来生成寻路网格，所以对象的碰撞越简单，生成越快。建议Static Mesh使用Simple Collision，三角面要少。

7.5 减少能够影响寻路网格的对象

默认情况下，Actors和Static Mesh会影响寻路系统。禁用的方法 Details panel > Collision > Can Ever Affect Navigation，禁用之：

7.6 锁定和解锁Navigation Mesh生成

可以在loading阶段锁定不生成，等地图加载完毕后再生成

// 锁定
bInitialBuildingLocked  = true;

// 解锁，解锁后，会重建被标记为dirty的Tile
ReleaseInitialBuildingLock();

// 不想重建，可以阻止重建：
DefaultDirtyAreasController.Reset();

7.7 开启多线程Navigation Mesh生成

MaxSimultaneousTileGenerationJobsCount可以控制线程数。
受限于FRecastNavMeshGenerator::Init()。

7.8 Use Dynamic Obstacles with Full Dynamic Navigation Mesh Generation

You can mark Static Meshes and other Actors in your Level as Dynamic Obstacles. Dynamic Obstacles mark the Navigation Mesh surface where generation needs to be rebuilt. This prevents the entire Navigation Tile from being rebuilt.

Using this method is less costly than generating the full Navigation Tile and should be used when a Navigation Mesh surface is not needed on top of moving obstacles.

7.9 Use Data Chunk Streaming for Static Navigation Meshes Loaded in Sublevels

If the only changes to the Navigation Mesh come from loading and unloading sublevels, you can set the Navigation Mesh Generation Method to Static and use NavMesh Data Chunk Streaming, instead of using a dynamic Navigation Mesh.

With this method, the Navigation Mesh will be fully built in the editor and only the relevant parts will be loaded in and out at runtime.

8. 参考资料

https://docs.unrealengine.com/5.0/en-US/navigation-system-in-unreal-engine/

9. 友情链接

blog: https://www.cgsgood.tech/root_motion_simple/
语雀: https://www.yuque.com/cgsgood/dshx0b/qhqlmldu7s28o9bd
博客园: https://www.cnblogs.com/cgsgood/p/16890509.html