游戏中的寻路算法

电子游戏发展至今已经成为一个热门、体系成熟的高收益产业 。大大小小的游戏类型中，地图、角色、 AI 、迷宫等等元素都已被玩家们习以为常，而寻路算法在它们的逻辑和规则中又起着至关重要的作用。如果你想知道《王者荣耀》里迷失在野区草丛的炮车要如何找回前进的方向，或者你想搞明白为什么《生化危机 2 重制版》里面的暴君能如此恶心地绕着警署三层楼追的你死去活来，那就跟着我一起系统的了解一下游戏中常用的寻路算法吧。

• 地图和图

寻路算法要解决的问题是，如何厘清地图上各个位置之间的关系，如何选取关键位置以及制定在不同位置之间移动的策略。所以我们无法离开地图来谈寻路算法，而任何类型的游戏地图都可以被抽象为经典的数据结构 —— 图（ Graph ）。 图的正式表达式是 G=(V,E) ， V 是代表顶点的集合， E 和 V 是一种二元关系，可以理解为边，比如有条边从顶点 U 到顶点 V 结束，那么 E 可以用 (u,v) 来表示这条边。具体的有向图和无向图，也是根据边是否有方向来区分。为了方便理解，本文中大多数的数据演示都是基于 2D 网格地图来进行讲解，以下是几种关系梳理，以 A 为顶点， BCDE 为子顶点，我们可以把每个格子也看是一个顶点。

图中的边也可以带有权重或花费值 (weight/cost) ：

• 深度优先搜索（ DFS ）

深度优先搜索是搜索和遍历图的一种算法，与树的深度优先搜索类似（其实树形结构可以理解成一种特殊的图），选取一个深度规则，然后按照这个规则，从一个起点不断的向远端搜索。比如二叉树的深度搜索规则可以是：对于当前的节点，优先搜索它的左子，然后再搜索它的右子。方形网格图的一个深度搜索规则可以是：对于当前的节点，按照上 -> 右 -> 下 -> 左的优先级顺序去搜索与它临接的节点（ 这将是本文的几乎所有算法中应用的搜索规则 ）。   

图中灰色格子表示正常联通的路面，红色格子表示无法通过的障碍，黄色表示寻路过程中搜索过的格子，绿色格子表示最终生成的路径（另外感谢 Leo 的倾情出演 ）。我们可以看到， DFS 是遍历地图的算法，所以一定可以帮我们找到一条通往目标位置的路径（如果目标位置可到达），但是这条路径显然不太符合我们通常意义上的寻路需求，它既不是最短的也不是很快就可以找到。但 DFS 仍然是一个非常有用的探索算法，如果你玩过经典游戏《恶魔城》，你一定面临过这样的灵魂抉择：当前场景的所有内容都探索完后，开启了左右两个门，每个门后面都是一个未知的新场景，到底应该进哪个？作为一个追求 100% 探索率的 “ 强迫症玩家 ” ，我的选择是：见门一律进左，一直到走投无路再回来进右。这样的策略通常可以保证在未知的探索过程中少走一些冤枉路。

• 广度优先搜索（ BFS ）

与 DFS“ 一条路走到黑，不撞南墙不回头 ” 的策略不同， BFS 算法的思想是：先搜索附近的，然后再逐渐往外层扩

虽然搜索的优先级顺序仍是上 -> 右 -> 下 -> 左，但 BFS 会先搜索完一个节点的四个方向上直接相临的节点后，再去逐个搜索这些新发现的节点的相邻节点，从而形成层层扩散式的效果，可以看到，当我们搜索到目标点时就已经确定了从起始点和目标点之间 “ 移动步数最少 ” 的路径。然而由于搜索具有盲目性，导致 BFS 作为 “ 寻找最短路径 ” 的算法效率着实比较低下（遍历了过多与目标方向 “ 背道而驰 ” 的节点）。相比之下 BFS 其实更加适合这样的游戏场景：《过山车大亨》中的一位游客，突然感觉到肚子饿了，于是他以自己为中心，通过 BFS 确定第一个搜索到的餐厅或食品摊位，然后沿着路径去那里吃东西。

• Dijkstra 算法

