A*, A Star A星算法详解( 三 ) _a星算法

[图3]
现在我们来看看这些方格。写字母的方格里， G = 10 。这是因为它只在水平方向偏离起始格一个格距。紧邻起始格的上方，下方和左边的方格的G值都等于10 。对角线方向的G值是14 。
H值通过求解到红色目标格的曼哈顿距离得到，其中只在水平和垂直方向移动，并且忽略中间的墙。用这种方法，起点右侧紧邻的方格离红色方格有3格距离， H值就是30 。这块方格上方的方格有4格距离(记住，只能在水平和垂直方向移动) ， H值是40 。你大致应该知道如何计算其他方格的H值了～。
每个格子的F值，还是简单的由G和H相加得到
继续搜索
为了继续搜索，我们简单的从开启列表中选择F值最低的方格。然后，对选中的方格做如下处理：
4 ，把它从开启列表中删除，然后添加到关闭列表中。

文章插图
5 ，检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙，水的地形，或者其他无法通过的地形) ，把他们添加进开启列表，如果他们还不在里面的话。把选中的方格作为新的方格的父节点。
6 ，如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。换句话说，检查如果我们用新的路径到达它的话， G值是否会更低一些。如果不是，那就什么都不做。
另一方面，如果新的G值更低，那就把相邻方格的父节点改为目前选中的方格（在上面的图表中，把箭头的方向改为指向这个方格）。最后，重新计算F和G的值。如果这看起来不够清晰，你可以看下面的图示。
好了，让我们看看它是怎么运作的。我们最初的9格方格中，在起点被切换到关闭列表中后，还剩8格留在开启列表中。这里面， F值最低的那个是起始格右侧紧邻的格子，它的F值是40 。因此我们选择这一格作为下一个要处理的方格。在紧随的图中，它被用蓝色突出显示。
[图4]
首先，我们把它从开启列表中取出，放入关闭列表(这就是他被蓝色突出显示的原因) 。然后我们检查相邻的格子。哦，右侧的格子是墙，所以我们略过。左侧的格子是起始格。它在关闭列表里，所以我们也跳过它。
其他4格已经在开启列表里了，于是我们检查G值来判定，如果通过这一格到达那里，路径是否更好。我们来看选中格子下面的方格。它的G值是14 。如果我们从当前格移动到那里， G值就会等于20(到达当前格的G值是10 ，移动到上面的格子将使得G值增加10) 。因为G值20大于14 ，所以这不是更好的路径。如果你看图，就能理解。与其通过先水平移动一格，再垂直移动一格，还不如直接沿对角线方向移动一格来得简单。
当我们对已经存在于开启列表中的4个临近格重复这一过程的时候，我们发现没有一条路径可以通过使用当前格子得到改善，所以我们不做任何改变。既然我们已经检查过了所有邻近格，那么就可以移动到下一格了。
于是我们检索开启列表，现在里面只有7格了，我们仍然选择其中F值最低的。有趣的是，这次，有两个格子的数值都是54 。我们如何选择？这并不麻烦。从速度上考虑，选择最后添加进列表的格子会更快捷。这种导致了寻路过程中，在靠近目标的时候，优先使用新找到的格子的偏好。但这无关紧要。（对相同数值的不同对待，导致不同版本的A*算法找到等长的不同路径。）