第1部分。通用搜索算法
引言
寻找路径是游戏开发人员通常最困难的主题之一。 尤其是，人们对
A *算法的理解很差，许多人认为这是某种不可理解的魔术。
本文的目的是以一种非常容易理解和可访问的方式来解释对路径的一般搜索，尤其是对
A *的搜索，从而消除了人们普遍认为该主题很复杂的误解。 有了正确的解释，一切都很简单。
请注意，在本文中，我们将考虑寻找一种
游戏方式 ； 与其他学术文章不同，我们将省略深度优先或广度优先之类的搜索算法。 相反，我们将尝试尽快从零到
A * 。
在第一部分中，我们将解释找到路径的最简单概念。 通过理解这些基本概念，您将意识到
A *非常明显。
简单电路
尽管您可以将这些概念应用于任意复杂的3D环境，但让我们从一个非常简单的方案开始：一个5 x 5的正方形网格，为方便起见，我用大写字母标记了每个单元格。
简单的网格。我们要做的第一件事就是将这个环境想象成一个图形。 我不会详细解释什么是图形。 简而言之，这是一组由箭头连接的圆圈。 圆圈称为
“结” ，箭头
称为“边缘” 。
每个节点表示字符可能处于的
“状态” 。 在本例中，角色的状态就是他的位置，因此我们为每个网格单元创建一个节点：
表示网格单元的节点。现在添加肋骨。 它们指示可以从每个给定状态
“到达”的状态。 在我们的情况下，我们可以从任何一个单元进入下一个单元，但被阻止的单元除外：
弧表示网格单元之间的允许移动。如果我们可以从
A到达
B ，那么我们说
B是
A节点的
“邻居” 。
值得注意的是肋骨有
方向 ; 我们需要从
A到
B以及从
B到
A的边。 这似乎是多余的，但是当可能出现更复杂的“条件”时却不是。 例如，角色可能会从屋顶掉到地板上，但不能从地板跳到屋顶。 您可以从“活动”状态转到“死”状态，反之则不行。 依此类推。
例子
假设我们要从
A移到
T。 我们从
A开始
。 您可以执行两个操作：转到
B或转到
F。假设我们搬到了
B。 现在我们可以做两件事：返回
A或转到
C。 我们记得我们已经进入
A并考虑了那里的选项，因此再做一次是没有意义的（否则我们可以整日移动
A →
B →
A →
B ...）。 因此，我们将转到
C。在
C语言中 ，我们无处可去。 返回
B是没有意义的，也就是说，这是一个死胡同。 当我们在
A中时，选择过渡到
B是一个坏主意； 也许您应该改用
F ？
我们只是不断重复这个过程，直到我们进入
T。 此刻，我们仅从
A重新创建路径，返回步骤即可。 我们在
T ; 我们怎么到达那里？ 来自
o吗？ 也就是说，路径的末端具有
O →
T的形式
。 我们怎么到
O的 ？ 依此类推。
请记住，我们并没有真正
动起来 ； 所有这一切只是一个思考过程。 我们将继续站在
A内 ，直到找到完整的路径，我们才会离开它。 当我说“移至
B ”时，是指“想象我们移至
B ”。
通用算法
这部分是整篇文章中最重要的部分 。 您绝对
必须理解它才能实现搜索的方式； 其余的（包括
A * ）只是细节。 在本节中，您将了解直到
理解其中的含义 。
此外，本节非常简单。
让我们尝试形式化我们的示例，将其转换为伪代码。
我们需要跟踪我们知道如何从起始节点到达的节点。 在开始时，这只是起始节点，但是在“探索”网格的过程中，我们将学习如何到达其他节点。 让我们将此节点称为
reachable列表：
reachable = [start_node]
我们还需要跟踪已经检查过的节点，以免再次考虑它们。
explored称他们为
explored ：
explored = []
接下来，我将概述算法的核心 ：在搜索的每个步骤中，我们选择一个知道如何到达的节点之一，并查看可以从中获得哪些新节点。 如果我们确定如何到达最终（目标）节点，那么问题就解决了！ 否则，我们将继续搜索。
如此简单，什至令人失望？ 这是真的。 但这就是整个算法。 让我们用伪代码逐步记录下来。
我们继续搜索，直到到达最终节点（在这种情况下，我们找到从初始节点到最终节点的路径），或者直到用尽了可以搜索的节点为止（在这种情况下，开始节点和结束节点之间没有办法） 。
while reachable is not empty:
我们选择一个我们知道如何获得并且尚未进行调查的节点之一：
node = choose_node(reachable)
如果我们只是学习了如何到达最终节点，那么任务就完成了！ 我们只需要通过遵循
previous链接回到起始节点来构建路径：
if node == goal_node: path = [] while node != None: path.add(node) node = node.previous return path
多次检查该节点没有任何意义，因此我们将跟踪此情况：
reachable.remove(node) explored.add(node)
我们确定无法从此处到达的节点。 我们从与当前节点相邻的节点列表开始，然后删除已经检查过的节点：
new_reachable = get_adjacent_nodes(node) - explored
我们将它们中的每一个：
for adjacent in new_reachable:
如果我们已经知道如何到达该节点，请忽略它。 否则，将其添加到
reachable列表，跟踪其进入方式：
if adjacent not in reachable: adjacent.previous = node
查找结束节点是退出循环的一种方法。 第二个是
reachable变为空：我们已经用完了可以探索的节点，而我们还没有到达最终节点，也就是说，从初始节点到最终节点没有办法：
return None
而且...就是这样。 这是整个算法，并且路径构造代码是通过单独的方法分配的：
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
这是构建路径的功能，它遵循
previous链接回到起始节点：
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
仅此而已。
这是 每个路径搜索算法
的伪代码，包括
A * 。
重新阅读本节，直到您了解一切正常工作，更重要的是，
为什么一切正常。 最好在纸上手工绘制一个示例，但您也可以观看一个交互式演示：
互动演示
这是上述算法的演示和实现示例（您可以
在原始文章的
页面上运行它）。
choose_node只是选择一个随机节点。 您可以逐步启动算法，并查看
reachable和
explored的列表，以及
previous链接指向的位置。
请注意，一旦检测到路径，搜索就会结束； 有可能甚至没有考虑某些节点。
结论
这里介绍的算法是
任何路径搜索算法的通用算法。
但是，每种算法之间的区别是什么，为什么
A *是
A * ？
提示：如果在演示中多次运行搜索，您会发现该算法实际上并不总是找到相同的路径。 他找到
了一条路，而这条路不一定是
最短的 。 怎么了
第2部分。搜索策略
如果您没有完全理解上一节中描述的算法，请返回并重新阅读，因为这是理解更多信息的必要条件。 当您弄清楚时，
A *对您而言似乎是完全自然和合乎逻辑的。
秘密成分
在上一部分的结尾，我留下了两个问题：如果每种搜索算法使用相同的代码，为什么
A *的行为类似于
A * ？ 为什么演示有时会找到不同的路径？
这两个问题的答案都是相互关联的。 尽管算法定义明确，但我仍未解决一个方面，事实证明，这是解释搜索算法行为的关键：
node = choose_node(reachable)
正是这个看起来很天真的字符串将所有搜索算法区分开来。
choose_node取决于
choose_node的实现方法。
那么，为什么演示会找到不同的路径？ 因为它的
choose_node方法会随机选择一个节点。
长度很重要
在深入研究
choose_node函数的行为差异之前，我们需要对上述算法进行小的监督。
当我们考虑与当前节点相邻的节点时，我们忽略了那些已经知道如何实现的节点：
if adjacent not in reachable: adjacent.previous = node
这是一个错误：如果我们只是发现实现这一目标的
最佳方法该怎么办？ 在这种情况下，必须更改
previous节点链接以反映此较短的路径。
为此，我们需要知道从起始节点到任何可达节点的路径长度。 我们将其称为路径成本。 现在，我们假设从一个节点移动到相邻节点之一的成本为
1 。
开始搜索之前，我们将每个节点的
cost值分配给
infinity ； 因此，
任何路径都会比这更短。 我们还将
start_node节点的
cost设置为
0 。
然后是以下代码：
if adjacent not in reachable: reachable.add(adjacent)
相同的搜寻费用
现在让我们看一下
choose_node方法。 如果我们努力寻找最短的路径，那么随机选择一个节点不是一个好主意。
最好选择一个我们可以从最短路径的初始节点到达的节点。 因此，我们通常更喜欢较短的路径而不是较长的路径。 这并不意味着完全不会考虑较长的路径，而是意味着首先会考虑较短的路径。 由于算法在找到合适的路径后立即终止，因此这应该使我们能够找到较短的路径。
这是
choose_node函数的可能示例：
function choose_node (reachable): best_node = None for node in reachable: if best_node == None or best_node.cost > node.cost: best_node = node return best_node
直观地，对该算法的搜索从起始节点开始“径向”扩展，直到到达终止节点为止。 这是此行为
的交互式演示 ：
结论
下面考虑的选择节点的方法进行了简单的更改，使我们获得了一个相当不错的算法：它找到了从起点到终点的最短路径。
但是这种算法在某种程度上仍然是“愚蠢的”。 他继续到处搜索，直到偶然发现一个终端节点。 例如，如果很明显我们正在远离末端节点，那么上面显示的示例在
A方向上搜索的意义是什么？
是否可以使
choose_node更智能？ 我们是否可以使
搜索直接指向终端节点 ，甚至无需事先知道正确的路径？
事实证明，我们可以-在接下来的部分中，我们终于到达
choose_node ，它使我们可以将常规路径搜索算法转换为
A * 。
第3部分。从A *中删除秘密的面纱
在上一部分中获得的算法非常好：它找到了从起始节点到最终节点的最短路径。 但是，他浪费了精力：他考虑了一个人明显地称之为错误的方式-他们通常
会偏离目标。 如何避免这种情况？
魔术算法
想象一下，我们在一台特殊的计算机上运行搜索算法，该计算机具有可以执行
魔术的芯片。 得益于这款出色的芯片，我们可以
choose_node非常简单的方式来表达
choose_node ，从而确保创建最短路径，而不会浪费时间探索毫无结果的部分路径：
function choose_node (reachable): return magic(reachable, " , ")
听起来很诱人，但是魔术芯片仍然需要某种低级代码。 这是一个很好的近似值：
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = magic(node, " ") total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
这是选择下一个节点的好方法：选择一个节点，该节点使我们拥有从起点到终点的最短路径，这正是我们所需要的。
我们还最小化了魔术的使用量：我们确切知道从起始节点移动到每个节点的成本（这是
node.cost ），并且我们仅使用魔术来预测从节点移动到最终节点的成本。
不是魔法，而是很棒的A *
不幸的是，魔术芯片是新的，我们需要过时的设备的支持。 除了以下这一行外，大多数代码都适合我们：
也就是说，我们不能使用魔术来找出未探索路径的成本。 好吧，让我们做个预测。 我们将保持乐观，并假设当前节点与最终节点之间没有任何关系，我们可以直接移动：
cost_node_to_goal = distance(node, goal_node)
请注意，
最短路径和
最小距离是不同的：最小距离表示当前节点与最终节点之间绝对没有障碍。
该估计非常容易获得。 在我们的网格示例中，这是两个节点之间
的城市街区距离 （即
abs(Ax - Bx) + abs(Ay - By) ）。 如果我们可以沿对角线移动，则该值将为
sqrt( (Ax - Bx)^2 + (Ay - By)^2 ) ，依此类推。 最重要的是，我们永远不会获得
过高的价值估算。
因此，这是
choose_node的非
choose_node版本：
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
估计从当前节点到最终节点的距离的函数称为
启发式 ，此搜索算法（女士和先生们）称为...
A * 。
互动演示
当您从意识到神秘的
A *实际上
如此简单而引起的震惊中恢复过来时，您可以查看演示（或在
原始文章中运行它）。 您会注意到，与前面的示例不同，搜索花费很少的时间沿错误的方向移动。
结论
最后，我们得到了
A *算法，它仅是本文第一部分中描述的常规搜索算法，而第二部分中描述了一些改进，并使用
choose_node函数，该函数选择了我们估计与我们更接近的节点。终端节点。 仅此而已。
这是main方法的完整伪代码供您参考：
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
build_path方法：
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
这是
choose_node方法，将其转换为
A * ：
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
仅此而已。
但是为什么我们需要
第4部分 ？
既然您已经了解了
A *的工作原理，那么我想谈谈其应用中的一些令人惊奇的领域，这些领域不仅限于在单元格中查找路径。
第4部分。
本文的前三部分从路径搜索算法的基础开始，到对
A *算法的清晰描述结束。 从理论上讲，所有这些都是很棒的，但是了解这在实践中如何适用是完全不同的主题。
例如，如果我们的世界不是网格，会发生什么？
如果角色无法立即旋转90度怎么办？
如果世界是无尽的，如何建立图表？
如果我们不在乎路径的长度，但是我们依赖太阳能，并且我们需要尽可能地处于阳光下怎么办？
如何找到到达两个末端节点中任何一个的最短路径？
成本函数
在第一个示例中，我们寻找起点和终点之间的最短路径。 但是，我们没有将部分路径长度存储为可变
length ，而是将其称为
cost 。 怎么了
我们可以使
A *不仅寻找
最短的路径 ，而且寻找
最佳的路径，并且可以根据我们的目标选择“最佳”的定义。 当我们需要最短的路径时，成本就是路径的长度，但是，例如，如果要最小化燃料消耗，则需要使用它作为成本。 如果我们想最大化“在阳光下度过的时间”，那么成本就是没有阳光的时间。 依此类推。
在一般情况下，这意味着相应的成本与图形的每个边相关联。 在上面显示的示例中，该值是隐式设置的，并且始终被视为等于
1 ，因为我们计算了整个过程中的步骤。 但是我们可以根据我们要最小化的成本来更改肋骨的成本。
标准函数
假设我们的对象是一辆汽车，而他需要到达加油站。 任何加油将适合我们。 它以最短的路线到最近的加油站。
天真的方法是依次计算出每次加油的最短路径，并选择最短的路径。 这将起作用，但是这将是一个非常昂贵的过程。
如果我们可以用一种方法来替换一个
goal_node ，该方法可以在给定节点上判断其是否有限。 因此，我们可以同时搜索多个目标。 我们还需要修改启发式方法，以使其返回所有可能的终端节点的最小估计成本。
根据情况的具体情况，我们可能无法
完美地实现目标，否则可能会花费太多（如果通过半
is_goal_node地图发送角色，那么一英寸的差异重要吗？），所以当我们使用
is_goal_node方法时，它可以返回
true我们“足够亲密”。
不需要完全确定。
将世界表示为离散的网格可能不足以用于许多游戏。 以第一人称射击游戏或赛车游戏为例。 世界是离散的，但不能表示为网格。
但是，还有一个更严重的问题：如果世界是无止境的呢？ 在这种情况下，即使我们能够以网格的形式呈现它，我们也将无法构造与网格相对应的图形，因为它必须是无限的。
但是，并非一切都丢失了。 当然，对于图搜索算法，我们肯定需要一个图。 但是没有人说图表应该是
全面的 ！
如果仔细看一下算法，您会发现我们对整个图没有做任何事情； 我们在本地检查该图，从而获得可以从相关节点到达的节点。 从演示
A *可以看出，图的某些节点根本没有被研究。
那么，为什么不在研究过程中建立图表呢？
我们将角色的当前位置作为起始节点。 调用
get_adjacent_nodes它可以确定角色从给定节点移动并动态创建相邻节点的可能方式。
超越三个维度
即使您的世界是
真正的2D网格，也需要考虑其他方面。 例如，如果角色通常不能立即旋转90或180度怎么办？
每个搜索节点表示
的状态不必只是一个
位置 ; 相反，它可能包含任意复杂的值集。 例如，如果从一个单元格过渡到另一个单元格所需的时间为90度，则可以将角色的状态设置为
[position, heading] 。 每个节点不仅可以代表角色的位置，还可以代表他的注视方向； 图的新边缘（显式或间接）反映了这一点。
如果返回到原始的5x5网格，则初始搜索位置现在可以为
[A, East] 。 现在，相邻节点为
[B, East]和
[A, South] -如果要到达
F ，我们首先需要调整方向，以使路径采用
[A, East] ，
[A, South] ，
[F, South] 。
第一人称射击游戏？ 至少四个维度：
[X, Y, Z, Heading] 。 甚至
[X, Y, Z, Heading, Health, Ammo] 。
注意，状态越复杂，启发式函数应该越复杂。
*本身很简单； 艺术通常源于良好的启发式方法。
结论
本文的目的是彻底消除神话，即
A *是无法解密的神秘算法。 相反，我表明其中没有任何神秘之处，实际上，可以很简单地从头开始推论得出。
进一步阅读
阿米特·帕特尔（Amit Patel）有出色的
“ A *算法简介” （关于哈布雷的
翻译 ）（他关于其他主题的其他文章也很出色！）。