注意
本文转载并翻译自
网站 Red Blob Games
文章 Introduction to the A* Algorithm
如有侵权, 请联系删除。
正文
在游戏中我们常会需要找出从一个点到另一个点的路径。我们不仅需要找出最短路, 有的时候也需要考虑经过这条路径所花费的时间。
当地图使用图来表示的时候，我们可以使用一种基于图论的搜索算法来找出我们想要的路径。A*算法是一种比较受欢迎的图搜索算法。但是让我们先从最简单的图搜索算法-广度优先搜索来一步一步探索并接近A*。
地图表示
学习一种算法的第一步通常是先理解[数据]，输入数据是什么？输出数据是什么？
[输入数据]:
像A*这样的图形算法通常会使用"图"做为输入, 一个"图"由"点"和"边"的集合组成。
下面是我给A*输入的一个"图"的示例:
A*除了输入给它的"图"以外不会关心其他任何数据。它并不会知道什么东西在里面或者外面，不会知道这个点是个通道还是个房间, 也不会知道这块区域到底有多大, 它只关心输入给它的"图"(点集与边集之间的关系)！
对于它来说，下面这幅地图和上面那副根本没什么两样。
[输出数据]:
A*算法所找出的路径是由点集和边集组成的。这里的"边"是一种抽象的数学概念。A*会告诉你需要从一个点移动到另外一个点但是不会告诉你如何移动过去。记住, 它除了点集与边集之间的关系组成的"图"之外并不知道其他额外的信息, 比如这里是个通道还是个门。你将会需要自己决定A*算法交给你的这条边是一格一格地移动、走一条直线、打开一扇门、游过去亦或是沿着一条曲线移动过去。
[权衡]:
对于任何一副给出的游戏地图来说, 有很多种方式去划分出一份交给A*算法的"图"。
最开始我们给出的示例"图"将许多"点"表示为通道:
那如果我们将通道放在"边"上表示会是如何呢?
又或者我们使用寻路网格来表示呢?
用于输入给寻路算法的"图"不需要与你使用的游戏地图保持一致。一个由格子组成的游戏地图可以使用并不是由格子组成的寻路“图”， 反之亦然。对于A*算法来说，点集中的点越少，运算的速度就越快。通常，使用网格来划分地图会变得比较容易处理，但是与此同时也会导致点集中的节点数量过多。这篇文章只探究A*算法本身而非“图”划分的设计，如果你想了解更多关于“图”设计的内容，可以阅读我的其他文章。对于本文章的后文，若没有特殊说明，我将默认使用格子去划分地图以便于将相关概念以更加直观的方式表现出来。
算法
基于图论的算法有很多，我将重点探究以下几种：
广度优先搜索算法对于所有的方向都进行等价搜索，这是一种不仅对于常规寻路, 同时也对随机地图生成(procedural map generation)、流场寻路(flow field pathfinding)、距离图(distance maps)还有其他类型的地图分析等都非常有效的算法。
Dijkstra算法(也叫做一致代价搜索UCS)让我们对于那些路径需要优先搜索给出优先级而不是等价地探索所有可能的路径，在探索过程中，Dijkstra算法更偏爱于代价更低的路径。我们可以通过给一些路径设置较低的代价(消耗)来是的算法搜索过程中优先考虑使用这条路径，或者是设置较高的代价(消耗)使得算法尽量避免通过一些类似于丛林、敌人之类的地方。当地图上的路径行动消耗不同时, 我们通常会使用Dijkstra算法而非广度优先搜索算法。
A*算法是Dijkstra算法对一个单独目的地的情况做出针对性优化的一个改版。Dijkstra算法可以找出一个点到“图”上所有点的路径。A*算法只找出一个点到一个特定目的地的所有路径，或者是到一些点的最短路径。它会给通往一个目标哦的那些看起来更近的路径排出先后顺序。
我将会从最简单的广度优先搜索算法开始，然后逐步添加特性来让它一步步转变为A*算法。
广度优先算法
所有这些算法的中心思想是，我们跟踪一个不断膨胀的、叫做“边界”的环，在网格中，这个过程有时被称为“洪水式填充”，不过这个技术同样也适用于非网格的“图”。
我们要怎么样实现这样的过程？重复以下过程直至取到的“边界”为空：
- 在边界上选择并移除一个点
- 通过查找周围的节点进行扩展：如果是墙， 则跳过；否则，如果是没有到达过的节点，那么都加入到环中，到达过的节点，从环中移除并记录为已到达。
演示图如下，其中带数字的格子表示当前演示步骤。
以上步骤的实现只有10行（Python）：
frontier = Queue()
# start指图中星星所在的起始点
frontier.put(start)
reached = set()
reached.add(start)
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in reached:
frontier.put(next)
reached.add(next)
这个循环是这片文章内包括A*在内的图搜索算法的本质。但是，我们要如何才能找到最短路径呢？这个循环实际上并没有在构建任何路径，它只是告诉我们如何去遍历这张“图”上的所有节点。这是因为，广度优先搜索算法的用途不仅仅是在寻路上，在这篇文章中，我演示了这个算法如何应用在塔防游戏中，然而其实它也可以用在距离图、生成随机地图和很多其他事情上。
不过这里我们还是想把它应用在寻路上，所以我们修改一下这个循环来使得我们可以追踪我们是从哪个点去往每一个到达点的，同时，我们将到达点集合reached改为一个记录从哪个点来到当前到达节点的表came_from（表的键为过程中所到达的点）：
frontier = Queue()
frontier.put(start)
came_from = dict()
came_from[start] = None
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
这样处理完毕之后，得到的came_from表可以用来得到来到某个点之前的点，就像“面包屑”一样散落在地图上。这些信息已经足够让我们用来构建出一整条路径了。
用于重建出路径的代码就很简单了：从终点一路跟随
came_from中所指向的“前一个点”直到起点位置即可。一条路径是一系列边组成的序列，但是通常情况下，存储节点来表示路径会更加简单：
# goal表示上图叉所在的终点位置
current = goal
path = []
while current != start:
path.append(current)
current = came_from[current]
path.append(start) # optional
path.reverse() # optional
以上就是最简单的一种寻路算法，它不仅仅对于上面展示的这种格子地图有效，对其他各种类型的“图”结构亦是如此。在地牢中，图上的点可以是各个房间，图上的边可以是房间之间的通道；在一个平台游戏中，图上的点可以是每一个位置，而图上的边可以是各种类似于左移、右移、上跳、下跳等行为的可能性，大体上说就是把图想象成是各种状态，然后各种行为会改变状态。我在这里有写更多关于地图的表现相关的内容。在这篇文章剩余的部分，我还是会继续使用格子来作为示例，然后去探索为什么我们可能会需要使用各种广度优先搜索算法的变体。
提前退出
我们已经可以找到从一个点到其他所有点的路径，通常来说，我们并不需要所有的结果，而是只需要从一个点到另外一个点的一条具体路径，所以我们可以在找到终点的时候立即停止边界的扩张。
代码也比较简单：
frontier = Queue()
# start 起点
frontier.put(start)
came_from = dict()
came_from[start] = None
while not frontier.empty():
current = frontier.get()
# goal 终点
if current == goal:
break
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
你可以通过提前退出条件做出很多有趣的事情。
移动消耗
到目前为止，我们在格子上移动的“消耗”都是相同的，然而在某些寻路场景中不同的移动方式所需要的消耗（代价）是不同的。例如，在《文明》中，移动经过平原或者沙漠将会消耗1个行动点，但是移动经过树林或者山丘就得消耗5个行动点。在这篇文章最初的那个地图中，走过水地将会花上等价于10倍走过草地的时间，再例如，某个地图上的格子斜着走要比直着走消耗更大。我们一般会希望寻路算法在寻路过程中将这些消耗也考虑进去。让我们比较一下从起点到终点的[步数]与[距离]：
对于这种情况，我们会希望使用Dijkstra算法（一致代价搜索UCS）。不过这个算法与广度优先搜索相比有什么不同之处呢？
为了追踪移动的消耗，我们加入一个新的变量
cost_so_far来保持追踪从起点开始的累计移动消耗。我们想要在评估一个点的时候把移动消耗也纳入决策中。首先让我们把代码中的队列转换成一个优先队列，不太明显的一点是，我们可能会多次到达并访问同一个点，但是消耗不同，所以我们需要稍微改动一点逻辑，如果访问到了一个没有到达过的点，我们先不急着将它加入边界中，而是在考量这条新路径比之前所得的最优路径更好之后再把它加入边界。
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost
frontier.put(next, priority)
came_from[next] = current
使用优先队列而不是常规队列改变了边界扩张的方式。在运行过程中我们会发现使用Dijkstra算法边界在扩张时，通过中间树林地形的速度会更慢，并且尝试在树林的周围去寻找最短路径而不是穿过树林：
非1的移动消耗让我们除了格子之外还能探索更多有趣的图形。在文章开头的地图中，移动消耗是由房间与房间之间的距离来决定的。移动消耗也可以用来根据邻近敌人或盟友来规避或偏好某些区域。
实现说明：我们想要代码中的优先队列优先返回最小值。在[代码实现]系列文章中我展示了PriorityQueue在Python中使用heapq来优先返回最小值。在C++实现部分中我通过配置std::priority_queue来优先返回最小值。同样的，我在这篇文章中呈现的Dijkstra算法与A*算法实现有别于算法教材，它们会更加接近于被叫做 一致代价搜索 的算法。我会在实现篇中描述这些区别。
启发式搜索
通过广度优先搜索算法和Dijkstra算法，边界可以向各个方向进行扩张，如果你想要找出一条通往所有点或者许多点的路径的话，这的确是一个合理的做法。不过，通常情况我们是需要寻找到某个特定点的路径，不妨让我们尝试一下让边界相比于其他方向更多地朝着目标点扩张。首先，我们需要定义一个 启发函数 heuristic 来告诉程序我们当前距离目的地有多远：
def heuristic(a, b):
# 方形格子的曼哈顿距离
return abs(a.x - b.x) + abs(a.y - b.y)
在Dijkstra算法中我们使用从起点开始的实际距离来给优先队列排序，不过在 贪婪最佳优先搜索 中，我们将会使用到终点的估计距离来进行优先队列的排序，最靠近终点的点将会最先被探索。下面这段代码沿用了Dijkstra算法的优先队列但是没有使用cost_so_far字段。
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
came_from[start] = None
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
if next not in came_from:
priority = heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
让我们看看运行情况：
喔！是不是很神奇？如果换成一张更复杂的地图会怎么样呢？
贪婪最佳优先搜索找出的路径并不是最短路径，所以这个算法在地图上没有太多障碍物的时候运行的非常快。但是所得的路径并不是很完美，我们还能更进一步吗？当然可以！
A*算法
Dijkstra算法很善于找出最短路径，但是它在探索各个没啥用的方向上浪费了太多时间了。贪婪最佳优先搜索始终在尝试探索最接近目标的方向，但是它找到的却不一定是最短路径。A*算法在它的决策中同时考虑了距离起点的实际距离以及距离终点的预估距离。
代码方面和Dijkstra算法比较相像：
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
将几种算法进行比较：Dijkstra算法计算了从起点开始的距离；贪婪最佳优先搜索预估了到终点的距离；而A*算法使用了两者之和。
当尝试随便在墙上开几个洞的时候, 我们会发现如果贪婪最佳优先搜索能够找到最短路径，那么A*算法可以在和贪婪最佳优先搜索探索相同区域的情况下也找到最短路径。
但是当贪婪最佳优先搜索不能得到最短路径的时候，A*算法却依然可以做到在比Dijkstra算法探索更少区域的情况下找到和Dijkstra算法一样的最短路径。
A*算法是两全其美的，只要保证启发函数在距离上不过度预估，A*算法就能像Dijsktra算法一样找到一条最优路径。A*使用启发函数去重排节点来让目标点尽可能快地被探索到。
嗯......这就完事了！以上就是A*算法。
更多
你准备好去实现这个算法了吗?考虑去使用一个现成的库吧。如果你正在自己实现这个算法，我在这份指南里展示了如何使用 Python/C++/C# 去一步一步实现 图、队列和寻路算法。
当你想在游戏地图中使用寻路的时候你应该选择哪个算法呢？
- 如果你想要寻找到所有点的路径，就使用广度优先搜索或者Dijkstra算法：如果移动消耗都是等价的话就是用广度优先搜索，如果移动消耗各有不同，那就使用Dijkstra算法。
- 如果你想寻找到某一个特定点的路径，或者到某几个点的最短路径，那就使用贪婪最佳优先搜索或者A*算法，大部分情况下应该优先选择A*，当你想要使用贪婪最佳优先搜索的时候，可以考虑一下使用一个带有“非常规”的启发函数的A*算法。
关于最优路径呢？广度优先搜索和Dijkstra算法保证可以找到给出的图中的最短路径，但是贪婪最佳优先搜索无法保证，A*算法在启发值保证不大于从起点开始的真实距离的情况下可以保证找到最短路径。当启发值变得越来越小的时候，A*就逐步变成Dijkstra算法。当启发值变得越来越大的时候，A*就会逐步变成贪婪最佳优先搜索。
关于性能呢？你最需要做的事情就是一出你图中的冗余节点，如果是使用一个格子图的话，看这里。减小图的规模可以帮助所有的图搜算法加快速度，然后，用你可以用的最简单的算法，队列越简单，算法运行越快。贪婪最佳优先算法通常比Dijkstra算法运行地更快，但是不能产出最优路径。一般寻路需求下A*算法通常都会是一个比较好的选择。
关于没有地图的情况呢？使用地图来举例是因为我认为用地图可以助于理解算法的运行原理。然而，图搜算法除了游戏地图外可以用在各种各样的图上。我已经设法在不依赖于2D格子的方向上去呈现算法代码，地图上的移动消耗可以是图边上的任意权重，启发函数并不能很简单得翻译给任意地图，你必须给不同类型的图设计不同的启发函数。对于平面地图，使用距离来作为启发值是一个好选择，所以我们在这里也是这么用的。
我在这里写了很多关于寻路的内容。记住，图搜仅仅是你需要的内容的一部分而已，A*算法本身并不会去处理诸如协同移动、移动障碍物、更改地图、危险区域评估、编队、转弯半径、对象大小、动画、路径平滑等内容。
