图形引擎实战：寻路从接触使用到改造的征途

一、项目介绍

大家好，我是来自搜狐畅游引擎部的codemouse，这次是分享关于3D世界寻路的生成方法，以及对寻路生成过程的一个改造。

项目需求：

1. 需要寻路导航面根据场景中的积木的修改，实时进行变化。

2. 识别一个较为平坦的区域作为大路使用。

3. 寻路导航面的多边形过多，优化减少，增加寻路性能。

4. 需要寻路支持超大场景8公里*8公里。

二、寻路的开始接触

突然有一天，老大跟我说：咱们要做3D世界做寻路了，你去看下navMesh寻路吧，该navMesh是基于体素去生成的寻路导航面，去把它看懂，后面我们要给寻路路面挖洞，做道路识别。于是我的navMesh寻路生涯开始了。

我赶紧去github上下载了一版新版的代码，并根据代码中测试样例开始研究什么是navMesh寻路，感受学校时候学习的深度搜索和广度搜索的寻路有什么区别，开始接触起了项目级别的寻路。

navMesh项目链接（https://github.com/recastnavigation/recastnavigation）

三、寻路的钻研

拿到源代码后，找到测试运行样例，先运行看看。

映入眼帘，可以看到在建筑物可行走的表面上，铺上了一层地毯一样的东西，寻路的话还可以给出一条距离最近的路径。于是觉得可以如何给出一条路径下手，开始将使用断点调试的方式，找到对应寻路的部分，发现每次寻路都会找出很多的多边形，在这些多边形中通过类似于拉绳子的方法（漏斗算法）得到一个最短路径。

那么这些多边形又是怎么生成出来的呢？于是我带着这个问题开始研究这个寻路的导航网格面的生成过程。

四、寻路的生成

从百度上，有可以直接找到关于navMesh的生成过程，在大致的阅览过后，才发现学生时代学习的数学是真的有用，这里面涉及到了几何数学和高数等知识，感概学生时代没白学，还好自己有好好听过课，数学真好用。

在对其生成过程有了一定的了解，然后观看其真正的源代码，在看过之后，对体素这个系统有了更深刻的认知，了解其是从一个obj对象（构建立体的点面集合）转成了体素对象，然后从体素层面转成几何关系，并将这些几何关系存储到数据结构中，最终寻路运用这些几何关系，找出最终的寻路路径。

