A*算法

对比于Dijkstra多了启发函数的概念，在启发函数适合的时候可以更高效率。因为启发函数的估计往往不是精确的，所以A Star 不一定能找出最优解，但是对于游戏来说，看上去合理就行。

 

搜索区域

首先我们对搜索区域要做一个处理，让他变成我们可以进行处理的形式。我们可以把它分成不同的区域，每个区域我们使用一个中心点来代表它。区域可以划分成不同的多边形，而节点也可以在多边形的任一位置选取。根据不同的需求我们会做不同的选择。

 

节点代价

当我们已经选取一个节点，要选取下一个节点的时候，我们需要进行一些选择。我们这里是通过一个等式：

F = G + H 计算出我们每个节点的代价

其中G是指从起点移动到该节点的移动代价，而H是指从该节点移动到终点的估算代价，这个代价我们通常是根据曼哈顿距离来进行计算。但还有很多其他的方法可以估算。

曼哈顿距离：计算从当前位置横向或纵向移动到达目标所经过的距离，忽略对角移动，然后把总数乘以一个值。

 

开始搜寻

把起点加入 open list 。

重复如下：

1. 遍历OpenList，寻找F最小的节点。
2. 把它移出OpenList，加入ClosedList。
3. 对它的相邻节点进行遍历，进行判断

• 如果是不可到达的（我们可以设置一些不可到达的节点）或者在ClosedList的，忽略。
• 如果没在OpenList中，加入OpenList，并且把当前节点设置为该节点的父节点。
• 如果已经在OpenList中，更新 F，G，H值，并且把当前节点设置为该节点的父节点。

到最后加入终点节点时，寻找结束，从终点沿着父节点回去就是我们的路径。

 

NavMesh

NavMesh是广泛使用的一种寻路技术，将地图中可走的部分生成连续的多边形/三角形网格，寻路在网格中进行。

网格生成

1. 体素化。从源几何体构造实心的高度场，用来表示不可行走的空间。

2. 生成地区。将实心高度场的上表面中连续的区间合并为地区。

3. 生成轮廓。检测地区的轮廓，并构造成简单多边形。

4. 生成多边形网格。将轮廓分割成凸多边形。

5. 生成高度细节。将多边形网格三角化，得到高度细节。

更详细的内容可以参考 navmesh原理 https://wo1fsea.github.io/2016/08/20/About_NavMesh/  我这里还有点没太看明白，之后看明白了会修改一下。

根据网格构建起点到终点的多边形集合

根据网格的邻接信息构造图，使用A*之类的寻路算法计算出从起点到重点需要走过的多边形/三角形集合

生成路径点

对于三角形列表的漏斗算法 

 

原理

关于凸多边形我们有这样的一个性质：在凸多边形边上的一个点走到另外一点，不管怎么走都不会走出这个多边形。

应用到游戏世界里，我们只要在空地上放置凸多边形，小人在多边形内怎么走都不会碰到障碍。

我们知道任意一个三角形都是凸多边形，我们可以先通过地图的边界点和障碍物的边界点，将地图划分成很多个三角形，如下图所示。

我们可以看到，虽然通过这种方法生成的网格相比grid已经大大减少，但是图上很多相邻的三角形是可以合并形成新的凸多边形的。所以我们其实还可以进一步优化，将可以合并成新的凸多边形的相邻多边形合并，并重复这一过程，最终得到下图。

 

然后我们可以在每一个网格每一条边的中点上放置pathnode(路径点)，然后将每一个网格自己边上的路径点连接起来就得到了完整的路径网络了，如下图，同上绿色的线代表画好的navigation mesh，蓝色的线代表可以走的路径网络。

 

 

优点：这种方法可以大大减少路径点和搜寻所需的计算量，同时也使小人的移动更加自然。在这样的路径点之间行走，我们其实可以完全无视地图上的任何障碍物。

 

缺点：计算三角形和合并相邻的凸多边形需要很大的计算量，而且实现起来没有看上去那么简单。不过成熟的游戏引擎一般是有现成的解决方案的。

 

 上面第二段 navmesh的内容来源于 https://www.zhihu.com/question/20298134/answer/37952808 @王凝

文章里还探讨了Dijkstra’s algorithm，可以一看。动态寻路中最好还是用A*，Dijkstra可以在静态地图中使用。

Dijkstra’s algorithm。说Dijkstra是A*的无heuristic版本，其实并不准确。A*去掉heuristic其实是uniform cost search。而Dijkstra是uniform cost search的multiple destination的变形。也就是说，给出地图上一个路径点，使用Dijkstra可以对地图上所有其他的路径点一次性计算出最优路径。Dijkstra的时间复杂度是O(|E|+|V|log|V|)，这时E是edge数，V是vertex的数目(Dijkstra's_algorithm)。从这里可以看出，如果需要对地图上所有的路径点同时计算左右路径，Dijkstra会比使用A*更方便。这也就说明了为什么Dijkstra适合对静态的环境进行计算，因为静态的环境是不会变的，我们可以是用Dijkstra对地图进行preprocess获得navigation table（后面会说明navigation table如何生成）。我们可以把navigation table记录下来，这样在游戏进行的时候从一个路径点到另外一个路径点只需要查表就可以了，这样一来游戏实际运行时的寻路的时间复杂度就减少到了O(V)，也就是线性复杂度了，而且对于静态的环境，我们的navigation table是百分之百可靠的。

 

一大群单位的寻路

还有Flocking Behavior，
在对于一大群单位的寻路，计算量是很大的，而且往往会有很多的重复，这些都是可以避免的。
如果单位的移动是利用Steering Behavior 来实现的话， （Steering Behavior，将一个单位考虑成一个受力点，通过增加不同的力，如吸引的，排斥的等等，实现如搜索、逃跑、躲避障碍和Flocking等行为。）
那么就可以为其中一个单位，称之为Leader，计算路径（例如用导航网格），
然后其他单位按照以下Flocking原则来移动：
1. 分离，避开相邻单位
2. 一致，和整体的移动方向一致，这里应该是Leader的移动方向
3. 聚合，向整体的平均位置靠拢
这样的话，就可以降低寻路的计算量，并且得到更加真实的群体单位行进效果。

对于不用Steering Behavior的一大群单位，
可以将他们设为一个组，计算这个组的路径（并且要考虑到这个组的半径以便通过转角位），
然后给每个单位offset一个适当的距离，
如果遇到小的通道，例如门，可以适当调整offset。
《全面战争》里面一个队伍40人，大概用的就是这种方法 [11]。

 

还有一个优化技巧是Chunk 

（这个就是我们上面最开始提到的NavMesh？）
“先切分地图然后分块去做”
在规模宏大的地图中，为了进一步提高寻路速度，可以在编辑地图时将一些节点处理成一个Chunk，它有入口和出口，并且不同Chunk之间需要连接起来。
从A点移动到B点，首先先在Chunk之间做寻路，得到一系列的Chunk，
在Chunk 1的时候只需要在Chunk 1中寻路，去到Chunk 2的时候就只在Chunk 2中寻路。
它本质上是将地图分为两种维度，一种是粗略的Chunk，一种是Chunk里面的节点（可以是方块，路径点，导航网格），并分开进行处理。有种空间分割（Space Partition）的味道在里面。
 

这里参考自https://www.zhihu.com/question/20298134/answer/22861904 @伍一峰