趣说游戏AI开发：曼哈顿街角的A*算法

0x00 前言

请允许我自称为“标题党”。因为接下来的内容既不会围绕美国曼哈顿展开，也不是一个关于美国梦的故事。实际上，这是一篇尽量避免枯燥，深入探讨算法的文章。A星算法，作为游戏寻路开发中常用的算法，将是本文的核心主题。

0x01 曼哈顿的街道

下面展示的是美国曼哈顿的俯视图。除了能看到林立的高楼，我们还能发现其街道布局的显著特点：横平竖直的街道将整个区域整齐地划分成多个区块。行人和车辆只能在街道上行驶，并且只能在街道交叉口改变行进方向。例如，要在地图中找出从A点到B点的最佳路线，实际上就是从A点所在的交叉口沿着街道走到B点所在的交叉口，无法穿越街道围成的区块，只能沿着街道行进。

我们把曼哈顿的街道交叉口看作结点，两个交叉口之间的街道视为边，构建一个二维网格。

那么，A点到B点的实际距离是多少呢？由于只能沿着街道行走，无法穿越区块，所以A点到B点的实际距离并非它们之间的直线距离，而是如下图所示的路径长度。

用数学语言表示为：

dis = abs(A.x - B.x) + abs(A.y - B.y)

这就是曼哈顿距离，在A星算法中，它常被用作启发函数。那么，启发函数是什么呢？接下来将为你详细介绍。

0x02 醉汉寻“路”

从A点到B点的路径，由一系列以A为起点、B为终点的结点组成，且每个结点只能从其相邻结点中选择下一个行走目标。然而，在现实中，道路并非总是畅通无阻，可能会因路况不佳、交通拥堵等因素，导致在某些道路上行走需要花费更多时间。因此，在寻路过程中，一条路径的代价等于在每个路口选择的道路的代价之和。

了解这些后，我们来实现一种最直接的寻路方式，就像一个醉汉，不考虑是否走过某条道路，也不关心每条道路的时间代价，只是在路口随意做出选择。

// 伪代码
q = new queue
q.enqueue(new path(start))
while q is not empty
p = q.dequeue
if p.lastNode == destination
return p
foreach n in p.lastNode.neighbours
q.enqueue(p.continue path(n))
// 找不到合适路径
return null

这种做法的后果显而易见。就像醉汉一样，从路口的四个方向随机选择一个方向，甚至可能走回头路（因为没有记录已走过的路口）。也许最终能找到目的地，但会消耗大量时间，走很多冤枉路。更糟糕的是，如果实际上不存在到达目的地的路径，还可能陷入无限的死循环，即出现“鬼打墙”的情况。

为了解决这个问题，我们帮助醉汉记录他已经走过的路口。引入一个closed集合，用于保存已走过的路口。

// 伪代码
// 引入一个集合，用来保存已经走过的路口
closed = {}
q = new queue
q.enqueue(new path(start))
while q is not empty
p = q.dequeue
// 如果closed集合中包含了路径p的最后一个路口，则忽略
if closed contains p.last
continue
// 如果路径p的最后一个路口即是目的地，则直接返回p
if p.last == destination
return p
// 否则将该点p.last加入到closed集合中
closed.add(p.last)
// 把点p.last相邻的点加入到队列中
foreach n in p.last.neighbours
q.enqueue(p.continue path(n))
// 找不到合适的路
return null

通过这种方式，我们解决了醉汉走回头路的问题，消除了“鬼打墙”的隐患。但醉汉在选择道路时仍然没有明确的目标，这导致他寻找目的地的效率不高。尽管在我们的帮助下不会走回头路，但他仍然会向四面八方寻路。显然，为了让醉汉尽快回家，我们需要为他选择一条最佳路径。那么，如何选择（预估）这条最佳路径呢？

0x03 给我一个指南针

在寻找最佳路径之前，我们需要为最佳路径定义一个可量化的标准。最简单的方法是选择两个路口之间的距离作为标准，我们将这个距离长度称为路径的开销。规定一个路口上下左右相邻的路口的消耗为1，对角线上的路口消耗则为1.41。

评价一条潜在路径的开销时，主要依据两个方面的数据：

