《Unity3D高级编程之进阶主程》第十章，地图与寻路(二) 寻路网格的构建

寻路网格构建

上一节我们了解了A星寻路的算法及其优化，A星寻路只是算法，需要配套的模块和工具链支撑，单独的一个A星无法运行在游戏项目中因为它只是一个算法。那么我们需要什么样的模块和工具链来支撑整个寻路系统呢，我们这节就来讲一讲寻路周边工具链中最重要的配套模块‘寻路网格构建’。

===

1.用二维数组构建虚拟的方形网格

最简单的也是最易于理解的网格构建方式要属二维数组网格，它是一个二维数组，每个元素就代表一个可行走位置，我们可以假设元素中数字0代表无障碍，1代表有障碍，或者也可以用数字代表障碍阻碍难度，比1大的数字代表更高的障碍难度，数字越大障碍难度越大，到达某个数字比如999则认为该障碍难度无法跨越。

举个二维网格的例子：

	[0][0][0][0][0][0]
	[1][1][0][0][1][1]
	[1][1][0][1][1][1]
	[0][1][0][0][1][1]
	[0][0][0][1][1][1]

这是一个 5 * 6 的二维数组，0代表无障碍，1代表有障碍。我们能从中很清晰的看到这张地图中有哪些是障碍点，张地图点都是连同的我们从任意一个可行走点出发都能到达任意终点，我们可以想象寻路时一步步按照方格的方式去行走。

用二维数组代表地图相对比较抽象，它需要与地图的尺寸相匹配，怎么与地图真正的关联起来呢？我们在脑海中需要把一整块地图也切成 5 * 6 这样30块地，比如这个张地图总共大小为 50米 * 60米 的大小，假如左下角为[0,0]位置，我们从0，0点开始，从10，10点到0，0点为一个方块与[0,0]这个点关联，从坐标10，10到坐标20，20为另一个方块与[1,1]这个点关联，从0，10点开始，10，20点到0，10点的方块与[0,1]这个点关联，依次类推。

在地图上每个10 * 10大小的一块正方形的区域都与数组关联，这样我们在用A星寻路中以及寻路后的结果都可以对应到地图上的坐标。

比如，我们寻路到从[0,0]点开始，到[1,4]点的路径为，[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4]，反应到地图上时，是0，0点开始移动，先移动到第一个方块也就是(0,0)到(10,10)这个方块的中点，也就是坐标(5,5)的点位上，再移动到(10,0)与(20，10)这个方块区域的中点上，即(15,5)坐标点位上，再移动到(20,0)与(30,10)这个方块区域的中点上，即(25,5)坐标点位上，依次类推，直到移动到最后一个点位，即(10,40)与(20,50)这个方块区域的中点上，即(15,45)这个坐标上，到达终点。

因此A星寻路结束后，给出了[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4]，即数组上的坐标路径，在实际地图中则移动的路径为(5,5)->(15,5)->(25,5)->(25,15)->(25,25)->(25,35)->(25,45)->(15,45)的坐标点位顺序。

相当于把整个地图想象成一个矩形，把矩形横切N刀，竖切N刀，成了一个与二维数组匹配的方块地图，每个方块与数组中的一个元素相关联，当我们使用A星算法从数组中算出一个具体的路径时，可以根据这个数组中的路径，来匹配地图上的点位，即方块的中点。

在数组与地图的匹配中，如果这个地图很大，但数组的大小很小，就无法实现细腻的路径与障碍，所以我们需要在内存占用量与地图寻路细节之间权衡。多大的数组与当前的地图才能匹配的更好呢，我们的数组不能过大因为过大的数组会造成内存的浪费，又不能过小因为过小的数组使得地图的障碍细节无法得到完美的体现。所以我们在决定数组多少的时候，需要考虑的是整个地图的大小，以及最小障碍物为多大，来决策究竟需要用多大的数组。

可视化地图编辑界面

这些切割与关联都是由我们的脑袋抽象出来的，毕竟我们在做游戏项目的时候，抽象的东西如果无法可视化的话，就会变得难以灵活运用，至少是难以灵活的编辑和扩展，于是可视化编辑也是一个比较重要的节点。

