A *(发音为A-star)算法对于初学者可能是复杂的。虽然网上有很多文章解释A *,但大多数文章是为那些了解基本知识的人写的。本文是为真正的初学者。 

本文不试图成为这个主题的最终工作。相反,它描述了基本原理,并准备你出去阅读所有这些其他材料,并了解他们在说什么。本文末尾提供了一些最好的链接,在下一步阅读。

最后,本文不是程序特定的。你应该能够适应这里的任何计算机语言。但是,正如您所期望的,我在本文末尾提供了一个示例程序的链接。示例包包含两个版本:一个在C + +和一个在Blitz Basic。它也包含可执行文件,如果你只是想看到A *在行动。 

但我们正在领先自己。让我们从头开始…

简介:搜索区

让我们假设我们有一个人想从点A到点B.让我们假设一个墙分隔了两个点。这在下面示出,其中绿色是起点A,红色是终点B,并且蓝色填充的方块是其间的壁。

你应该注意的第一件事是,我们将搜索区域划分为正方形网格。简化搜索区域,正如我们在这里所做的,是寻路的第一步。这种特定的方法将我们的搜索区域减少为简单的二维数组。数组中的每个项目表示网格上的一个正方形,其状态记录为可步行或不可越轨。通过找出我们应该采取哪些正方形从A到B找到路径。一旦找到路径,我们的人从一个正方形的中心移动到下一个的中心,直到到达目标。 

这些中心点称为“节点”。当你阅读其他地方的寻路时,你会经常看到有人讨论节点。为什么不直接叫他们广场?因为可以将你的寻路区域划分为除正方形以外的东西。它们可以是矩形,六边形,三角形或任何形状,真的。并且节点可以放置在形状内的任何地方 – 在中心或沿边缘,或任何其他地方。我们使用这个系统,但是,因为它是最简单的。

开始搜索

一旦我们将搜索区域简化为可管理的节点数,就像我们上面的网格布局一样,下一步是进行搜索以找到最短路径。我们从点A开始,检查相邻的正方形,并且通常向外搜索,直到找到我们的目标。 

我们通过执行以下操作开始搜索:

  1. 从起始点A开始,并将其添加到要考虑的正方形的“打开列表”。开放的列表就像一个购物清单。现在列表上只有一个项目,但我们以后会有更多。它包含可能沿着你想要走的路径落下的方块,但也许不是。基本上,这是一个需要检出的方格列表。  
  2. 看看所有可及的或可步行的广场相邻的起点,忽略与墙壁,水或其他非法地形的广场。也将它们添加到打开的列表中。对于这些正方形中的每一个,将点A保存为其“父平方”。当我们想要跟踪我们的路径时,这个父方块的东西很重要。这将在后面解释。  
  3. 从你打开的列表中删除开始的方格A,并将其添加到正方形的“封闭列表”,你现在不需要再看。

在这一点上,你应该有类似下面的插图。在此图中,中心的深绿色正方形是您的起始正方形。它以浅蓝色标出,表示该方形已添加到已关闭的列表中。所有相邻的正方形现在都在要检查的开放的正方形列表上,它们以浅绿色轮廓。每个都有一个灰色指针,指向它的父对象,这是开始的方块。 

接下来,我们选择开放列表上的相邻正方形之一,并且或多或少重复较早的过程,如下所述。但是我们选择哪个广场呢?F成本最低的一个。

路径评分

确定在计算路径时使用哪个方块的关键是以下公式:

F = G + H 

哪里

  • G =从起点A移动到网格上给定正方形的运动成本,根据生成的路径到达。 
  • H =从网格上的给定平方移动到最终目的地(点B)的估计移动成本。这通常被称为启发式,这可能是有点混乱的。之所以被称为是因为它是一个猜测。我们真的不知道实际的距离,直到我们找到路径,因为各种各样的事情可以在路上(墙壁,水等)。您在本教程中给出了一种计算H的方法,但是有许多其他方法可以在网络上的其他文章中找到。

我们的路径是通过重复浏览我们的打开列表并选择具有最低F分数的正方形来生成的。这个过程将在文章中进一步更详细地描述。首先,我们更仔细地看看我们如何计算方程。

