liweizhaolili

多边形寻路算法简单介绍

之前有网友在我这里留言，问我怎样用自己的方法生成NavMesh。我也答应了有空的时候介绍一下，所以写了这篇博客。

在说明生成的方法之前，需要先搞清楚几个概念性的问题：

1、NavMesh是一种寻路的算法，我使用的是凸多边形寻路算法，你可以理解成和A星寻路差不多的算法，并不是只有Unity才有的。

2、我使用的NavMesh寻路算法并不是Unity自带的那一套，而是全部自己写的，所以你在Unity的API里面不会找到对应的方法。

3、NavMesh是导航网格的意思，实际工作时他的数据来源是一个由顶点和索引信息构成的网格模型数据。不过这也只是数据而已，并不一定说要把这个网格模型显示出来，或者生成出来，才能工作的。

4、由于是算法，所以它其实是纯数学的方法来的，和你在哪个平台或者引擎使用是无关的。我这个寻路的方法曾经在Unity和As3都用过，都是通用的，理论上在其他语言也是可以实现的。

5、由于和语言关系不大，所以我这里只会简单的介绍一下思路和原理，至于实现，要看各位的数学水平了。懒得看原理想直接伸手要代码的，请自重。

好，废话说完，开始进入正题：

一、总体思路

1、整个寻路的网格是由多个互相连接的凸多边形组成

2、初始化网格的时候，计算出凸多边形互相相邻的边，和通过互相相邻的边到达另外一个多边形的距离。

3、开始寻路时，首先肯定是会得到一个开始点的坐标和结束点的坐标

4、判断开始点和结束点分别位于哪个多边形的内部（只通过x和z坐标，高度先忽略掉），把多边形的编号记录下来

5、使用A*寻路，找到从开始的多边形到结束的多边形将会经过哪几个多边形，记录下来。

6、在得到途径的多边形后， 从开始点开始，根据拐点算法，计算出路径的各个拐点组成了路径点坐标。（忽略高度，只计算出x和z）。

7、到上一步，2D寻路部分结束。人物根据路径点做移动。

8、假如需要3D高度计算，那么在获得了刚才2D寻路的路径点之后，再分别和途径的多边形的边做交点计算，得出经过每一个边时的交点，那么当多边形与多边形之间有高低变化，路径点也就通过边的交点同样的产生高度的变化。

二、详细算法：

1、A*寻路得出途径的多边形：

根据A*寻路的估价

F = G + H

F是格子的总消耗

G是走到下一个格子的消耗的值

H是格子到终点的理论消耗值

在这里，G等于是当前多边形与下一个多边形中心点的距离，这个距离在初始化的时候会先算出来，以后只需要根据交接的边就能取出这个距离。

H其实就是下一个多边形到终点的直线距离了。

 

 

之后就是普通的A*算法了，为每一个格子建立开启列表和关闭列表，然后判断开启列表里面每一个多边形的F值，选取最小的作为下一个格子，如此类推得到了所走过的所有多边形id。

我暂时写好的算法并不是寻找最小路径的，而是用G和H值最快的得出一条可走的路径。这是因为做最小路径必须要历遍所有的开启列表，会比较耗时间。但假如只通过G和H来找路径，有可能会找出绕远路的路径。这时候就要衡量一下G和H的权重了。我这里是把H的权重加大，让方向性比走到下一个多边形的消耗更优先的作为考虑的依据。

2、求拐点算法：

从坐标点出发，往与下一个多边形的交接边的两个顶点产生两个向量v1、v2，然后再往下一个多边形的交接边的两个顶点产生两个向量v3、v4。通过计算这四个向量的叉乘，可以判定一个向量是在另一个向量的左边或者右边。

注意的是，边的两个点是有顺序的，以点的坐标为人物，人物往交接边看去，左边的点是1，右边的点是2，所以与左边的点的向量是v1，与右边的点的向量是v2。

 

 

这里会出现几种情况：

1.下一组边与上一个路径点的向量全部在前一组边的范围内，直接把下一组边的两点替换前一组边的两点。