我们可以用最简单的方法Excel方式，建立一个Excel，在Excel表中填入一个与数组相等大小的矩形方格块，在方格内填入颜色或数字，绿色代表可行方块，红色代表不可行方块。这样在Excel内就可以设置地图的元素以及障碍物，可行走与不可行走区域一眼就能知道。那些标记为红色的方格是障碍物，那里是不可通行的，那些标记绿色的地方为空地，那地方是可通行的，整个地图下来哪些地方不可通行，哪些地方可通行一目了然。最后我们把这个Excel里的数据导出到文件，再在游戏中读取文件中的数据，就能得到我们需要的地图二维数组的可行走与不可行走的地图数据。

除了Excel，我们还可以使用UnityEditor提供的编辑器API编写的地图编辑窗口，把地图大小，方格大小，障碍物等以可视化的形式放在 UnityEditor UI编辑窗口中，并附上保存数据到文件和从文件读取地图数据的功能，这样的地图编辑窗口就能更形象的体现地图的元素。

如果这种可视化还不够，就在具体的3D场景中的地图上做些编辑功能，先要把整个地图加载并渲染在画面上，然后在地图上用颜色方块的方式画出不同颜色的块状，用具体地图为背景来编辑地图障碍和可行走区域。当然这也带来更加多的代码的编写和维护工作，但也同时是非常值得的可视化网格编辑器，为设计师提供了更加良好的编辑工具，这对游戏的创新设计会有更好的支持作用。

除了以上形式的地图编辑工具，也可以用类似地形贴图的形式来做为可行走点的依据，就像地形高度图那样，我们也可以用一张图来存储障碍数据。用一整张1024 * 1024图代表一整个地形的大小，或者也可以为 2048 * 256等按不同需求规格的大小，每个像素点代表二维数组的一个元素，(255,255,255)白色代表可行走区域，(0,0,0)黑色为不可行走区域，那么这张图就可以压缩成只有RGB通道的8比特的图，也加入更多元素，泥潭，沼泽等等分别用其他颜色代表，这样就可以用图片代替了Excel的数据，Unity3D自带的地形就是这么做的，它的地形图中包括了一张高度图和地图元素图，贴图中每个颜色像素都代表一种植被。当需要加载二维数组作为可行走数据时，则加载该图片读取像素中的每个元素录入到内存中，然后就可以依据内存中的二维数组来判定是否是可行走区域，以及相邻的格子是否是障碍物的判断。

由于一维数组在分配内存块时的紧凑度往往比二维数组要来的好，用一维数组来读取索引中的数值会更加的快，因此我们常常使用一维数组来代替二维数组，在调用索引时也只是多了一个简单的乘法和加法的操作，即 二维数组 [a, b] 等于 一维数组 [a * width + b]，这样一来只是整个内存访问都是连续的而不再需要内存地址的跳转，这有利于提高指令缓存命中率，加速了指令运算。

2.用路点系统构建寻路路线图

用二维数组的方式来构建寻路的基础数据有一定的局限性。当场景特别大，我们就要存储特别大的一个数组，编辑可行走区域的工作量也有所提高。假设我们的地图场景有 2048 * 2048 个数组这么大甚至更大，我们在制作可行走区域时就要把所有的障碍点都细致的设置一遍这样的工作量比较大。除了数组太大和需要编辑的工作量扩大外，二维数组下的寻路路径最多是8方向的，上，下，左，右，左上，左下，右上，右下，寻路后的行走时也会感觉比较不真实，感觉是直来直去行走方向，要么90度方向行走，要么180度方向行走，要么45度方向行走，没有其他角度的行走姿势，让人感觉不真实，在像素游戏上还感觉不出什么来，但在3D地形中则会感觉明显的怪异。

路点系统就弥补了一些二维数组形式的缺点。路点系统是一个易于理解的系统，它由很多个点构成，这些点我们称它们为路点，即路上的点。我们将路点放入地图中，并为每个路点标记ID，以及与哪些路点相连的数据。我们在地图中放入了很多个路点，并且为这些路点配置了连线，于是就有了这幅画面：

	缺少图片