如上所述,G是使用生成的路径从起点移动到给定平方的移动成本。在本示例中,我们将为移动的每个水平或垂直方块分配10的成本,对角线移动的成本为14。我们使用这些数字,因为对角线移动的实际距离是2的平方根(不要害怕),或大约是水平或垂直移动成本的1.414倍。为了简单起见,我们使用10和14。比率大约是正确的,我们避免必须计算平方根,我们避免小数。这不只是因为我们是哑的,不喜欢数学。使用这样的整数对于计算机来说也快得多。正如你很快会发现的,寻路可能非常慢,如果你不使用这样的捷径。 

由于我们正在计算沿给定平方的特定路径的G成本,计算该平方的G成本的方法是取其父成本的G成本,然后根据其是对角线还是对角线添加10或14正交(非对角线)。在这个例子中,对于这种方法的需要将变得显而易见,因为我们从开始的方格开始超过一个方格。

H可以以多种方式估计。我们在这里使用的方法称为曼哈顿方法,其中您计算从当前正方形到达目标正方形水平和垂直移动的总平方数,忽略对角线运动,忽略任何可能会阻碍的障碍。然后我们将总和乘以10,我们的水平或垂直移动一个方块的成本。这是(可能)称为曼哈顿方法,因为它就像计算从一个地方到另一个城市街区的数量,在那里你不能对角地切开块。

阅读这个描述,你可能会猜测,启发式只是一个粗略估计当前广场和目标之间的剩余距离“随着乌鸦飞行。这不是这样的。我们实际上试图估计沿着路径(通常更远)的剩余距离。我们的估计越接近实际剩余距离,算法将越快。如果我们高估这个距离,但是,不能保证给我们最短的路径。在这种情况下,我们有所谓的“不可接受的启发式”。

在技​​术上,在这个例子中,曼哈顿方法是不允许的,因为它稍微高估了剩余距离。但我们将使用它,无论如何,因为它是  很容易理解我们的目的,因为它只是一个轻微的高估。在极少数情况下,当得到的路径不是尽可能短的时候,它将几乎是短的。想了解更多?你可以在这里找到关于启发式的方程和附加注释。

F通过加上G和H来计算。我们的搜索的第一步的结果可以在下面的图中看到。在每个正方形中写入F,G和H得分。如开头正方形右边的正方形所示,F打印在左上角,G打印在左下角,H打印在右下角。

让我们来看看其中的一些方块。在其中具有字母的正方形中,G = 10。这是因为它在水平方向上从起始正方形起只有一个正方形。起始方格正上方,下方和左侧的方格都具有相同的G分数10.对角线方格的G分数为14。

H分数通过估计到红色目标正方形的曼哈顿距离来计算,仅仅水平和垂直地移动,并且忽略了在路上的墙。使用这种方法,开始的右边的正方形是从红色正方形的3个正方形,H的分数为30.正方形上方的正方形是4个正方形(记住,只有水平和垂直移动)H你可以看到如何计算其他方格的H分数。

同样,每个正方形的F分数通过将G和H一起相加来简单地计算。

继续搜索

要继续搜索,我们只需从打开的列表中的所有列中选择最低的F得分平方。然后,我们使用所选的正方形执行以下操作:

4) 从打开的列表中删除它,并将其添加到关闭的列表。

5)检查所有相邻的正方形。忽略那些位于已关闭列表上或不可覆盖(具有墙壁,水或其他非法地形的地形)的广告,如果开放列表中没有广告,请在打开的列表中添加正方形。将所选的方形作为新方格的“父”。

6)如果一个相邻的正方形已经在打开的列表中,请检查该方形的路径是否更好。换句话说,如果我们使用当前正方形到那里,检查该正方形的G得分是否更低。 如果没有,不要做任何事情。
另一方面,如果新路径的G成本较低,则将相邻正方形的父代更改为所选正方形(在上图中,将指针的方向更改为指向所选正方形)。最后,重新计算该正方形的F和G分数。如果这看起来很混乱,你会看到它如下图所示。

好吧,让我们看看这是如何工作的。在我们的最初的9个方格中,我们在开始的列表被切换到关闭列表之后,在开放列表上剩下8个。  其中,具有最低F成本的一个是起始方格的右边的一个,F分数为40.因此,我们选择这个正方形作为我们的下一个正方形。在下图中以蓝色突出 显示。

