UE4 Navmesh剖析

UE4 ue4 Navmesh
Created At :
Comment:
  1. Navmesh原理
    1. 导航网格构建
      1. Recast流程
        1. 高度场
          1. 实心高度场
          2. 开放高度场
        2. 处理过程
          1. Voxelization( Create a solid heightfield from the source geometry)
          2. Generate Regions（Detect the top surface area of the solid heightfield and divide it up into regions of contiguous spans.）
          3. Generate Contours （ Detect the contours of the regions and form them into simple polygons.）
          4. Generate Polygon Mesh（ Sub-divide the contours into convex polygons.）
          5. Generate Detailed Mesh（Triangulate the polygon mesh and add height detail.）
    2. 寻路算法
      1. 寻路情况
        1. A*
        2. 行走优化（多边形网格）
        3. 行走优化(三角网格) - 拉绳算法（漏斗算法）

Navmesh原理

导航网格构建

  • 方式

    • 多边形裁剪
      • 多边形裁剪是直接对地形的多边形网格数据进行裁剪及合并，从而生成导航网格
      • havok引擎
    • 体素化
      • 体素化是对地形多边形网格进行栅格化，然后用这些“格子”重新生成导航网格
      • Recast(UE4,Unity)

  • UE4使用开源的recast其包括两个过程:Recast和Detour

    • Recast:将场景网格模型生成用于寻路的导航网格
    • Detour：利用导航网格进行寻路

Recast流程

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

高度场

实心高度场
开放高度场

处理过程

Voxelization( Create a solid heightfield from the source geometry)
Generate Regions（Detect the top surface area of the solid heightfield and divide it up into regions of contiguous spans.）
Generate Contours （ Detect the contours of the regions and form them into simple polygons.）
Generate Polygon Mesh（ Sub-divide the contours into convex polygons.）
Generate Detailed Mesh（Triangulate the polygon mesh and add height detail.）

寻路算法

  • 经过导航网格构建后的游戏场景,大致可以抽象成下面这样

    黑色是不可通过的地块，黄点是每个地块的中心点，黄线是将每个可通过地块的中心点进行了连接

连接条件是：如果两个可通过地块有邻边，则连接

寻路情况

  • 1.两个点在同一个地块内，走直线；
  • 2.其中一个点不在合法地块内，此路不通；
  • 3.两个点在不同地块，需要寻路。

A*

  • A算法详见:[A](https://sanctorum003.github.io/2021/06/03/Algorithm/A_Star/)

  • 对于情况3,一个简单的寻路算法就是A*算法

    • 其中,f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。
    • 其中,g(n)就是在Djikstra算法中计算的离起始点的距离,我们在Djikstra中取g(n)值最小的作为最高优先级
    • 其中,h(n)为A*算法的启发函数,计算节点n距离终点的预计代价(距离).取h(n)值最小的作为最高优先级
    • 对于在navmesh中,g(n)的计算可以通过每两个可通行块之间的连线(即图中黄线)来作为边
    • h(n)可以简单的用当前黄点与目标点直接连线

行走优化（多边形网格）

  • 左一连接每个块的中心点
  • 中间连接每个块最近边的中心点
  • 右边沿着边走

行走优化(三角网格) - 拉绳算法（漏斗算法）

©2019-2021 Sanctorum003

Built with Hexo and 3-hexo theme