A星算法原理【转】- 下篇

在A星算法的上一篇，我们已经大致明白了该算法的过程，现在让我们看看它具体是怎么运作的。我们最初的9格方格中，在起点被切换到关闭列表中后，还剩8格 留在开启列表中。这里面，F值最低的那个是起始格右侧紧邻的格子，它的F值是40。因此我们选择这一格作为下一个要处理的方格。在紧随的图中，它被用蓝色 突出显示。

 

 

  

[图4] 

 

 

 

首先，我们把它从开启列表中取出，放入关闭列表(这就是他被蓝色突出显示的原因)。然后我们检查相邻的格子。哦，右侧的格子是墙，所以我们略过。左侧的格子是起始格。它在关闭列表里，所以我们也跳过它。 

 

其他4格已经在开启列表里了，于是我们检查G值来判定，如果通过这一格到达那里，路径是否更好。我们来看选中格子下面的方格。它的G值是14。如果我们从 当前格移动到那里，G值就会等于20(到达当前格的G值是10，移动到上面的格子将使得G值增加10)。因为G值20大于14，所以这不是更好的路径。如 果你看图，就能理解。与其通过先水平移动一格，再垂直移动一格，还不如直接沿对角线方向移动一格来得简单。

 

当我们对已经存在于开启列表中的4个临近格重复这一过程的时候，我们发现没有一条路径可以通过使用当前格子得到改善，所以我们不做任何改变。既然我们已经检查过了所有邻近格，那么就可以移动到下一格了。

 

 

 

于是我们检索开启列表，现在里面只有7格了，我们仍然选择其中F值最低的。有趣的是，这次，有两个格子的数值都是54。我们如何选择？这并不麻烦。从速度上考虑，选择最后添加进列表的格子会更快捷。

 

这种导致了寻路过程中，在靠近目标的时候，优先使用新找到的格子的偏好。但这无关紧要。（对相同数值的不同对待，导致不同版本的A*算法找到等长的不同路径。）

 

那我们就选择起始格右下方的格子，如图。

 

 

     [图5] 

 

 

 

这次，当我们检查相邻格的时候，发现右侧是墙，于是略过。上面一格也被略过。我们也略过了墙下面的格子。为什么呢？因为你不能在不穿越墙角的情况下直接到 达那个格子。你的确需要先往下走然后到达那一格，按部就班的走过那个拐角。(注解：穿越拐角的规则是可选的。它取决于你的节点是如何放置的。) 这样一来，就剩下了其他5格。当前格下面的另外两个格子目前不在开启列表中，于是我们添加他们，并且把当前格指定为他们的父节点。其余3格，两个已经在关 闭列表中（起始格，和当前格上方的格子，在表格中蓝色高亮显示),于是我们略过它们。最后一格，在当前格的左侧，将被检查通过这条路径，G值是否更低。不 必担心，我们已经准备好检查开启列表中的下一格了。
    我们重复这个过程，直到目标格被添加进关闭列表，就如在下面的图中所看到的。 

 

 

 

[图6] 

 

注意，起始格下方格子的父节点已经和前面不同的。之前它的G值是28，并且指向右上方的格子。现在它的G值是20，指向它上方的格子。这在寻路过程中的某 处发生，当应用新路径时，G值经过检查变得低了－于是父节点被重新指定，G和F值被重新计算。尽管这一变化在这个例子中并不重要，在很多场合，这种变化会 导致寻路结果的巨大变化。 

 

那么，我们怎么确定这条路径呢？很简单，从红色的目标格开始，按箭头的方向朝父节点移动。这最终会引导你回到起始格，这就是你的路径！看起来应该像图中那样。从起始格A移动到目标格B只是简单的从每个格子（节点）的中点沿路径移动到下一个，直到你到达目标点。就这么简单。  

 

 

 

[图7] 

 

 

A*方法总结 

 

好，现在你已经看完了整个说明，让我们把每一步的操作写在一起：   

 

1，把起始格添加到开启列表。    

 

2，重复如下的工作：       

 

  a) 寻找开启列表中F值最低的格子。我们称它为当前格。       

 

  b) 把它切换到关闭列表。       

 

  c) 对相邻的8格中的每一个？           

 

     * 如果它不可通过或者已经在关闭列表中，略过它。反之如下。           

 

     * 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。          * 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如            果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启            列表按F值排序，改变之后你可能需要重新对开启列表排序。

 

 d) 停止，当你           

 

     * 把目标格添加进了关闭列表，这时候路径被找到，或者           

 

     * 没有找到目标格，开启列表已经空了。这时候，路径不存在。    

 

3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。 

 

 

(注解:在这篇文章的较早版本中，建议的做法是当目标格（或节点）被加入到 开启列表，而不是关闭列表的时候停止寻路。这么做会更迅速，而且几乎总是能找到最短的路径，但不是绝对的。当从倒数第二个节点到最后一个（目标节点）之间 的移动耗费悬殊很大时－例如刚好有一条河穿越两个节点中间，这时候旧的做法和新的做法就会有显著不同。）