首先,我们从我们的打开列表中删除它,并将其添加到我们的关闭列表(这就是为什么它现在突出显示为蓝色)。  然后我们检查相邻的正方形。那么,在这个广场的右边的那些是墙上的正方形,所以我们忽略这些。左边的那个是起始广场。这是封闭的列表,所以我们也忽略了。 

其他四个正方形已经在打开的列表中,所以我们需要检查这些正方形的路径是否更好使用这个正方形到达那里,使用G分数作为我们的参考。让我们看看我们选择的正方形正上方的正方形。它的当前G分数是14.如果我们改为通过当前平方到达那里,G分数将等于20(10,即获得到当前正方形的G分数,再加上另外10分,垂直到一个就在它上面)。AG得分20高于14,所以这不是一个更好的路径。这应该有意义,如果你看看图。它更直接从起始的广场,通过简单地移动一个正方形对角线到达那里,而不是水平移动一个正方形,然后垂直一个正方形。 

当我们对已经在打开列表上的所有4个相邻正方形重复这个过程时,我们发现没有一个路径通过当前正方形改进,所以我们不改变任何东西。所以现在我们看了所有的相邻的正方形,我们完成了这个正方形,并准备移动到下一个正方形。 

因此,我们通过我们的开放名单上的正方形列表,现在下降到7个正方形,我们选择具有最低F成本的那个。有趣的是,在这种情况下,有两个方格的得分为54.所以我们选择哪个?这并不重要。为了速度的目的,它可以更快地选择您添加到打开列表中的最后一个。这使搜索偏向于在搜索中找到的方块,当您已经更接近目标时。但它并不重要。(关系的不同处理是为什么两个版本的A *可能找到不同的长度相等的路径。)

因此,让我们选择一个正下方,并开始方块的右边,如下面所示

这一次,当我们检查相邻的正方形,我们发现右边的那个是一个墙壁的正方形,所以我们忽略它。这同样适用于上面的那个。我们也忽略了墙下的正方形。为什么?因为你不能从当前广场直接到达那个广场,而不穿过附近墙壁的角落。你真的需要先下去,然后移动到那个广场,在过程中移动的角落。(注意:这个关于切角的规则是可选的,它的使用取决于节点的放置方式。)

剩下五个方块。当前正方形下方的其他两个正方形不在已打开的列表中,因此我们添加它们,当前正方形成为其父。在其他三个正方形中,两个已经在闭合列表上(起始正方形,以及刚好在当前正方形上方,在图中以蓝色突出显示),因此我们忽略它们。并且检查当前正方形的左边的最后一个正方形,以查看如果通过当前正方形到达那里,G得分是否更低。没有骰子。所以我们完成了,准备检查我们的开放名单上的下一个广场。 

我们重复这个过程,直到我们添加目标广场封闭列表,此时它看起来像 的下方。

请注意,起始正方形下方的两个正方形的正方形已从上一个 图示中更改。之前它的G得分为28,并指向回到上方的广场和右边。现在它的得分为20,并指向正上方的广场。这发生在我们的搜索过程中的某个地方,其中G分数被检查,并且结果是使用新的路径更低 – 所以父母被切换,G和F得分重新计算。虽然这个变化在这个例子中似乎不太重要,但是有很多可能的情况,这种常数检查将决定到目标的最佳路径的所有差异。 

那么我们如何确定路径呢?简单,只是从红色目标广场开始,向后工作,从一个方块移动到它的父方,跟着箭头。这将最终带你回到起始的广场,这是你的路。它应该如下图 所示。从起始方格A移动到目的地方格B仅仅是从每个正方形(节点)的中心移动到路径上下一个正方形的中心,直到到达目标。

A *方法的总结

好的,现在你已经通过了解释,让我们一步一步的方法在一个地方:

1)将开始方格(或节点)添加到打开的列表。

2)重复以下步骤:

a)在打开的列表上查找最低的F成本平方。我们将其称为当前正方形。

b)将其切换到关闭列表。

c)对于与当前正方形相邻的8个正方形中的每一个…

  • 如果它不是可走的或如果它在封闭的列表上,忽略它。否则请执行以下操作。
  • 如果它不在打开的列表上,请将其添加到打开的列表。使当前方形为该正方形的父代。记录广场的F,G和H成本。
  • 如果已经在打开的列表上,请检查该方块的路径是否更好,使用G成本作为度量。较低的G成本意味着这是一个更好的路径。如果是,将方形的父代更改为当前方形,然后重新计算方形的G和F分数。如果您按照F分数排序打开的列表,则可能需要使用列表来记录更改。

