Recastnavigation解析

一、什么是Recastnavigation

Recastnavigation是一个用于Mesh导航、寻路方面的底层库，由Mikko Mononen制作，可以高效、精确地为游戏、仿真、虚拟现实等领域中的静态或动态环境生成导航网格。Recastnavigation利用了构建和搜索图形存储在网格上的路径的技术，并具有强大的问题空间分割，自适应代理大小，快速寻路和缓存以及多线程支持。Recastnavigation库开发始于2006年，目前支持Windows，Mac OSX，Linux和Android。Recastnavigation在游戏、工程、兵棋推演等领域广泛应用。

二、Recastnavigation的特点

Recastnavigation有哪些突出和独特的特性卓越，可以适应需求呢？以下是Recastnavigation的几个特征。

1. 三角形网格建模

Recastnavigation可以处理多边形，但最好使用三角形作为Recastnavigation的输入。在三角网格上可生成更准确的、没有分gon的或漏洞的多边形地形。

2. 智能拼接单元格：

Recastnavigation使用一维线网格，而不是二维网格作为底层数据结构，它有助于Recastnavigation在巨大的网格上解决舒适取出的问题。大规模的单个网格会导致性能问题和内存使用问题，Recastnavigation将代理单元格子分成矩形网格进行处理，从而可以处理大规模世界。Recastnavigation采用粘合Trimmed K-D树的局部化搜索，以避免在搜索路径时耗费太多时间。

3. 凸性体积的智能代理缩放

Recastnavigation可以根据需要自动缩放代理，以适应现实世界中的不同类型的代理。Recastnavigation可以自适应改变代理的大小，区分原始数据的地形和代理的大小之间的关系，可以产生更加精确的地图，并以更快的速度计算出路径。

4. 快速路径检索

Recastnavigation相对Agenta*和其他技术有较快的寻路算法。Recastnavigation缓存最短路径，缓存同一个代理请求的路径，这就降低了寻路时间。

5. 多线程优化:

Recastnavigation被优化了多线程，它的路径搜索算法非常可扩展，使Recastnavigation能够在具有多核心处理器的现代计算机上快速计算路径。

三、如何使用Recastnavigation

Recastnavigation的使用步骤如下：

1. 获取Recastnavigation

Recastnavigation可以在网上下载最新的源,当前最新的版本为1.5.1。开发人员需要将源代码包解压并将其包含在程序项目中。

2. 加载三角形网格

首先加载三角形网格。Recastnavigation最好处理通过三角形，因此在进行人工建模时，需要确保将建模顶点转化成三角形。将三角形网格导出为OBJ格式的文件，并在RCA滤芯中使用它。

3. 配置代理

代理有始于延续的过程。Recastnavigation通过代理评估代理的高度、宽度和长度，并为每个代理确定一个缩放半径。使用单角代理时，需要根据代理尺寸设置缩放环境变量，以保证代理可以在地形上充分运用。

4. 构建导航网格数据

输入三角形网格和代理尺寸，执行构建导航网格，Recastnavigation将生成和存储导航网格数据。

BuildContext ctx;
InputGeom inputGeom;
if (!inputGeom.loadMesh(&ctx, sceneFilename)
    return;//导入地形
float* bmin = inputGeom.getMeshBoundsMin();
float* bmax = inputGeom.getMeshBoundsMax();
float* vertices = inputGeom.getMesh()->getVerts();
int nverts = inputGeom.getMesh()->getVertCount();
int* faces = inputGeom.getMesh()->getTris();
int ntris = inputGeom.getMesh()->getTriCount();
rcHeightfield* solid = rcAllocHeightfield();
rcChunkyTriMesh* chunkyMesh = rcAllocChunkyTriMesh();
if (!solid || !chunkyMesh)
    return; //无法正常申请相应大小的内存

5. 搜索路径

在构建导航网格后，就可以开始在导航网格上执行搜索路径。根据需求设置起点和终点，调用寻路算法得到路径。

rcContext ctx;
rcPolyMesh* m_navMesh = nullptr; //导航网格信息
rcCompactHeightfield* m_chf = nullptr;  //高度图信息
rcConfig m_cfg;    //方格配置信息
rcPolyMeshDetail* m_pmdtl = nullptr;  //网格细节，用于寻路路径的偏移量
rcContext m_ctx;   //地形数据信息
dtNavMeshQuery* m_navQuery = nullptr;  //查询导航网格信息
//设置起始位置和目的地位置
dtPolyRef endPoly;
float endPos[3] = { dest[0], dest[1], dest[2] };
float startPos[3] = { start[0], start[1], start[2] };
dtStatus findStatus = m_navQuery->findNearestPoly(startPos, queryExtents, &filter, &m_startRef, 0);
dtStatus status = m_navQuery->findNearestPoly(endPos, queryExtents, &filter, &endPoly, 0);
//寻找路径
int npath = 0;
status = m_navQuery->findPath(m_startRef, endPoly, startPos, endPos, &filter, polys, &npath, MAX_POLYS);
if (status != DT_SUCCESS || !(npath > 0))
    return; //寻路失败

四、Recastnavigation的应用

Recastnavigation可以应用于虚拟现实、游戏、工程、军事仿真等众多领域。以下是Recastnavigation的一些应用示例。

1.游戏领域

显然，寻路是游戏的重要组成部分，Recastnavigation作为一款优秀、可靠的寻路引擎，已被许多游戏和游戏引擎所采纳。例如：Unreal Engine 4、Unity、Cry Engine等。

2.军事仿真领域

在军事仿真领域，Recastnavigation可以用于仿真计算中的路径搜索，以及部队、交通工具移动的指挥和控制。Recastnavigation在仿真领域的精度和可靠性更有优势。

3.虚拟现实领域

在虚拟现实领域，Recastnavigation可以为VR世界的导览和交互提供导航解决方案。

五、总结

Recastnavigation是一款优秀、高效、可靠的寻路引擎，并具有智能代理缩放、快速路径检索、多线程支持等优秀特点。Recastnavigation已广泛应用于游戏、工程领域、兵棋推演领域等多个领域。如果你需要一个高效且可扩展的寻路解决方案。那么，请尝试适用Recastnavigation。