本文仅用于学习过程的记录和分享，由本人翻译自 redblobgames.com ，如有任何错误和纰漏望各位海涵。

在游戏中，我们经常需要找到从一个位置到达另一个位置的路径。我们不仅需要找到最短的距离，可能还需要考虑经过这段路程所耗费的时间。比如从星星（起点）到叉叉（终点）的最短路径。

如果地图是由图形形式表示的话，我们可以使用图形搜索算法来寻找这条路径。 A* 算法是图形搜索算法的一个广泛选择，而广度优先搜索（BFS）是最简单的图形搜索算法。

所以让我们从BFS开始，逐步探索并接近 A*吧~

地图表示

学习算法的第一件事就是理解数据。 输入的是什么数据？ 输出的是什么数据？

输入数据：图形搜索算法，包括 A*算法，将“图形”作为输入。 图形是一组位置 （蓝色路径节点）和它们之间的连接（绿色的路径连线）。 这是我使用 A* 算法的一张图：

A* 算法没法识别到任何其他内容。 它只能识别图形。 它不会知道某个物体是在室内还是室外，不知道某处是一个房间还是一个过道，也不知道这些区域有多大。 它只能识别图形，它也没法理解上面这张地图和下面这张的区别。

输出数据：A* 算法找到的路径是由路径节点和路径连线组成的，路径连线是个抽象的数学概念。 A* 会告诉你需要从一个位置移动到另一个位置，但不会告诉你如何操作。 请记住，它对房间或者通道一无所知； 它所识别的只是图形。 你必须决定 A* 所使用的路径连线是指从一个图形瓦片移动到另一个，还是沿着直线行走，或是打开一扇门，还是游泳或是沿着弯曲的路径奔跑。

权衡：对于任何给定的游戏地图，有许多不同的方法可以制作寻路图以提供给 A*。 上图将大多数通道变成了路径节点； 那如果我们把通道都改成路径连线呢 ?

或者如果我们使用寻路网格来表示呢？

寻路图没有必要与你使用的游戏地图相同。 网格游戏地图也可以使用非网格寻路图，反之亦然。 A* 使用越少的路径节点运行越快； 网格通常更易于使用，但会产生大量路径节点。 本文涵盖了 A* 算法，但不包括图形的设计； 有关图形设计的更多信息，请参见我的其他文章。 对于本文其余部分的解释，我将默认使用网格，因为它更容易让概念可视化。

算法

有很多算法可以在图形上运行。本文将囊括以下这些：

广度优先搜索 在各个方向上均等地探索。这是一个非常有用的算法，不仅适用于常规路径查找，还适用于程序地图生成、流场寻路、距离映射和其他类型的地图分析。

Dijkstra 算法（也称为统一成本搜索）让我们考虑需要探索路径的优先级。它不是平等地探索所有可能的路径，而是倾向于探索移动成本较低的路径。我们可以通过分配较低的移动成本来鼓励玩家在道路地形上移动，或是分配较高的成本来避开森林地形，或阻止玩家靠近敌人等等。当移动成本不同时，我们通常使用它而不是广度优先搜索。

A*算法 是对 Dijkstra 算法的修改，并针对单个目的地的情况进行了优化。 Dijkstra 算法可以找到起点到所有位置的路径； A* 只找出起点到一个位置，或几个位置中最近的路径。它优先考虑看上去更接近终点的路径。

我将从最简单的广度优先搜索开始，逐步添加特征，逐渐将其转变为 A*。

广度优先搜索

所有这些算法的关键思想是，我们持续跟踪一个被称为边界frontier（蓝框方格）的持续扩展的环。 在网格中，这个过程有时被称为“洪水填充”，但同样的技术也适用于非网格。 连续观察以下图片，看看边界是如何扩展的：

我们该如何实现这样的过程？重复以下步骤，直到可取得的边界变为空：

1. 从边界中选择一个位置并移除。 （从编号为1-4的方格中选择1并移除）
   

2. 通过查找它的相邻位置（绿色方格）来扩展它。
   

   跳过障碍位置。
   

   将任何未到达的相邻位置添加到边界集合frontier和已到达点集合reached（5，6，7，8，9，10）  。

让我们近距离观察一下。 将图形瓦片按我们访问它们的顺序编号，逐步查看展开过程：

这些只需要十行Pythone代码：

