创建于2014年5月26日，更新于2014年8月、2016年2月、2016年6月、2020年6月。在游戏中，我们经常想找到从一个地点到另一个地点的路径。我们不仅在努力寻找最短的距离；我们还要考虑旅行时间。移动blob（起点）和cross（终点）以查看最短路径。
为了找到这条路径，我们可以使用一个图搜索算法，当地图被表示为一个图时，该算法就会起作用。A*是图形搜索的常用选择。广度优先搜索是最简单的图搜索算法，所以让我们从这里开始，我们将逐步发展到A*。
学习算法时要做的第一件事是理解数据。输入是什么？输出是什么？
输入：图形搜索算法，包括A*，以“图形”作为输入。图是一组位置（“节点”）以及它们之间的连接（“边”）。这是我给A*的图表：
A*看不到其他任何东西。它只看到图表。它不知道某物是室内还是室外，或者是房间还是门口，或者一个区域有多大。它只看到图表！它不知道这张地图和其他地图的区别。
输出：A*找到的路径为。边是抽象的数学概念。A*会告诉你从一个地方移动到另一个地方，但不会告诉你如何移动。记住，它对房间或门一无所知；它看到的只是图表。您必须确定由*返回的图形边是否意味着从一个图块移动到另一个图块，或是直线行走，或是开门，或是游泳，或是沿着弯曲的路径跑步。
权衡：对于任何给定的游戏地图，有许多不同的方法可以制作一个路径查找图，以提供给*。上面的地图将大多数门口变成了节点；如果我们成功了呢？如果我们使用？
寻路图不必与游戏地图使用的相同。网格游戏地图可以使用非网格寻路图，反之亦然。A*运行最快，图形节点最少；网格通常更容易使用，但会产生大量节点。本页介绍A*算法，但不包括图形设计；有关图表的更多信息，请参见我的另一页[1]。对于本页其余部分的解释，我将使用网格，因为更容易将概念可视化。
有很多算法在图形上运行。我将介绍以下内容：
广度优先搜索在所有方向上都进行了同等的探索。这是一个非常有用的算法，不仅适用于常规路径查找，还适用于程序地图生成、流场路径查找、距离地图和其他类型的地图分析。
Dijkstra的算法（也称为统一成本搜索）让我们可以优先选择要探索的路径。与其平等地探索所有可能的路径，它更倾向于低成本的路径。我们可以分配更低的成本来鼓励在道路上移动，更高的成本来避免森林，更高的成本来阻止接近敌人，等等。当移动成本发生变化时，我们使用这种方法，而不是广度优先搜索。
A*是对Dijkstra算法的修改，该算法针对单个目的地进行了优化。Dijkstra算法可以找到所有位置的路径；A*查找到一个位置或几个位置中最近位置的路径。它优先考虑那些似乎更接近目标的路径。
我将从最简单的广度优先搜索开始，一次添加一个功能，将其转换为*。
所有这些算法的关键思想是，我们跟踪一个称为“前沿”的不断扩大的环。在网格上，这个过程有时被称为“洪水填充”，但同样的技术也适用于非网格。启动动画以查看边界是如何扩展的→ →
通过观察它的邻居来扩展它。跳过墙壁。任何未到达的邻居，我们都会添加到边界和到达的集合中→ .
让我们近距离看看。瓷砖按我们参观的顺序编号。逐步查看扩展过程：
边疆。put（start）reach=set（）reach。添加（开始）而不是边界。空（）：当前=前沿。get（）表示图形中的下一个。邻居（当前）：如果未到达下一个：边界。放（下一个）到。添加（下一步）
这个循环是本页上图形搜索算法的精髓，包括*。但是我们如何找到最短的路径呢？循环实际上并不构成路径；它只告诉我们如何参观地图上的一切。这是因为广度优先搜索的用途远远不止于寻找路径；在本文中，我将展示如何将其用于塔防，但它也可以用于距离贴图、程序贴图生成，以及其他许多事情。在这里，虽然我们希望使用它来查找路径，但让我们修改循环，以跟踪每个到达的位置的来源，并将到达集重命名为come_from table（表的键是到达集）：
边疆。put（开始）comed_from=dict（）comed_from[start]=none而非front。空（）：当前=前沿。get（）表示图形中的下一个。邻居（当前）：如果下一个不在，来自边境。put（next）come_from（next）=当前
现在从每个地点到我们来的地方。这些就像“面包屑”。它们足以重建整条路。移动十字架，查看跟随箭头如何为您提供返回起始位置的反向路径。
重建路径的代码很简单：从目标到开始，沿着箭头向后走。路径是一系列边，但通常更容易存储节点：
当前=目标路径=[]当前！=开始：路径。append（current）current=来自[current]路径。附加（开始）#可选路径。反转（）#可选
这是最简单的寻路算法。它不仅适用于如图所示的网格，而且适用于任何类型的图形结构。在地牢中，图形位置可以是房间，也可以是房间之间的门口。在platformer中，图形位置可以是位置和图形边缘，包括可能的动作，如向左移动、向右移动、向上跳、向下跳。一般来说，将图形视为改变状态的状态和动作。我在这里写了更多关于地图表示的文章[2]。在本文的其余部分，我将继续使用网格示例，并探索为什么可能使用广度优先搜索的变体。
我们找到了从一个位置到所有其他位置的路径。通常我们并不需要所有的路径；我们只需要一条从一个位置到另一个位置的路径。一旦找到目标，我们就可以停止扩张边境。拖动鼠标，查看边疆在到达目标后如何停止扩张。
边疆。put（开始）comed_from=dict（）comed_from[start]=none而非front。空（）：当前=前沿。get（）如果当前==目标：在图中为下一个中断。邻居（当前）：如果下一个不在，来自边境。put（next）come_from（next）=当前
到目前为止，我们已经采取了同样的“成本”措施。在某些寻路场景中，不同类型的移动会产生不同的成本。例如，在文明中，穿越平原或沙漠可能需要1个移动点，但穿越森林或丘陵可能需要5个移动点。在页面顶部的地图上，在水中行走的费用是在草地上行走的10倍。另一个例子是网格上的对角线移动，其成本高于轴向移动。我们希望探路者考虑到这些成本。让我们比较一下从起点到终点的步数和距离：
为此，我们需要Dijkstra算法（或统一成本搜索）。它与广度优先搜索有何不同？我们需要跟踪移动成本，所以让我们添加一个新变量cost_so_far，以跟踪从起始位置开始的总移动成本。在决定如何评估地点时，我们希望将移动成本考虑在内；让我们把队列变成优先队列。不太明显的是，我们可能会多次访问一个地点，花费不同，所以我们需要稍微改变一下逻辑。如果从未到达某个位置，我们不会向边界添加位置，而是在该位置的新路径优于之前的最佳路径时添加该位置。
边疆=优先队列（）边疆。put（start，0）come_from=dict（）cost_so_far=dict（）come_from[start]=Nonecost_so_far[start]=0而不是frontier。空（）：当前=前沿。get（）如果当前==目标：在图中为下一个中断。邻居（当前）：新成本=成本迄今为止[当前]+图表。成本（当前、下一个）如果下一个不在成本中，则当前或新成本<；成本迄今[下一步]：成本迄今[下一步]=新成本优先级=新成本前沿。put（next，priority）来自[next]=当前
使用优先级队列而不是常规队列会改变边界扩展的方式。轮廓线是观察这一点的一种方式。启动动画，查看边界如何在森林中缓慢扩展，找到围绕中心森林的最短路径，而不是穿过森林：
除1以外的移动成本使我们能够探索更有趣的图形，而不仅仅是网格。在页面顶部的地图中，移动成本基于房间之间的距离。移动成本也可以用于避开或选择基于接近敌人或盟友的区域。
实现说明：我们希望这个优先级队列首先返回最低值。在实现页面上，我用Python显示PrimeRealQuey，使用HeAPQ返回第一个值，在C++中使用STD：：PrimRythyQueQue2被配置为首先返回最低值。此外，Dijkstra算法的版本和我在这一页上展示的A*与算法教科书中的不同。它更接近于所谓的统一成本搜索。我在实现页面上描述了这些差异。
通过广度优先搜索和Dijkstra算法，前沿向各个方向扩展。如果你想找到一条通往所有地点或多个地点的路径，这是一个合理的选择。然而，常见的情况是只找到一个位置的路径。让我们让前沿朝着目标扩展，而不是向其他方向扩展。首先，我们将定义一个启发式函数，告诉我们离目标有多近：
def启发式（a，b）：#正方形网格上的曼哈顿距离返回abs（a.x-b.x）+abs（a.y-b.y）
在Dijkstra算法中，我们使用了从起点到优先级队列排序的实际距离。相反，在贪婪的最佳优先搜索中，我们将使用到优先级队列排序目标的估计距离。首先探索距离目标最近的位置。代码使用Dijkstra算法中的优先级队列，但迄今为止没有成本：
边疆=优先队列（）边疆。put（start，0）come_from=dict（）come_from[start]=none而非frontier。空（）：当前=前沿。get（）如果当前==目标：在图中为下一个中断。邻居（当前）：如果下一个不在，来自：优先级=启发式（目标，下一个）边界。put（next，priority）来自[next]=当前
这些路径不是最短的。因此，当没有太多障碍物时，该算法运行得更快，但路径没有那么好。我们能解决这个问题吗？对
Dijkstra的算法可以很好地找到最短路径，但它会浪费时间去探索那些没有前途的方向。贪婪的“最佳优先搜索”（Best First Search）朝着有希望的方向探索，但它可能找不到最短的路径。A*算法使用从起点到目标的实际距离和估计距离。
边疆=优先队列（）边疆。put（start，0）come_from=dict（）cost_so_far=dict（）come_from[start]=Nonecost_so_far[start]=0而不是frontier。空（）：当前=前沿。get（）如果当前==目标：在图中为下一个中断。邻居（当前）：新成本=成本迄今为止[当前]+图表。成本（当前、下一个）如果下一个不在成本中，则当前或新成本<；cost_so_far[下一步]：cost_so_far[下一步]=新成本优先级=新成本+启发式（目标，下一步）前沿。put（next，priority）来自[next]=当前
比较算法：Dijkstra的算法计算从起点到终点的距离。贪婪的最佳优先搜索估计到目标点的距离。A*是这两个距离的总和。
试着在墙上不同的地方开个洞。你会发现，当贪婪的Best First Search找到正确答案时，A*也会找到它，探索同一个区域。当贪婪的Best First搜索找到错误的答案（路径更长）时，A*会像Dijkstra的算法一样找到正确的答案，但仍然比Dijkstra的算法探索得更少。
A*是两个世界中最好的。只要启发式算法不会高估距离，A*就会像Dijkstra算法一样找到一条最优路径。A*使用启发式对节点进行重新排序，以便更有可能更快地遇到目标节点。
你准备好实施了吗？考虑使用现有的库。如果你自己实现它，我有同伴指南，它一步一步地展示如何在Python、C++和C语言中实现图、队列和寻路算法。
如果你想找到所有位置之间的路径，可以使用广度优先搜索或Dijkstra算法。如果移动成本相同，则使用广度优先搜索；如果移动成本不同，请使用Dijkstra算法。
如果你想找到一个位置的路径，或者几个目标中最近的一个，使用贪婪的最佳优先搜索或A*。在大多数情况下，我更喜欢A。当你想使用贪婪的第一次搜索时，考虑使用一个带有“不允许”的启发式算法* [3 ]。
最优路径呢？宽度优先搜索和Dijkstra算法保证在给定输入图的情况下找到最短路径。贪婪的最好的第一次搜索不是。如果启发式永远不超过真实距离，则A*保证找到最短路径。随着启发式变得更小，A*变成了Dijkstra算法。随着启发式变得更大，A*变成贪婪的最佳优先搜索。
表现如何？最好的办法是消除图表中不必要的位置。如果使用网格，请参见此。缩小图的大小有助于所有的图搜索算法。之后，使用最简单的算法；简单的队列运行得更快。贪婪的最佳优先搜索通常比Dijkstra算法运行得更快，但不会产生最优路径。对于大多数寻路需求来说，A*是一个不错的选择。
非地图呢？我在这里展示地图是因为我认为使用地图更容易理解算法的工作原理。然而，这些图形搜索算法可以用于任何类型的图形，而不仅仅是游戏地图，我试图以一种独立于2d网格的方式呈现算法代码。地图上的移动成本变成了图边上的任意权重。启发式算法不容易转化为任意的地图；你必须为每种类型的图设计一个启发式。对于平面地图，距离是一个很好的选择，所以这就是我在这里使用的。
我在这里有更多关于寻路的文章[4]。记住，图形搜索只是你需要的一部分。A*本身不会处理诸如协同移动、移动障碍物、地图更改、危险区域评估、编队、转弯半径、对象大小、动画、路径平滑等问题。
版权所有©2022 Red Blob Games RSS源引用：Patel、Amit和#34；A*算法简介"；，红点游戏，2014，https://www.redblobgames.com/pathfinding/a-star/introduction.html@文章{article，author={Patel，Amit}，title={A*算法简介}，年份={2014}，注={https://www.redblobgames.com/pathfinding/a-star/introduction.html}}
在conrec的帮助下于2014年5月26日创建。js；斯塔拉文的草图绘制画笔中的地图精灵；最后修改：25 DEC 2021