到目前为止，我们已经可以解决如何在联通的区域中，帮 Leo 找到一条通往宝箱的步数最少的路径的问题。但有没有发现，我们其实默认了，每两个格子之间 “ 移动的代价 ” 都是一样。而在实际问题中的地图环境可能要复杂得多，我们要考虑的就不单单是步数这一个因素了。假设我们在花园里散步，我们要从花园的入口到花园中心的池塘边上去。我们肯定会沿着花园中已经铺好的石子路走过去，而不会沿直线穿过各种花丛、草丛和泥坑 “ 跋涉 ” 到目的地。这就是因为综合了 “ 弄脏鞋子 ” 、 “ 蚊虫叮咬 ” 、 “ 猛兽出没 ” 等很多因素后，我们认为石子路比 “ 跋涉 ” 路线的 “ 代价 ” 要低得多（尽管前者的路程可能要比后者要长）。

将 “ 代价 ” 抽象成图的数据结构的话，我们用节点与节点之间的边的 cost 来表示。 Dijkstra 算法便是经典的求解到目标点最小 cost 路径的算法。算法的步骤如下：

1. 将起始点作为第一个 “ 已探索点 ” 。

2. 发现所有通过 “ 已探索点 ” 可以到达的新的节点，计算并更新要到达它们所需的最小 cost 。

3. 选取所有新发现的点中 cost 最小的标记为 “ 已探索点 ” 。

4. 重复 23 直到目标点被标记为 “ 已探索点” 。

假设灰色格子表示正常路面，蓝色格子表示水坑，黄色格子则表示 “ 已探索点 ” 。 Leo 在路面上移动一个格子的 cost 是 1 ； Leo 从路面进入水坑，或从水坑游到另一个水坑，或者从水坑上岸的 cost 都是 5 。则 Dijkstra 算法的过程可以表示为：

可以看到，我们在找到目标格子的最小 cost 路径后仍然没有停止搜索，这是因为该算法很大的一个优点在于，可以一次性计算出从该起点格子出发到达地图上任意一个格子的最小 cost 值和对应的路径。一个典型的游戏应用场景是：《主题医院》中，科室房间和其他的功能区域一旦建成，便可以以医院大门或者分诊咨询台为起点，计算一次到达所有这些区域或房间的位置的寻路路径。只要医院的布局不变化，路径就一直有效，当病人进入医院后就可以根据他要去的地方直接提取路径数据进行移动控制，不必再为每个病人单独进行一次寻路。

• A* 算法（ AStar ）

你可能已经发现，在上面所描述的算法中， Leo 其实并不知道地图上的宝箱在哪，他甚至都不知道地图上是不是真的有宝箱，只是在不断的盲目探索中碰巧发现了宝箱。但在游戏设计开发中，许多时候， Leo 手里其实是有这张藏宝地图的，他跟我们一样是上帝视角。这种前提下，他自然不会眼睁睁的看着宝箱在自己的东方，自己却偏偏先往西方去探索，从而做出很多 “ 无用功 ” 。鼎鼎大名的启发式寻路算法 A* 算法就是被赋予了这样一点点 “ 智能 ” ，却在很大程度上提高了寻路的效率，使得它几乎成为了游戏开发中最常见的寻路算法，以至于程序员们经常开玩笑道： “ 没写过 A 星寻路，都不好意思说自己是游戏开发者。 ”

A* 算法的整体思路步骤与 Dijkstra 算法大致相同，只是在计算每个节点的 cost 时，将其拆分成两部分之和，记作 F(i)=G(i)+H(i) ， G(i) 表示从起点到 i 点的移动 cost ， H(i) 表示 i 点到目的地的估计 cost ， F(i) 则表示从起点要移动到 i 点的最终 cost ，每一轮算法中都选择 F 值最小的节点标记为 “ 已探索点 ” 。我们假设 G 函数的计算方式与上一例子中的 cost 计算方式相同，为相邻格子的移动 cost 的累加。假设 H 函数为 “ 要计算的格子到终点格子在 x 方向和 y 方向上要走的步数之和 ” ，即 “ 曼哈顿距离 ” 。那么算法的过程将如下所示：

与之前的算法相比，该算法不管在算法步骤次数和探索的节点个数上都有相当大的效率提升，这得益于 G 和 H 两个函数为算法提供了 “ 可定制的目的性 ” 。将上面我们选取的 G 和 H 函数所表达的规则翻译成人话就是： “ 朝着靠近宝箱的方向，找一条好走的路。 ”G 和 H 选取的灵活性使得 A* 算法在五花八门的寻路问题中都可以提供有效的解决方案。同时 G 和 H 的选取会直接影响到算法的性能，比如上例中如果 H 选取的定义为 “ 要计算的格子到终点格子的直线距离 ” ，即 “ 欧几里得距离 ” ，那么寻路过程还会进一步得到简化，起点正下方相邻的格子甚至不会被标记为 “ 已探索点 ” 。