这个循环是本文图形搜索算法的精髓，包括A*。 但是我们如何找到最短路径呢？ 这个循环实际上并没有构建路径； 它只告诉我们如何遍历地图上的所有位置。 这是因为广度优先搜索不仅仅用于查找路径，还可以用于更多用途。 在本文中，我展示了它是如何用于塔防游戏的，但它也可以用于距离映射、程序地图生成和许多其他事情。 尽管如此，在这里我还是想用它来寻找路径，所以让我们修改一下循环，以便追踪我们是从哪里到达的每个位置，并将已到达点集合 reached 重命名为 came_from 表（表的键就是过程中所到达的点 ):

现在，每个位置的 come_from 都指向我们来自的点的位置，就像“面包屑”一样。 它们足以重建整条路径了。

重建路径的代码很简单：从终点向后跟随箭头直到起点。 路径是一系列路径连线的集合，但通常存储路径节点来表示路径更容易一些：

这是最简单的一种寻路算法。 它不仅适用于此处所示的网格，也适用于任何类型的图形结构。 在地牢模型中，图形路径点可以是房间，图形路径连线可以是它们之间的门。 在平台游戏中，图形路径点可以是一个位置，而图形路径连线可能是一些动作，例如左移、右移、上跳、下跳。 大体上，图形可以被视为改变状态的阶段和动作。 我在这里（文章：地图表示）写了更多关于地图表示的文章。 在本文的剩余部分中，我将继续使用带有网格的示例，并探讨为什么我们可能会需要使用广度优先搜索的变体。

提前退出

我们已经找到了从一个位置到所有其他位置的路径。 通常来说，我们并不需要所有的路径； 我们只需要从一个位置到另一个位置的路径。 一旦找到终点，我们就可以停止扩展边界。 随着叉叉的移动，观察边界到达目标点后如何停止扩展。

代码也很简单：

关于提前退出的条件，你可以自己尝试很多有趣的设置。

移动成本

到目前为止，我们的 每步移动 都具有相同的“成本”。 在某些寻路场景中，不同类型的移动所需要的成本是不同的。 例如在游戏《文明》中，穿越平原或沙漠可能需要 1 个移动点，但穿越森林或丘陵可能需要 5 个移动点。 在本文顶部的地图中，穿越水地形的移动成本是在草丛中行走的 10 倍。 另一个例子是网格地图上的对角线移动，其移动成本比轴向移动要高。 我们希望寻路逻辑能将这些成本也考虑在内。

让我们比较从起点开始的步数和距离起点的距离：

针对这种情况，我们需要 Dijkstra 算法（或称为统一成本搜索）。 那它与 广度优先搜索 有何不同呢？

为了追踪移动成本，我们添加一个新变量，cost_so_far，来追踪从起始位置开始的总移动成本。 在决定如何评估移动位置时，我们希望将移动成本也考虑在内； 让我们把路径点队列变成优先级队列。 一种不太明显的可能是，我们最终会以不同的成本多次访问一个位置，因此我们需要稍微改变一下逻辑。 如果一个位置从未到达过，我们先不将它添加到边界里，而如果到该位置的新路径优于之前的最佳路径，我们才添加它。

使用优先队列而不是常规队列会改变边界扩展的方式，等高线是观察这一点的一种方式。 观察以下图片，看看边界如何在森林中缓慢地扩展，以找到中央森林周围而不是穿过它的最短路径：

非 1 的移动成本允许我们探索更有趣的图形，而不仅仅是网格。 在文章顶部的地图中，移动成本由各个房间之间的距离决定。 移动成本也可用于根据与敌人或盟友的接近程度来避开或选择偏好区域。

实现算法的说明：我们希望这个优先级队列可以优先返回最低成本值。 在上述页面中，我展示了使用 heapq 来使Python中的 优先级队列 优先返回最小值，而在 C++ 中可以使用 std::priority_queue 配置以优先返回最小值。 此外，我在此文展示的 Dijkstra 算法和 A*算法 实现与算法教科书中的版本不同，它们更接近于所谓的统一成本搜索算法。 我在实现算法文章（文章：A*算法的实现）中描述了这些差异。

启发式搜索

使用 广度优先搜索 和 Dijkstra 算法，边界可以向各个方向扩展。 如果你试图找到通向所有位置或多个位置的路径，这是一个非常合理的选择。 然而，常见的情况是，我们只需要找到到达某个特定位置的路径，让我们试着使边界向终点扩展多于向其他方向的扩展。 首先，我们将定义一个启发式函数，来告诉我们离终点的距离：