地图中每个路点都会有与其他某些路点相连接的线，我们可以称它们为路线，由路点与路点之间连线而成。如果把地图里的路点和路线铺设的更加复杂一点时，所有的点和线都拼成了一张网：

	缺少图片

这张网中，只要我们得到某个点，就能根据这些路点和路线，用A星的算法来寻路到目的地。图中当起点为A，与起点最近的路点寻路到与终点最近的路点的一条路径。如图：

	缺少图片

路点系统相对容易理解，因为它本身就是点与点之间的连路，我们在制作时也需要一些可视化的编辑器的支撑，因为所有的路点都需要在既有的地图上编辑，所以编写一个专门的地图编辑器也是必不可少的，没有地图编辑器至少也需要路点编辑器，可用来保存路点数据到具体的数据文件、从文件加载路点数据，以及增加路点，减少路点，添加和减少路点连接信息等功能。

路点系统相对简单，它的缺点也是比较严重的。当我们大范围设置可行走区域时它任然需要大量的工作来编辑可寻路的路点信息与连线。它的寻路方式也无法识别碰撞而只能用路点的形式来绕过障碍。当在大块空地上做寻路时，需要在这个大块空地上添加比较多的路点，才能平滑的适应各种寻路路径。

3.平面三角形网格的构建

路点系统直观、门槛低、上手简单，一般情况下路点的数量相对比其他方式的网格少很多，因此内存消耗和CPU消耗都比较少。但它的缺点也比较大，行走路线的平滑程度依赖于添加的点的密度与形状，更糟糕的是它无法识别障碍区域，行走的路线也依赖路点之间的连线。三角形网格形式的寻路网格就很好的解决了路点系统的缺陷，它用算法自动生成的网格，无需手动编辑就能避开障碍区域。

那么三角形寻路网格是怎么生成的呢，这个问题在计算机图形学里叫做 “平面多边形的三角剖分问题”，意思是说我们在一张平面图上有很多的颜色，这些颜色就形成了很多的点，根据这些点将这幅图分解为由许多三角形组成的多边形。

平面多边形的三角形剖分问题是计算几何研究的一个基本问题，它广泛应用于模式识别、图像处理、计算机图形学以及机器人领域。一方面，三角形作为最简单的平面图形，较其他平面图形在计算机表示、分析及处理时方便得多。另一方面，三角剖分是研究其他许多问题的前提。

Delaunay三角剖分算法是一种三角剖分的标准，它是由前苏联数学家Delaunay提出来的：“对于任意给定的平面点集，只存在着唯一的一种三角剖分方法，满足所谓的“最大-最小角”优化准则，即所有最小内角之和最大。”这种剖分方法遵循“最小角最大”和“空外接圆”准则，“最小角最大”准则是在不出现奇异性的情况下，Delaunay三角剖分最小角之和均大于任何非Delaunay剖分所形成三角形最小角之和，三角形的最小内角之和最大，从而使得划分的三角形不会出现某个内角过小的情况，比较有利于有限的后续计算。“空外接圆”准则是Delaunay三角剖分中任意三角形的外接圆内不包括其他结点。因此在各种二维三角剖分中，只有Delaunay三角剖分才同时满足全局和局部最优。

Delaunay三角剖分算法由好几种，但都遵循Delaunay三角剖分特点，即其剖分后的多边形里的三角形必须满足：

	1.除了端点，三角形的边不包含其他任何点。

	2.除了在点上的连接，没有任何一条边是相交的。

	3.所有的面都是三角形，且所有三角形的合集是所有点集合的凸包。

第一、二点要求三角形的边上没有任何其他的点和相交的线，第三个说的是所有的点都是三角形的点并且最后所有三角形所形成后是个凸多边形。

Delaunay三角剖分算法有翻边算法、逐点插入算法、分割合并算法、Bowyer-Watson算法，它们都只适用于凸多边形的三角剖分。这里我们仅对Bowyer-Watson算法进行讲解。Bowyer-Watson算法的基本步骤是：

	1.构造一个超级三角形或多边形，把所有数据点都包围起来。

	2.依次逐个加入新的顶点，找到包含新顶点的所有外接圆对应的所有三角形。

	3.删除包含在所有外接圆中的边，这时围绕新插入的点构成了一个凸多边形。

	4.将新插入的点与这个凸多边形的所有点相连，形成多个新的三角形。

	5.返回到第二步，继续加入新的点直到所有顶点增加完毕则结束。