d)当您:

  • 将目标正方形添加到关闭列表中,在这种情况下,已找到路径(请参见下面的注释)或
  • 无法找到目标正方形,并且打开的列表为空。在这种情况下,没有路径。

3)保存路径。从目标广场向后工作,从每个广场到其父广场,直到到达起始广场。这是你的路。

注意:在本文的早期版本中,建议您可以在目标正方形(或节点)已添加到打开列表而不是已关闭列表时停止。这样做会更快,它几乎总是给你最短的路径,但不总是。这样做可能产生差异的情况是当从第二个节点移动到最后一个节点到最后一个(目标)节点的移动成本可能显着变化 – 例如,在两个节点之间的河流交叉的情况下。

执行注意事项 

现在你已经了解了基本的方法,这里有一些额外的事情要考虑当你编写自己的程序。以下材料中的一些参考了我在C ++和Blitz Basic中编写的程序,但这些要点在其他语言中同样有效。

1.其他单位(碰撞避免): 如果你仔细看看我的示例代码,你会注意到它完全忽略屏幕上的其他单位。单位通过彼此。根据游戏,这可能是可以接受的或可能不是。 如果要考虑寻径算法中的其他单位,并使它们相互移动,我建议您只考虑在计算路径时停止或邻近寻径单位的单位,将其当前位置视为不可解。对于正在移动的相邻单元,您可以通过惩罚沿着它们各自的路径的节点来阻止冲突,从而鼓励寻径单元找到备选路由(在#2下更多地描述)。

如果您选择考虑其他正在移动且不与寻路单元相邻的单元,则需要开发一种方法来预测它们在任何给定时间点的位置,以便正确地躲避。否则,你可能会得到奇怪的路径单位之字形,以避免其他单位,不再有。

当然,你还需要开发一些碰撞检测代码,因为无论路径在计算时有多好,事情都可能随时间而变化。当碰撞发生时,单元必须计算新的路径,或者如果另一个单元正在移动并且不是正面碰撞,则在继续当前路径之前等待另一个单元步进离开。

这些提示可能足以让你开始。如果您想了解详情,请参阅以下链接:

  • 自动角色的转向行为:Craig Reynold在转向上的工作与寻路有点不同,但它可以与寻路相结合,以实现更完整的移动和碰撞避免系统。
  • 电脑游戏中的转向长短:一个关于转向和寻路的文献的有趣的调查。这是一个pdf文件。
  • 协调单位运动:首先是帝国时代设计师Dave Pottinger的关于形成和基于群体的运动的两部分系列文章。
  • 实施协调运动:第二在Dave Pottinger的两部分系列。

2.可变地形成本: 在本教程和我的附带程序中,地形只是两个东西之一 – 可步行或不可越轨。但是如果你有地形是可步行的,但是运动成本更高?沼泽,丘陵,地牢中的楼梯等 – 这些都是可步行的地形的例子,但成本比平坦,开阔的地面更高。类似地,道路可能具有比周围地形更低的运动成本。

通过在计算任何给定节点的G成本时添加地形成本,可以轻松处理此问题。只需为这样的节点添加奖励成本。A *寻路算法已经写入以找到最低成本路径并且应该容易地处理这个。在我描述的简单例子中,当地形只是可步行或不可越轨时,A *将寻找最短,最直接的路径。但在成本可变的地形环境中,最小成本路径可能涉及行驶更长的距离 – 如在沼泽地周围的道路,而不是直接通过它。

一个有趣的额外考虑是专业人员称为“影响映射”。正如上面描述的可变地形成本一样,您可以创建一个附加点系统,并将其应用于AI目的的路径。想象一下,你有一个地图上有一堆防御通过山区的单位。每当计算机通过那个路径发送某人的路径,它就会被打。如果你想要的话,你可以创建一个影响地图,惩罚发生大量屠杀的节点。这将教会计算机支持更安全的路径,并帮助它避免愚蠢的情况,它不断发送军队通过特定的路径,只是因为它更短(但也更危险)。

另一种可能的用途是惩罚沿着附近移动单元的路径放置的节点。A *的缺点之一是当一组单元都尝试找到到类似位置的路径时,通常存在大量的重叠,因为一个或多个单元尝试对其目的地采取相同或相似的路线。对已由其他单元“声明”的节点添加惩罚将有助于确保一定程度的分离,并减少冲突。不要把这样的节点看作是不可解开的,但是,如果需要,你仍然希望多个单元能够在单个文件中挤压通过紧密的通道。此外,你应该惩罚单位的路径,在路径寻找单位,而不是所有的路径,或者你会得到奇怪的躲避行为,因为单位避免单位的路径,在当时不在附近他们。此外,您应该仅惩罚沿着路径的当前和未来部分的路径节点,而不是惩罚已经被访问和遗留的先前路径节点。

3.处理未开发区域: 你曾经玩过一个电脑游戏,其中计算机总是知道什么路径,即使地图还没有被探索?根据游戏,寻路太好可能是不现实的。幸运的是,这是一个可以很容易处理的问题。

答案是为每个玩家和计算机对手(每个玩家,而不是每个单元 – 需要更多的计算机内存)创建一个单独的“knownWalkability”数组。每个数组将包含关于玩家已经探索的区域的信息,地图的其余部分被假定为可行走,直到被证明否则。使用这种方法,单位将徘徊在死胡同,做出类似的错误选择,直到他们学会了他们的方式。一旦地图被探索,然而,寻路将正常工作。

4.平滑路径: A *将自动给你最短,最低成本的路径,它不会自动给你最平滑的路径。看看我们的示例中计算的最终路径(图7)。在这条道路上,第一步是在下面,并在起始广场的右边。如果第一步,而不是直接位于起始方格下方的方块,我们的路径不会更平滑吗?

有几种方法来解决这个问题。当你计算路径时,你可以惩罚节点的方向改变,增加一个惩罚他们的G分数。或者,您可以在计算之后运行您的路径,查找选择相邻节点的位置可以为您提供更好的路径。对于更多的整个问题,请查看更多的现实寻路,一个(免费,但需要注册)文章在Gamasutra.com由Marco Pinter。

5.非正方形搜索区域: 在我们的示例中,我们使用一个简单的2D方形布局。你不需要使用这种方法。您可以使用不规则形状的区域。想想棋盘游戏Risk,以及那个游戏中的国家。你可以为这样的游戏设计一个寻路方案。为此,您需要创建一个表格,用于存储与其相邻的国家以及与从一个国家移动到另一个国家相关联的G成本。你还需要想出一个估计H的方法。一切都将被处理与上面的例子相同。而不是使用相邻的正方形,当您在打开的列表中添加新项目时,您只需查找表中的相邻国家/地区。

同样,您可以为固定地形图上的路径创建一个航点。航点通常是路径上的横越点,可能是在地下城的道路或钥匙隧道上。作为游戏设计师,您可以预先分配这些路点。如果在它们之间的直接线路路径上没有障碍物,则两个航路点将被认为是彼此“相邻”。在Risk示例中,您可以将此邻接信息保存在某种查找表中,并在生成新的打开列表项时使用它。然后,您将记录相关的G成本(可能通过使用节点之间的直线距离)和H成本(可能使用从节点到目标的直线距离)。一切都会照常进行。

Amit Patel写了一篇简短的文章 探讨一些替代品。有关使用非正方形搜索区域在等长RPG图上搜索的另一示例,请查看我的文章Two-Tiered A * Pathfinding

  1. 有些超速提示: 当你开发自己的A *程序,或者改编我写的,你最终会发现寻路使用您的CPU沉重的大块,特别是如果你对的寻路台像样的数板和一个相当大的地图。如果你读网上的东西,你会发现这是真的,即使是设计游戏,如星际争霸或帝国时代的专业人士。如果你看到事情开始减慢,由于寻路,这里有一些想法,可能加速:
  • 考虑更小的地图或更少的单位。
  • 一次不要做路径查找超过几个单位。而是把它们放在一个队列中,并在几个游戏周期中展开。如果你的游戏以每秒40个周期运行,没有人会注意到。但是他们会注意到,如果游戏似乎每隔一段时间减慢一次,当一堆单位都是同时计算路径。
  • 请考虑使用较大的正方形(或您使用的任何形状)。这将减少搜索的节点总数以查找路径。如果你有雄心,你可以设计两个或更多的寻路系统,在不同的情况下使用,取决于路径的长度。这是专业人员做的,使用大面积的长路径,然后切换到更小的搜索使用较小的方块/区域,当你靠近目标。如果你对这个概念感兴趣,请查看我的文章Two-Tiered A * Pathfinding
  • 对于较长的路径,请考虑设计硬连线到游戏中的预先计算的路径。
  • 考虑预处理您的地图,以确定哪些区域无法从地图的其余部分访问。我把这些地区称为“岛屿”。在现实中,它们可以是岛屿或任何其他被隔离和不可访问的区域。A *的缺点之一是,如果你告诉它寻找到这样的区域的路径,它将搜索整个地图,只有当每个可访问的方形/节点已经通过打开和关闭列表处理时才停止。这可能浪费很多CPU时间。它可以通过预先确定哪些区域是不可访问的(通过洪水填充或类似的例程),在某种数组中记录该信息,然后在开始路径搜索之前检查它来防止。
  • 在一个拥挤,迷宫式的环境中,考虑标记节点,不会导致任何地方死胡同。这些区域可以在地图编辑器中手动预先指定,或者如果您有雄心,可以开发一种算法来自动识别这些区域。给定死端区域中的任何节点集合可以被给予唯一的标识号。然后,你可以安全地忽略所有死胡同在寻路时,暂停只考虑死区终端区域中的节点,如果起始位置或目的地恰好在特定的死角区域。

7.维护开放列表: 这实际上是A *寻路算法中最耗时的元素之一。每次访问打开的列表时,您需要找到具有最低F成本的正方形。有几种方法可以做到这一点。您可以根据需要保存路径项,并且每次需要找到最低的F成本平方时,只需浏览整个列表。这很简单,但对于长路径真的很慢​​。这可以通过维护一个排序列表,只需在每次需要最低的F成本平方时从列表中抓取第一个项目来改进。当我写我的程序,这是我使用的第一个方法。

这对于小地图工作相当好,但它不是最快的解决方案。Serious A *程序员想要真正的速度使用称为二进制堆的东西,这是我在我的代码中使用。根据我的经验,在大多数情况下,这种方法的速度至少要快2-3倍,而在更长的路径上,速度会快几十倍(快10倍)。如果你有兴趣了解更多关于二进制堆,请查看我的文章,在A * Pathfinding使用二进制堆

另一个可能的瓶颈是在寻路调用之间清除和维护数据结构的方式。我个人更喜欢将所有数据存储在数组中。虽然可以以动态的,面向对象的方式生成,记录和维护节点,但是我发现创建和删除这些对象所需的时间量增加了额外的,不必要的开销,从而减缓了事情。但是,如果使用数组,则需要在调用之间清理。在这种情况下,你最不愿意做的事情是花费时间将所有东西都在寻路调用之后,特别是如果你有一个大的地图。

我通过创建一个名为whichList(x,y)的2d数组来指定我的地图上的每个节点作为开放列表或关闭列表,从而避免这种开销。寻路尝试后,我不归零这个数组。相反,我重置onClosedList和onOpenList在每个pathfinding调用的值,增加+5或类似的每个路径尝试尝试。这样,算法可以安全地忽略作为垃圾从先前的寻路尝试剩下的任何数据。我还存储值,如F,G和H成本在数组。在这种情况下,我简单地写任何预先存在的值,并不打扰清除数组,当我完成。

然而,将数据存储在多个阵列中消耗更多的存储器,因此存在折衷。最终,你应该使用任何你最舒适的方法。

  1. Dijkstra算法:虽然A *通常被认为是最好的寻路算法(见上面的rant),但至少有一个其他算法有它的用途–Dijkstra的算法。Dijkstra的本质上与A *相同,除了没有启发式(H总是0)。因为它没有启发式,它通过在每个方向上平均扩展来搜索。正如你可能想象的,因为这个Dijkstra通常最终在目标被找到之前探索一个更大的区域。这通常使它比A *慢。

那么为什么要用呢?有时我们不知道我们的目标目的地在哪里。假设你有一个资源收集单位,需要得到某种资源。它可能知道几个资源区域在哪里,但它想要去最近的一个。这里,Dijkstra比A *好,因为我们不知道哪个最接近。我们唯一的选择是重复使用A *来找到到每个的距离,然后选择该路径。可能有无数类似的情况,我们知道我们可能寻找的位置,想找到最近的一个,但不知道它在哪里或哪个可能是最接近的。