游戏中的寻路算法解析

发表于2015-04-29

游戏角色的自动寻路，已经是游戏中一个历史比较悠久的领域，较为成熟也有很多种实现。这里摘录一句后面所提的参考资料中的描述：“业内AI开发者中有一句话：“寻路已不是问题。”我们有针对各种寻路问题的各种解决办法，只不过不常使用而已。“

实际应用中寻路算法里里面还是有挺多讲究的，如果寻路在游戏中占了很大比重，是有很多相应优化的方式和空间的，可以特别关注。以下内容主要是查阅了网上很多资料文档后整理出的内容，比较偏重于需要特别关注的点。以便感兴趣的同学查看后对其有一个基本的概览和了解。

可能有同学嫌整的凌乱了些，亦可以直接跳过到后面内容的第四点，从查阅 “四.写得很好的一些相关参考资料地址“开始。

一、游戏中的寻路算法

大部分游戏在开发过程中都会遇到路径探索问题：需要快速、准确地计算出游戏角色从地图中的A点到达B点（自动绕过障碍物）的一条较好最短路径。这个已经是一个游戏AI中较成熟的的必要组成部分(一不小心在网上搜出了2008年腾讯还申请注册了一个相关专利"一种地图寻路方法及系统"：路点加三角面的方式)。

寻路可以有多种算法：

1) DFS

2) BFS

3) Dijkstra

4) A*路点寻路

5) D*

6) NAV导航网格寻路

7) 预设导航点的固定路径

8) 。。。

在以上前四种中，A*是平均计算速度最优的；Dijistra算法相当于A*算法中估价值为0的情况。后面几种，D*是用于动态路径的算法(用于机器人探路，比如火星探测器的寻路; NAV导航网格寻路其实也是基于A*实现，目前主要应用在3D游戏中。

二、 A*路点寻路和NAV导航网格寻路

在目前的游戏中使用和提到较多的是A*路点寻路和NAV导航网格寻路，均己有较多探讨和一些主流语言的实现。这两种算法本质上都是以A*算法为基础。

对于A*路点寻路。目前在游戏中(尤其是市面上的2D网页游戏中)普遍使用A*算法做为自动寻路算法。A*算法本身思路比较简单，程序写起来也不麻烦，关键是要在代码优化上下功夫，并且根据不同类型的游戏运行场景在实现上做优化。比如针对地图类型的不同、同屏需要同时寻路的单位数目的不同、对路径光滑度要求的不同、不同的设备(PC或者手机)、不同的设备性能，甚至即使在同一个设备同一个游戏内不同的游戏场景也可以相应有更优化的算法实现。因此，在手机上的HTML5游戏这种页游中，如果有游戏的需求，根据寻路操作在游戏中所占的比重大小(频率及重要性等)，寻路算法的实现上还是可以有很多讲究的。

对于另一种寻路算法：NAV导航网格寻路。这种算法是在进行地图划分的时候是划分成多个凸多边形（一般是三角形），然后也是基于A*算法来遍历查找最短路径。与将地图划分为规则等大格子的A*路点寻路相比，该算法在地图预处理或者地图发生变化时需要更复杂的处理：按照一定的算法将地图上可达区域划分为多个三角形；另外使用A*算法时找到路径经过的三角形以后，需要根据已经连接好的三角形路线进行拐角点判断，将起点逐个连接这些拐角点直至终点得到最终路线。

A*路点寻路有一些缺点，列举其中一些比如：1.在地图较大划分格子较多的时候效率会较低；2.最终的行走路线不够光滑。而NAV导航网格寻路将地图划分为三角形后，在大多数情况下进行A*寻路效率会更高，路径也会更光滑，并且在路径上可以加入更多额外的信息。

NAV导航网格寻路在地图处理和算法实现上会更复杂一些，目前还主要是在3D游戏里使用，3D游戏里的模型己自带网格。一般而言，对于目前的2D游戏的内容和形式基本的基于A*的路点寻路算法已经足够；比如对于纯2D策略类游戏，那么一个基于方格的路点寻路算法更为合适，因为格子允许更快捷地访问任意地块。

三、在游戏中应用A*路点寻路

在游戏中应用A*算法主要是以下步骤：

1．将地图划分包含多个等大区域的网络：传统做法是将地图划分为多个等大的正方形小格子，或者也有将地图划分为由菱形小格子组成；另外如果将地图划分为多个凸多边形情况下，便是NAV导航网格寻路的思路了。

每个小格子就是一个导航路点(waypoint)，这种寻路算法就是常说的路点寻路算法。

疑问：地图有多大，小格子多大一个，就会对寻路的效率（对空间、时间消耗均有影响)，以及人物行走的视觉效果有直接影响。

2．生成相应的地图数据：主要用于标记各路点可否通过，及其他相应的一些地图信息。

疑问：通常不同的地形通过的代价应该是不同的，比如通过1米宽的沼泽的代码要大于通过3米长的道路，这时候较短路径应该是起道路而不是沼泽。所在在寻路算法中的最短路径一般是指最小代价路径。对于路点寻路算法来说可对waypoint加上权值来描述。

3．将地图数据、起点、终点交给A*算法，即可得到一条由多个waypoint组成的路径

针对A*算法本身，也有很多值得优化的地方；

A*算法本质是一个启发式搜索算法(BFS等算法其实是A*的一个特例)，在计算过种中会主要涉及这么两个重点：

Ø 计算过程中的临时空间：包括一个待搜索点表(open表)和一个已搜索点表(close表)；

Ø 路径长度的估价等式：f(n) = g(n) + h(n)

其中f(n)是节点n的估价函数，g(n)是在状态空间中从起点到n节点的实际代价，h(n)是从n到终点的最佳路径的估计代价。需要特别关注h(n)，因为g(n)一般是已知的。

？？？在该算法中，对空间是有一定消耗的，尤其在找不到一条通达的路径时，open表是可能比较庞大的。针对open表是需要做一些添加、删除、排序的操作。比较常见的做法是使用二叉堆来存储这个结构（这会增加“添加或者删除”操作的时间及一些存储空间，但会大大减少排序时间），地图路点越多时性能提升越明显，这需要根据应用场景做不同的取舍。经过实际的HTML5动画的javanoxss实现，性能提升是非常明显的。

？？？对于路径长度估价等式中估价函数即h(n)，一般的估值计算方式包括：对角线距离、欧几里得距离、曼哈顿距离等等。这个计算会在算法中经常用到，需要较为高效，计算简单使用最精简有效的公式。目前的实现中一般使用曼哈顿距离方式。

4．在得到由多个waypoint组成的路径后，再按照游戏的动画方式让精灵沿此路径行走即可。对于这种算法，精灵可能走出Z字形或者锯齿形的路线，如果游戏有需求需要更平滑，还可以做一些额外的处理使其更平滑。

？？？目前一般弗洛伊德路径平滑算法进行后期处理。

以上便是在游戏中应用A*路点寻路的一些过程和思考。

其他一些算法的优化：性能上可以对地图数据做一些提前处理和运算，记录下结果，空间换时间；另外对于不同语言实现的算法本身细节做一些优化；针对效果：鼠标点击到障碍点无路可走的处理等等。在具体的游戏场景中，也有一些细节优化即可得到大效果的处理方式，或者一些变种的寻路算法。另外还有结合寻路算法的一些相关处理，如动态的运动障碍物等。

实现了个HTML5中javanoxss的版本.