2.下一组边的右边点与上一个路径点向量在上一组边的范围内，但左边的点不在范围内，把下一组边的右边点替换前一组边的右边点

3.下一组边的左边点与上一个路径点向量在上一组边的范围内，但右边的点不在范围内，把下一组边的左边点替换前一组边的左边点

4.下一组边两个点组成的向量都在上一组边的左边，那么上一组边的左边点成为拐点

5.下一组边两个点组成的向量都在上一组边的右边，那么上一组边的右边点成为拐点

6.假如下一组边左边的点和上一组边的左边点重合，则把上一组边的左边点成为拐点

7.假如下一组边右边的点和上一组边的右边点重合，则把上一组边的右边点成为拐点

8.当寻路达到最后一个多边形，直接判断终点和上一个路径点的向量是否在上一个边两点的中间，假如不是，再增加一个拐点

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

 

初始化时先把开始点加到路径点中，从开始点往下一边两个顶点做出向量v1、v2（红色，下同），往再下一边做出向量v3、v4（蓝色，下同），这时候，明显蓝色的线段都在红色线段组成的夹角内部，所以直接往前移动一格

 

同样做出四个向量，这时候，左边的v3在夹角范围内，右边的v4在夹角外，所以把左边的点替换掉，往前移动一格

 

继续做出四个向量，这时同样是v3在夹角内，v4在夹角外，所以替换掉左边的点，往前移动一格

 

这次做出的向量，蓝色的两条明显在红色夹角的右边，所以v2的点就会成为拐点了

 

把拐点加入到路径点中（这是路径点共有2点，一点是初始点，一点是刚加入的拐点），然后我们从拐点开始出发，重新的做4个向量。这时候同样是v3在夹角内，v4在夹角外，所以替换左边的点，往前移动一格。

 

这次蓝色线段都在红色范围内，所以两个点都替代掉，往前移动一格

 

这时候，红色线段已经移动到与最后一个多边形接触的边了。所以下一个判断的蓝色向量，是终点到当前拐点的向量，这时候，蓝色线段在夹角的左边，所以红色的v1的点就成为拐点，加入到路径点

 

由于已经前进到最后一个多边形了，所以也不需要再做向量了，直接从当前拐点走到终点就行了。所以最后把终点加入到路径点。

  

3、三维坐标求高度的处理：

计算地图起伏有2种方法：

第一种，寻路的时候不计算高度，而在人物与地形之间做射线检测，让人物自动的移动到地形上面。这样做在寻路的时候少了一个步骤，会稍微快一点，但却需要每帧的去计算每个人物的高度，而且这种方法只适合于做没有重叠的地形寻路。

第二种，是在得出2D的路径之后，再和多边形的交接边做交点计算，把得出的交点假如路径点中。这种做法在寻路时会稍微费一点时间，不过能直接得出有高度起伏的坐标点。之后就不需要再针对它做其他计算，人物直接跟着路径点走就行了。这种方法可以支持任意的地形。

我采用了第二种方法。

计算交点的公式：

假设p1和p2是前一个和后一个路径点，p3和p4是交接边的两个顶点，那么

float cx =  ((p1.x - p2.x) * (p3.x * p4.z - p4.x * p3.z) - (p3.x - p4.x) * (p1.x * p2.z - p2.x * p1.z)) / ((p3.x - p4.x) * (p1.z - p2.z) - (p1.x - p2.x) * (p3.z - p4.z));   

float cz =  ((p1.z - p2.z) * (p3.x * p4.z - p4.x * p3.z) - (p1.x * p2.z - p2.x * p1.z) * (p3.z - p4.z)) / ((p1.z - p2.z) * (p3.x - p4.x) - (p1.x - p2.x) * (p3.z - p4.z));  

在假设p3和p4的高度是相同的情况下，我们就可以简单的把交点的y坐标等于p3的y坐标就行了。如果p3和p4高度不一样，还需要计算偏移的权重，然后通过p3.y和p4.y在权重点影响下的y坐标。