我们用图示来说明算法步骤：

	[缺图1]

	[缺图2]

	[缺图3]

	[缺图4]

	[缺图5]

这5张图清晰解释了Bowyer-Watson算法的步骤，从把所有的散点用凸多边形包围起来到插入新点再到形成删除边形成新的三角形最后将所有散点都加入进来形成了三角形网格。

可惜Delaunay三角剖分只合适凸多边形，对于我们在场景中凹形区域占到了大量的面积和数量则需要另外考虑其他算法，Delaunay则可以用于其他凸多边形的情况我们将在后面介绍。现在我们需要的不只是凸多边形和凹多边形的三角形剖分，也需要考虑凹凸多边形中含有‘洞’(即不规则多边形阻挡物)的情况，甚至还有更复杂的‘洞’中有孤岛的情况，因此单单是凸多边形的三角形剖分不能满足我们实际的需求。

2002年 David Eberly 在《Triangulation by Ear Clipping》论文中提出了用切耳法构建简单多边形的三角化，正好解决了我们的问题。

切耳算法

Ear Clipping 切耳算法是一个简单实用的三角形分割算法，其步骤可以简单的分为三步，在解释三步骤之前，我们先解释下几个名词的意思。

	1.简单多边形是，所有顶点都是顺时针或者逆时针排列的顶点，每个顶点只连接两条边，边与边之间没有交叉的多边形，就叫做简单多边形。

	2.耳点，耳点的意思是，多边形中相邻的三个顶点V0,V1,V2形成的三角形里，不包含任何的其他顶点，并且如果V1点是凸点，即V0-V1的连线与V1-V2的连线之间形成的夹角小于180度，则认为V1是耳点。所以一个由4个顶点组成的多边形中，至少有2个耳点。

	3.耳朵三角形，三角形顶点中有耳点的就叫耳朵三角形。

我们知道耳点和耳朵三角形再来看这三步骤就容易理解的多，其三步骤为：

	第一，找到一个耳点。

	第二，记录这个耳朵三角形，然后去掉这个耳朵点，在剩余的顶点中，继续回到第一步

	第三，直到剩下最后3个点形成一个三角形并记录下来，把所有记录的三角形拼接起来就形成了三角化网格。

经过这三个步骤的计算，所有的耳点都被切掉后，再把所有记录的三角形拼装成三角形网格，就完成了整个三角形剖分步骤。

	缺少图片

多边形含‘洞’的情况

除了普通的简单多边形(包括凹凸多边形)的三角剖分外，如果简单多边形中有‘洞’的情况怎么办。论文中也给出了解决方案，即，依旧使用上述三步骤来做三角形剖分，只是剖分之前定把‘洞’并入外围的简单多边形，即：

	1，用外围的简单多边形上的点，连接‘洞’的简单多边形，因此为了保持所有点的一致性，‘洞’必须是与外围的多边形的点的顺序是相反的。即外围如果是逆时针的顺序，‘洞’则需要顺时针的顺序。

	2，在连接处，产生两个一模一样的点，即连接点。

用这种方式来将‘洞’并入成为一个单独的简单多边形，如果有多个洞，则先并入的洞为，拥有x轴方向最大的点的‘洞’，依次并入。

也就是说，最终计算的还是一个单独的简单多边形，只是在计算之前，将‘洞’以凹形形态并入最外围的简单多边形。

我们以图为例，可以看的更加清楚一点：

	缺少图片

图中展示了，如何将一个‘洞’以凹形形态的方式并入外围简单多边形的，就如同从外围简单多边形上，修了一条小小的通路到‘洞’中那样，其实我们完全可以理解为，下图那样：

	缺少图片

图中从外围简单多边形的点上延伸出一条路径来连接‘洞’，使得‘洞’的空白与外围的空白联通，就像贴膜里的气泡开了个口把空气放出去了那样。

