导航系统教程：Recast和Detour

在现代游戏和3D应用程序中，导航系统扮演着至关重要的角色。本教程将介绍整个导航系统的工作流程，重点阐述Recast和Detour这两个核心组件。

1. 系统架构概述

整个导航系统的工作分为两个主要部分：

• Recast: 负责在三维场景中构建正确的寻路网格（NavMesh）。
• Detour: 使用寻路算法（如A*和Dijkstra）在构建的网格中进行寻路。

2. Recast的工作流程

在Recast的处理过程中，依次执行以下步骤：

1. Voxel化:

   • 将三维场景进行体素化，类似于二维场景中的光栅化。这一过程的主要目的是简化寻路中不必要的模型细节，以提高计算效率。

2. 区域过滤（Filter）:

   • 根据当前的导航配置，过滤出可行走的区域。通过设置可行走区域的参数，确保代理能够有效地在环境中移动。

3. 多边形生成（Poly）:

   • 将可行走区域按照一定规则切分为导航多边形。后续的寻路算法将在这些多边形基础上进行运算。

虽然以上步骤听起来简单，实际的代码实现却相当复杂。

3. 数据结构：rcHeightfield

在体素化后，整个场景将被存储在rcHeightfield结构中。该结构将场景划分为多个单元格，并在每个单元格中定义多个span，每个span代表在Z方向上的一小段体积。以下是rcHeightfield的基本结构：

/// A dynamic heightfield representing obstructed space.
/// @ingroup recast
struct rcHeightfield
{
    rcHeightfield();
    ~rcHeightfield();

    int width;           ///< The width of the heightfield. (Along the x-axis in cell units.)
    int height;          ///< The height of the heightfield. (Along the z-axis in cell units.)
    float bmin[3];      ///< The minimum bounds in world space. [(x, y, z)]
    float bmax[3];      ///< The maximum bounds in world space. [(x, y, z)]
    float cs;           ///< The size of each cell. (On the xz-plane.)
    float ch;           ///< The height of each cell. (The minimum increment along the y-axis.)
    rcSpan** spans;     ///< Heightfield of spans (width*height).
    rcSpanPool* pools;  ///< Linked list of span pools.
    rcSpan* freelist;   ///< The next free span.

private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcHeightfield(const rcHeightfield&);
    rcHeightfield& operator=(const rcHeightfield&);
};

4. 常用属性

在此Demo中，有三种不同的Sample模式可供选择：

• TileMesh: 将场景划分为多个Tile，以Tile为单位进行管理。
• SoloMesh: 只有一个Tile。
• TempObstacles: 类似于TileMesh，但支持动态阻挡物。

5. 导航代理属性

导航系统需要以下属性进行有效的寻路：

• Rasterization: 体素化时单元格的大小和span分层的高度。这些值与计算效率成正相关，而与NavMesh的精细程度成反相关。

  • 大体素和小体素的选择会影响寻路的效率和精度。

• Agent: 设置导航代理的宽高、最大可爬坡高度和最大可爬坡角度。这两个属性在过滤阶段用于判断区域是否可行走。

• Region: 生成的多边形轮廓，表示可导航区域的边界。

• Partitioning: 提供三种不同的分区方法，以满足不同的寻路需求。

• Filter: 用于判断区域是否可行走的过滤器。可以选择开启，Demo中包括三种过滤方法，后文将详细分析。

6. 总结

本教程介绍了导航系统的基本架构，以及Recast和Detour的工作流程。通过对体素化、区域过滤和多边形生成的理解，您可以更好地实现和优化导航功能。

相关算法：

多边形寻路算法，A星算法，选点，优化，路径平滑，漏斗算法，射线探测算法