在 Dijkstra 算法中，我们使用离起点的实际距离来进行优先级队列排序。 这里相反，在 贪婪最佳优先搜索 中，我们将使用到达终点的预估距离进行优先级队列排序。 最接近终点的位置将最先被探索。 这段代码使用了 Dijkstra 算法中的优先级队列，但没有使用 cost_so_far：

让我们来看看它是如何运行的：

哇哦！是不是很神奇？

那在更复杂的地图中会发生什么呢？

我们发现，贪婪最佳优先搜索 得到的路径并不是最短的。 所以这个算法在地图上没有太多障碍物的情况下运行得更快，但得到的路径并不是很理想。

那我们能解决这个问题吗？ 当然可以！

A星算法

Dijkstra 算法可以很好地找到最短路径，但它会浪费时间探索没有希望的方向。 贪婪最佳优先搜索 会优先探索有希望的方向，但可能会找不到最短的路径。 而A* 算法既使用离起点的实际距离，也使用到终点的预估距离。

它的代码与 Dijkstra 算法非常相似：

比较这些算法：Dijkstra 算法计算离起点的距离。 贪婪最佳优先搜索 预估到终点的距离。

A* 则使用这两个距离的总和。

当我们尝试在墙上的各个地方开一个洞，我们会发现，当贪婪的最佳优先搜索找到正确的答案时，A* 也会找到它，并探索了相同的区域。

当贪婪的最佳优先搜索找到错误的答案（更长的路径）时，A* 会找到正确的答案，就像 Dijkstra 算法一样，但仍然比 Dijkstra 算法探索的区域少。

A* 是两全其美的。 只要启发式方法没有高估距离，A* 就会找到一条最佳路径，就像 Dijkstra 算法所做到的那样。 A* 使用启发式函数对路径节点进行重新排序，以便更有可能并更快地到达目标节点。

然后…就是这些了！ 这就是 A星算法。

更多

你准备好实现它了吗？考虑使用现有的库吧。如果你准备自己实现它，我有一个配套指南（文章：A*算法的实现），它逐步展示了如何在 Python、C++ 和 C# 中实现图形、队列和寻路算法。

我应该使用哪种算法在游戏地图上寻找路径呢？    

• 如果你想查找来自或到达所有位置的路径，请使用 广度优先搜索 或 Dijkstra 算法。如果移动成本都相同，使用广度优先搜索；如果移动成本不同，则使用 Dijkstra 算法。    
  

• 如果你想查找到一个特定位置或几个目标中最近的位置的路径，请使用 贪婪最佳优先搜索 或者 A*，在大多数情况下 A*是首选。当你想使用 贪婪最佳优先搜索 时，请考虑使用带有“inadmissible” *启发式函数的 A*。

那么关于最优路径呢？

广度优先搜索 和 Dijkstra 算法可以保证在给定输入图形的情况下找到最短路径，贪婪最佳优先搜索 则不能。如果启发式函数返回值永远不大于真实距离，则 A* 一定会找到最短路径。随着启发式值的减小，A* 变成了 Dijkstra 算法。随着启发式值的变大，A* 变成贪婪最佳优先搜索。 

这些算法的性能消耗如何？

最好的办法是消除图形节点中不必要的位置。如果使用网格，请参阅此（文章：网格寻路优化）。减小寻路图的规模有助于所有图形搜索算法。在此之外，使用最简单的算法；更简单的队列也会运行得更快。 贪婪最佳优先搜索 通常比 Dijkstra 算法运行得更快，但不能产生最优路径。 A* 是大多数寻路需求的不错选择。

如果是没有地图的情况呢？

我在这里展示地图是因为我认为使用地图更容易理解算法的运行原理。但是，这些图形搜索算法可以用于任何类型的图形，不仅仅是游戏地图。而且我也尝试过以不依赖于 2D 网格的方式呈现算法代码，比如将地图上的移动成本改变为图形路径连线上的任意权重。启发式方法则不那么容易转化为任意地图。您必须为每种类型的图都设计一个启发式方法。对于平面地图，计算距离是一个不错的选择，就像我在这篇文章里所使用的。

我在这里写了很多关于寻路的文章（redblobgames.com）。请记住，图形搜索只是你所需要的一部分内容。 A* 算法本身并不能处理诸如协同移动、移动障碍物、地图更改、危险区域评估、阵型编队、转弯半径、对象大小、动画、路径平滑之类的许多其他问题。

*注：“inadmissible” heuristic：https://en.wikipedia.org/wiki/Admissible_heuristic

感谢你看到这里。

如果你也正在学习寻路算法，请点赞或投币支持一下吧，让我有更多动力翻译更多的文章。

谢谢~