至此，我们终于掌握了一个真正好用的求解 “ 最短路径 ” 的算法。至于它在游戏中的应用，就太显而易见了：各种网络和单机游戏中玩家通过点击目标位置使角色向其移动的实现、 roguelike 类型游戏中怪物的仇恨追踪等等。

• NavMesh 导航网格寻路

在之前所有的例子中，为了方便算法说明，我们都选取了正方形网格地图作为我们地图的抽象模型。但是这种地图模型有几个致命问题：

1 、地图规模很大时，比如要开发这几年流行的开放世界无缝衔接的地图类型，格子的尺寸如果选取太小，数量就会太多从而直接导致寻路算法效率跌入谷底；格子的尺寸如果选取的太大，小物体的坐标描述成本会增加，角色寻路位置的精确性也会降低。

2 、角色在正方形格子上基本只能实现四个方向或八个方向的移动，在除像素风格以外的游戏类型中会显得不真实、不自然。毕竟如果能走直线，谁会非要去走个 90 度的大拐角呢？

3 、将格子当作节点来寻路，很难根据角色的身体特征来对寻路进行调整，比如某些狭窄的空间只允许体型较瘦的角色通过。

作为另一个在游戏开发中经常使用到的地图模型和算法， NavMesh 导航网格很好的解决了上面的问题，使角色的移动线路看起来更真实、更符合直觉。

地图生成

我们要对地图进行预处理，根据地图上不同区域特征将其划分成许多邻接的凸多边形（通常是三角形），即 NavMesh ，如下图所示，其中深红色为障碍区域，粉色为可移动区域。

至于如何定义和生成这样的地图格式，有兴趣可自行搜索 NavMesh 生成算法、 Delaunay 三角网格算法、 Weiler-Atherton 多边形裁剪算法等关键字，涉及比较复杂的数学知识，这里先不多赘述了。

寻路算法

假设我们要从 A 点寻路到 B 点。首先我们把地图上的所有三角形看成寻路算法中的节点（类似于之前我们把一个正方形看成算法中的一个节点），那么三角形与三角形之间有公共边就说明这两个节点间是联通的或有边的（当然肯定必须是两个非障碍三角形区域）。然后确定了 A 、 B 所在的三角形节点，我们就可以使用 A* 算法来确定一片 “ 最短三角形联通域 ” ，即图中紫色区域。 A* 算法中的 G 函数可以选取为：相邻三角形中心点（三个顶点的坐标平均值）之间的直线距离。 H 函数可以选取为：三角形的中心点到 B 点的直线距离。

具体路径确定

经过寻路算法，我们确实找到了包含 A 、 B 两个点在内的一条最短联通域，联通域的边界内实际上都是可以任意移动的。但我们怎么确定一条从 A 点到 B 点的最短移动路径呢（即找到上图中的黄色折线路径）？通常我们使用 Funnel Algorithm ， Funnel 中文里是漏斗的意思，这个词比较形象的概括了这个算法。如图：

首先把漏斗的出口设置为起始点（图 A ）。对于要穿过的每条边，依次不断缩小开口张角（图 B-E ）。如果张角闭合了，那么找到当前边的拐点，并重新设置为漏斗的起始点（图 F-G ）。重复该过程直到终点出现在开口中。依次连接起点、各个拐点以及终点，就形成了该次寻路的具体路径。

导航网格寻路在大型 3d 游戏中应用较多，比较成熟的游戏引擎如 Unity 和 Unreal 甚至提供了可以直接使用的 api 接口，可见该算法在效率、平滑度、真实性上的综合优势使其成为了行业内的主流选择。而它带给我更多的感受则是，优秀的算法在很大程度上依赖于优秀的数据结构设计，当遇到瓶颈时，不妨跳出原有的模型架构进行思考，说不定问题会迎刃而解。

• 结语

至此，游戏中比较经典的寻路算法就介绍完了。本文只对算法的大致思路进行说明，并没有涉及实际编码。实际上，这些算法在面临各种实际问题时都有相当大的优化空间，比如我们可以使用二叉堆来保存 A* 算法中的已经计算过 cost 值的节点，以降低最小 cost 选取的性能消耗；或者我们在计算导航网格的 A* 之前，直接对起点和终点进行射线检测，如果射线没有穿过障碍，则可将两者直接连接作为最终路径 。最后，希望各位大佬以后在游戏中被怪物追杀到骂娘时、在对自动寻路无脑做任务的网络游戏大翻白眼时，能顺道感受一下游戏开发者在其背后所付出的汗水和传递的智慧。

戳“阅读原文”get 流利说工作机会噢