如果’洞‘并不是完全包含在外围简单多边形下，有可能是一半在外面，一半在里面，这时只要做多边形裁剪就可以了，将原来外围的简单多边形根据这个’洞‘裁剪成一个凹形，就与’洞‘彻底分离开来了，形成了新的简单多边形。

‘洞’中的’岛‘

除了有’洞‘，以及’洞‘包含在里面和’洞‘一半在里面一半在外面的情况，还有种情况是‘洞’中有’岛‘。这个‘岛’就像是湖中的‘孤岛’，虽然它也是需要三角剖分，但与外界是无法取得连接的，也就没有与最外围的简单多边形连接的需求。

因此’洞‘中有’岛‘，这个’岛‘就相当于另一个独立的简单多边形范围，可以另外单独拎出来，自己计算自己的三角化部分。

到此，这样就形成了一整个算法，即，如果有‘洞’则先合并‘洞’，如果有岛，则拎出来作为与外围的简单多边形同级别的简单多边形自行计算。所有三角化的计算过程可简单描述为，找耳朵，去耳朵，记录耳朵三角形，最后得到了所有三角形，这四个步骤。

应用到实际项目中，最外层的简单多边形，就是我们在地图中定义的可行走的多边形范围。而‘洞’则是地图上的那些静态的障碍区域，而‘洞’中的‘岛’，则是不可行走范围内的可行走的‘孤岛’。我们在构建三角寻路网格时，首先需要找出这个最外围的简单多边形以及孤岛，再根据切耳算法来构建三角形网格。因此我们需要根据地形来生成相应的可行走三角形网格，通过读取地图中的可行走区域的Mesh，以及读取障碍物Mesh，将它们的竖直方向y轴的值忽略后，再通过多边形合并算法来合并成为最外层的多边形，操作还包括裁切‘洞’一半在里面的情况，最后可以得到需要三角化的简单多边形，以及‘洞’的数据。最后将这些数据用切耳算法得到一个具体的三角网格。

4.多层寻路网格

前面讲了2D平面上的寻路网格构建，在实际项目中大部分时候，2D平面上的寻路就已经够用了，即使是有起伏的地面寻路，也可以用 2D寻路 + y轴射线碰撞的形式 获得位置坐标的方式，在服务器端以2D平面数据的方式去保存和运算数据，这样即满足了寻路的需求也满足了高低起伏的地形。

有一种解决方案可以用多层级的2D网格做3D寻路，它在2D的RPG游戏中比较流行，也曾在PC端的RPG网络游戏中流行过，在现代的3D网络游戏中相对比较少见，因为现在的高度网格构建算法已经有了比较成熟的解决方案，但这种多层级2D网格的做法任然有比较好的实用价值。

我们暂且称它为‘多层寻路网格’，‘多层寻路网格’需要把所有可行走的区域分成多个层级，每一层都有自己的网格数据，第一层与第二层之间也可以多出一个中间连接层，这就像我们拥有一个多层楼梯的古堡中，古堡有4层楼这么高，每一层都用楼梯连接着，这个楼梯就是连接层与层之间的中间层。

我们任然使用2D三角形网格构建法构建每一层的可行走区域，用这种方法我们假设构建出四层楼的寻路网格，每一层都有自己可行走的平面三角形网格数据，每一层的数据网格数据中可以包含当前层的楼梯部分的数据，例如二层的寻路网格数据可以包含一到二层的楼梯部分的数据，也将楼梯部分的数据单独拆分出来成为一个独立的层级。

有了这‘多层寻路网格’的数据，我们就可以开始寻路了，由于我们只关心我当前层的数据，以及当前层上一层与下一层的数据，所以遍历起来非常方便高效。当要跨越层级寻路时，首先必须确定的是‘我’在哪一层，目的地是哪个层级，按次序一层层往上走或者往下寻路。比如我们去的目的地是二楼，所在的起点是大厅的一楼，那么我们就必须由地面层级开始，先找到楼梯层的入口点，从起点寻路到入口点，从入口点进入楼梯层后，从楼梯层数据中找到与二层楼衔接的入口点并寻路，最后到达二层楼并向目的地寻路。