• 该路径到目前的路口为止，已经经过的路口的总消耗。这是已知的，我们将这个消耗的值记为G。
• 该路径到目前的路口为止，预估到目的地的消耗。这是猜测的，我们将这个消耗的值记为H。

我们的目标是在帮助醉汉不走回头路的基础上，为他指明回家的方向。醉汉只需沿着这个方向走，就能更快地找到家。这个方向是如何确定的呢？其实很简单，我们只需找到总消耗最小的路径。记总消耗为F，则有如下等式：

F = G + H

具体操作如下：我们需要一个优先队列，记录每条路径的总消耗以及这条路径，并根据路径的总消耗对队列进行排序，这样就能轻松获取消耗最小的路径。代码拓展如下：

// 伪代码
// 引入一个集合，用来保存已经走过的路口
closed = {}
q = new queue;
// q为优先队列，记录路径的消耗以及路径，起始点消耗为0
q.enqueue(0, new path(start))
while q is not empty
// 优先队列弹出消耗最小的路径
p = q.dequeueCheapest
if closed contains p.last
continue;
if p.last == destination
return p
closed.add(p.last)
foreach n in p.last.neighbours
// 获得新的路径
new path2 = p.continue path(n)
// 将新路径的总消耗（G+H)，和新路径分别入队
q.enqueue(new path.G + estimateCost(n, destination), new path2)
return null

其中，预估到目的地消耗的函数estimateCost就是A星算法中常用的启发函数。它的作用是估算当前位置到目的地的大概距离，本文开头介绍的曼哈顿距离就是一种常用的启发函数，即计算当前路口（格子）到目标路口（格子）之间的垂直和水平的路口（格子）数量总和。

dis = abs(A.x - B.x) + abs(A.y - B.y)

这个启发函数就像我们送给醉汉回家的指南针。

当然，通过醉汉回家的例子，我们只是介绍了A星算法最基本的实现原理。在实际工程中，A星算法有更复杂的应用场景。接下来，我将简单介绍几种工程中实现A星寻路的工作方式。

0x04 工程中A星算法的实现方式

有了算法的实现思路，接下来探讨如何在游戏中实现A星算法。

在游戏中进行寻路，首先要借助图来表示游戏地形，这个图就是导航图。常见的导航图有以下三种：

基于单元格的导航图

将游戏地图划分为许多单元格，这种表示方式就是基于单元格的导航图。其结构规则，易于理解和使用，并且便于动态更新。因此，在需要频繁动态更新场景的游戏中，使用这种导航图非常合适。

然而，为了提高寻路结果的精确性，单元格的大小是关键因素。过大的单元格会导致寻路不精确，而使用过小的单元格会增加需要存储和搜索的结点数量，不仅消耗大量内存，还会影响搜索效率。

基于路点的导航图

如果用人工不规则放置的导航点代替单元结点，是否会有更好的效果呢？于是，基于可视点，即路点（The waypoints）的导航图应运而生。图中红色的结点就是放置的路点，路点之间的连线是游戏单位可以行走的路径。

基于路点的导航图的优势在于，场景设计师可以根据场景特点布置路点，具有很高的灵活性。与基于单元格的导航图相比，它不需要存储和搜索大量结点，因此在内存使用和搜索效率方面表现更优。

但它也有明显的缺点。如果场景过大，少量的路点无法满足需求；而放置大量路点会使场景设计师的工作变得复杂，容易出错。此外，游戏单位只能在两个路点之间的连线上移动，如果游戏单位不在结点或结点间连线上，会先移动到最近的路点，再继续移动，从视觉上看会显得不自然。

导航网格

导航网格将游戏地形划分为大大小小的三角形，这些三角形就是A星算法中的节点。相邻的三角形可以直达，即三角形相邻的其他三角形就是其相邻的结点。

与前两种导航图相比，导航网格的“节点”面积大，只需要少量的“节点”就能覆盖整个游戏区域，从而减少了“节点”数量。而且，由于节点完全覆盖了游戏场景，不用担心像基于路点的导航图那样因缺少路点而导致寻路不精确的问题。

不过，导航网格也并非完美。生成导航网格的时间较长，因此建议在静态场景中使用，在地形经常变化的场景中应减少使用。