我接触这个项目的体会，编程语言的基本功底要好，可以熟练使用编程语言（c/c++），并阅读别人的代码，还要快速学习使用新语言(c#，展示用)。数学功底也得有一些，例如高数，几何数学等。还有读文档的能力。

构建过程的讲解链接（http://www.critterai.org/projects/nmgen_study/regiongen.html）

从我的理解中，生成的过程大体上分为这几个步骤：

1. 将3D世界光栅话，有点类似于2D平面的那种像素点的概念，不过这个是3D世界的像素点。

2. 由于体素场景已经单位化了，在获取体素的反体素（没有体素的区域）后，就可以很方便的通过模拟人的高度和攀爬高度计算体素周围九宫格范围内，与自身体素的联通关系。得到这个联通关系，使用例如分水岭算法Watershed partitioning（暴力）的区域连接算法，利用相邻信息把区域连接起来。就可以得到如下图。

3. 生成轮廓，将得到区域后，将区域边缘边连接起来，形成一个大的轮廓。如果我们回到向量空间的话，我们需要的是顶点，而非边界。顶点的(x, z)值很容易确定。对于每条边界，我们取它的顺时针方向的区间的顶角的(x, z)值。

4. 简化轮廓，简化的时候有一个阈值（最大偏离值），用于决定要去除偏离多远的锯齿。

5. 生成多边形。通过数学算法，将简化后的轮廓划分出多边形来，此刻也就是NavMesh导航的寻路数据了，当然还可以继续做出形成细节网格，也就是打上高度补丁。

五、项目的改造

#寻路导航面根据场景中的积木的修改，实时进行变化

在了解了寻路导航面的生成过后，可以找到，他是通过将场景体素化，然后计算体素之间的联通关系，得到联通区域，再将其化为轮廓，再将转换为多边形的一个过程。

了解了这一点之后，其实可以大致分为两个思路：

1. 直接从最终的寻路导航面出发，修改当航面的几何多边形。本质上，navMesh存储的是多边形之间的相邻关系，只要对多边形的形状在几何上进行修改，对导航面挖出积木形状的坑来，并将积木形成的导航面与场景导航面，就可以完成该任务。（操作较为复杂，积木较多后，导航面维护困难，简单实现挖坑发现时间效率上也不如重新生成，也许是我写的不好）。

2. 对体素层面进行修改。在生成的时候，体素场景中被判定为不可行走的区域和没有体素的区域不会生成体素，因此在积木添加后，给体素场景添加上积木的体素，然后在生成寻路导航面就可以完成需求。

#识别一个较为平坦的区域作为大路使用

为了让角色寻路的时候，尽量行走在大马路上，项目上需要对场景中较为平坦的区域进行识别，同时在寻路系统中，可以对区域进行打标记，对某些标记有优先行走权，这样就可以使角色尽量行走在大马路上。

在和同事讨论实现方法的时候，想到一个可以通过数学上的平方差算法，就是该体素与周围体素的高度差的平方差越低，说明越平，通过这个原理，设定一个阈值，只要体素与周围体素的平方差大于阈值则认为该体素块不是个平坦区域的体素，给不是平坦区域的体素打上标记即可。 通过这个完成识别平坦区域的操作。 由于已经打上了标记，在生成的寻路导航的多边形上也存在这个标记，因此在寻路的时候，可以优先的选择该区域作为寻路的路线。

#寻路导航面的多边形过多，需减少，增加寻路性能

在寻路网格的生成的过程中，因为是根据体素系统数据来的，如果体素数据杂乱零碎，生成的寻路网格就会越复杂（多边形多），直接的影响到了寻路的效率。

项目那边在使用的过程中，发现我们的寻路对比其unity自带的navMesh导航，效率上和多边形数量上，差了些，希望我们能优化优化。

在清楚了需求后，也了解寻路生成的导航面过程，根据我对它的了解，是因为上面零零碎碎的不可行走体素，导致可完全联通区域过小，因此造成多边形的大量增加。并且这些零碎的体素数据在实际使用上，属于垃圾数据，可以直接清除，所以我们优化可以通过同化体素（可行走转为可不行走，不可行走转为可行走）的方式，将其变得规整而不影响实际的使用。优化方法如下。

在优化前的导航面：

优化的方法：

1. 去除掉细长无用数据（皱纹似的，斑点似的体素），让区块更加分明，就可以减少大量零散多边形的生成。通过体素之间的连通性，对其进行深度搜索，找到宽度较小的体素区域与周围进行同化。

2. 去除掉过小的孤岛，让小区块减少，让多边形可以形成的更大，减少小多边形碎片的生成，提升寻路的效率。通过广度搜索的方式，找到小的岛，将其与周围体素同化。

#寻路支持超大场景8公里*8公里

要支持超大场景的寻路，就需要将场景进行划分，不然navMesh在超大场景寻路压力过大，不一定能寻路出来（navmesh有寻路递归的池，寻路的多边形块超出池大小，就没办法寻路了），而且在超大范围寻路性能开销也是巨大的，因为navmesh里面做的是一个类似广度寻路的方式，只不过他找的是多边形块。因此我们设计了多navmesh的寻路结构。为了实现效果，我们实现了以下几点：

1. 场景划分，让navMesh变小。同时一个场景中划分出多个NavMesh。

2. 在逻辑上对navMesh之间做连通性处理。在设计上，我们做了一个navMesh查询器，在查询器中，实现对navMesh的寻路调用和 不同navMesh之间的跨区域连通性的记录，在发现寻路起点和终点不在同一个navMesh上的时候，就需要查询跨NavMesh之间的连通性关系，并在相应的navMesh中寻路，得到最终寻路的结果（相当于将多个寻路路径拼接起来），其中的难点在于跨NavMesh时候的联通区域的设计与维护。

3. 联通区域的设计，通过读取navMesh之间交接的体素的联通关系，可以清楚的找到哪些区域是可以达到对面的navMesh区域，只要维护好这个区间，寻路的时候，就可以做到跨navMesh的寻路。

下图为跨navMesh寻路的路线图，黑框与红框分别是两个不同的navmesh的区域，寻路的时候，得到的寻路结果拼接到一起，得到的最终的寻路结果是那条蓝线。

最后：个人学习心得

做需求的时候，也是深有体会，有一个人一起讨论着做和自己一个人埋头闷干差别很大。在制定功能的时候，也必须对自己手头上的东西有一定的了解，知道他能干什么，能干到什么程序，这样才能很好的和同事进行交流，分析可行性，和提需求方进行沟通。

从寻路上，我发现，一上手学一些新事物的时候，东西多不怕，可以先从使用开始入手，了解其最小结构，然后分解成一步一步的步骤去学习他里面的内容。例如生成寻路就分为，obj转体素，体素转反体素，然后转轮廓，在之后就是进入到几何方面，一步一步来。在不了解的地方可以进行断点调试，查看数据内容是否与预期相符，不理解的地方也可以翻翻文档或者看作者注释等。

欢迎加入我们！

感兴趣的同学可以在官网投递简历：

内推码：NTAI1kh