每一层都有自己独立的数据网格，跨越层级的寻路时需要层与层之间的连接点或连接信息，因此我们在制作时需要对层级之间的入口区域做记录，比如第一层某个矩形范围内为第一层与第二层的衔接，只要进入这个范围就认为我们上升了一层或者下降了一层，角色身上的层级标记也相应地变化，此时索引到的寻路网格数据也变成了当前层的数据。下楼也是同样的道理，在每一层中都有几个层与层之间的斜街区域可以通往下一个层级，只要到达这个范围以内就认为是进入了下一个层级，接着就在下一个层级的网格数据中寻路，每次跨层级寻路时都要先寻找上楼或下楼的衔接区域。

多层寻路网格在2D的RPG游戏中很实用，特别是那种有多个楼层的场景，也在王者荣耀、Dota的竞技游戏中用到，这些游戏的场景里面用到了有符号距离场，它是一个方格形式的网格数据，多各层级的网格数据对低洼和高起部分做了分层的可行走区域定制。

5.三角形网格中的A星寻路

前面说的都是网格构建，那么怎样才能让A星与网格数据结合呢。

在二维数组下的A星寻路很好理解，邻近节点就是周围的4个点或者8个点，并且与目的地的期望值可以直接用方块之间的距离来计算。在路点系统中，也有邻近节点概念，它的邻近节点就是与该节点有线条连接的点，与目的地的期望值可以直接用点与点之间的距离计算得到。在平面三角形网格中，以三角形为单位，每个三角邻接三角形为与它们有共享边的三角形，与目的地的期望值可以用三角形的中点与目的地之间的距离计算得到，我们来看下它们三者在寻路后得到的结果的数据示例：

	二维数组下，计算出来的路径，[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4]。

	路点系统中，计算出来的路径，(id=1)->(id=3)->(id=6)->(id=12)->(id=21)。

	平面三角形网格中，计算出来的路径，(trangle_id=1)->(trangle_id=4)->(trangle_id=8)->(trangle_id=13)。

前两者的路径我们很好理解，而三角形网格寻路后，虽然知道了路径上的三角形，但是如果我们行走的路径定位在三角形中心点，行走的路径会比较诡异，每次都要先到达三角形的中点才能去下一个三角形，这样导致中点与中点连线的路径还不够平滑。折中的办法我们可以考虑用边的中点来记录路径，因为相邻三角形之间的穿越都是靠邻边来穿越的，所以邻边的中点更符合三角形穿越，从ID为1的三角形穿越到ID位2的三角形上时，穿越的是ID 1与ID 2三角形的共同边，这种邻边中点计算出来的路径，有更好更平滑的路径效果。

但是这种三角形进出领边中点的方式使路径依然会存在许多折线的情况，为了更好的解决路径平滑问题，我们需要用拐点路径算法来优化寻路后的路径。拐点算法有点像射线，所以也常常被称作为射线优化路径算法，我们来看看算法的步骤：

	1.从起始坐标点出发，往与下一个三角形的入口边的两个顶点v1,v2产生两个向量line1、line2，然后再往下一个三角形的入口边的两个顶点v3,v4产生两个向量line3、line4。

	2.通过计算这四个向量的叉乘，可以判定一个向量是在另一个向量的左边或者右边。我们可以计算出v3，v4是否在line1，line2形成的夹角。

我们主要用这两步来计算拐点，特别是第二步的结果，我们对第二步结果中的几种情况分别做了对应的操作：

	1.line3和line4在line1和line2的夹角范围内，则把实用line3和line4的线作为下一次判断的基线。

	2.line3或line4超出了line1和line2的夹角范围(这里指的是line3超出line1外或line4超出line2外，而不是line3反向超出line2或line4反向超出line1)，则使用未超出的线或原始的线作为下次判断的基线，例如line3超出line1和line2夹角，而line4未超出，则使用line1和line4最为下次判断的基线。如果line3和line4都在line1和line2夹角范围外，则使用line1和line2作为下次判断的基线。

	3.当line3和line4都在line1左边时，则line1的坐标点成为拐点。类似的，当line3和line4都在line2的右边时，则line2的坐标点成为拐点。

	4.当line3和line1是同一个坐标时，它们的坐标点成为拐点。同样，当line4和line2是同一个坐标是，这个坐标点成为拐点。

	5.当寻路达到最后一个多边形，直接判断终点是否在line1和line2的中间，如果不是则用line1或line2的坐标点增加一个拐点，依照夹角偏向判定使用line1还是line2的坐标。

举例说明：从右边的开始点往左边的结束点寻路

	缺少图片1

line3，line4在line1，line2夹角内，左右都缩进。

	缺少图片2

v4在外面，左边缩进。

	缺少图片3

v3,v4都在line1 左边，v1成为拐点

	缺少图片4

从v1出发继续按上面步骤计算拐点

	缺少图片5

最后到达终点，收集所有拐点，加上起点和终点后就是条经过优化后的路径节点。拐点算法能将原本在三角形网格寻路后诡异的路径转化为更加平滑的直线路径。

体素化寻路网格构建

前面说的大都是2D上的寻路，即使多层寻路网格也只是用多个2D寻路网格数据来建立多个层次的寻路数据，但依然无法达到3D高度上自由寻路的功能。如果说要在高度上做到自由寻路则要加入’体素化‘这个概念。体素化就是将空间分割成一个个立方体小方块，每个立方体都标志着是否可行走的状态，如果人物角色有高度和宽度的细节，那么如果不够高或者不够宽的角色就无法通过狭窄的门缝或者矮小的洞穴。

RecastNavigation Navmesh 解决方案在各大引擎上非常流行，各大引擎都根据RecastNavigation Navmesh 对其做了相应的优化修改，不过其核心算法并没有变化。由于内容太多太深，我们并不打算把RecastNavigation Navmesh 里所有的算法都讲解一遍，而是将其制图的步骤和思路讲解一下，以便各位读者能在深入时能更好的理解。

RecastNavigation Navmesh 大体流程如下：

	1. 体素化

	2. 生成区域

	3. 生成轮廓

	4. 生成多边形网格

	5. 生成三角形网格和高度细节

体素化概念比较重要，相当于我们把空间分割成三维方块，每一块都是一个立方体，每个立方体都有着是否可行走的标记。对一个场景进行体素化分析后，就有了如下图所示的标记。

	[缺图1]

上图中，标记绿色立方体部分为可行走区域，标记红色部分为不可行走区域。

接着对这些’体素‘进行整理，生成不同的区块为后面的生成多边形做准备。生成区域时需要对一些不可行走区域进行过滤，比如障碍物以及障碍物周边角色宽度的体素部分，邻接体素的高度不符合要求的部分，邻接有空心体素的部分，都要进行过滤。再对剩下部分的体素集合起来进行体素分区，这里区分区域有好几种算法可以选择，它们都是将上下左右连续的体素进行识别分割成不同的区域，例如构成阶梯的区间能够当做邻居被连接在一起，阻挡物前方和阻挡物后方两块区域被分开来，狭窄的入口前与后两块部分被区分开来等。

	[缺图2]

区域化后就有了上图，去除障碍物周围角色宽度的体素，剔除邻接高度衔接不符的体素，去除邻接有空心的体素，再对剩下的体素识别他们的连续部分，分割成为不同的区域。

接着是检测划分出来区域的轮廓并构造成简单多边形，再将轮廓分割成多个凸多边形，好在后面使用三角剖分算法构建三角网格。如图：

	[缺图3]

最后将所有的多边形网格三角化，并且对多边形中，高低不平的地面部分，插入顶点去构建三角形得到高度细节，最后得到如图所示的三角形寻路网格。

	[缺图4]

上面步骤中用到了体素化算法，区域划分算法，多边形轮廓构建算法，轮廓分割成凸多边形的算法，最后是我们前面介绍过的Delaunay三角剖分算法。

参考文献：

《Triangulation by Ear Clipping》David Eberly

《Delaunay三角剖分的几种算法综述》吴莉莉

《多边形寻路算法简单介绍》 liweizhaolili

《The Core Build Process》http://critterai.org/projects/cainav/doc/html/e72bd1ee-04b0-4bbb-a21d-d8d7ecaa11af.htm