游戏A星寻路算法教程详解 a星寻路算法路径优化【新手必看】(2)

游戏A星寻路算法教程详解

好，现在让我们看看其中的一些方格。在标有字母的方格，G = 10。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方，下方，左方的方格的G值都是10，对角线的方格G值都是14。

H值通过估算起点于终点(红色方格)的Manhattan距离得到，仅作横向和纵向移动，并且忽略沿途的墙壁。使用这种方式，起点右边的方格到终点有3个方格的距离，因此H = 30。这个方格上方的方格到终点有4个方格的距离(注意只计算横向和纵向距离)，因此H = 40。对于其他的方格，你可以用同样的方法知道H值是如何得来的。

每个方格的F值，再说一次，直接把G值和H值相加就可以了。

继续搜索(Continuing the Search)

为了继续搜索，我们从open list中选择F值最小的(方格)节点，然后对所选择的方格作如下操作：

4、把它从open list里取出，放到close list中。

5、检查所有与它相邻的方格，忽略其中在close list中或是不可走(unwalkable)的方格(比如墙，水，或是其他非法地形)，如果方格不在open lsit中，则把它们加入到open list中。

把我们选定的方格设置为这些新加入的方格的父亲。

6、如果某个相邻的方格已经在open list中，则检查这条路径是否更优，也就是说经由当前方格(我们选中的方格)到达那个方格是否具有更小的G值。如果没有，不做任何操作。

相反，如果G值更小，则把那个方格的父亲设为当前方格(我们选中的方格)，然后重新计算那个方格的F值和G值。如果你还是很混淆，请参考下图所示。

让我们看看它是怎么工作的。在我们最初的9个方格中，还有8个在open list中，起点被放入了close list中。在这些方格中，起点右边的格子的F值40最小，因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。

首先，我们把它从open list移到close list中(这就是为什么用蓝线打亮的原因了)。然后我们检查与它相邻的方格。它右边的方格是墙壁，我们忽略。它左边的方格是起点，在close list中，我们也忽略。其他4个相邻的方格均在open list中，我们需要检查经由这个方格到达那里的路径是否更好，使用G值来判定。让我们看看上面的方格。它现在的G值为14。如果我们经由当前方格到达那里，G值将会为20(其中10为到达当前方格的G值，此外还要加上从当前方格纵向移动到上面方格的G值10)。显然20比14大，因此这不是最优的路径。如果你看图你就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

当把4个已经在open list中的相邻方格都检查后，没有发现经由当前方格的更好路径，因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格，并也对他们作了处理，是时候选择下一个待处理的方格了。

因此再次遍历我们的open list，现在它只有7个方格了，我们需要选择F值最小的那个。有趣的是，这次有两个方格的F值都54，选哪个呢？没什么关系。从速度上考虑，选择最后加入open list的方格更快。这导致了在寻路过程中，当靠近目标时，优先使用新找到的方格的偏好。但是这并不重要。(对相同数据的不同对待，导致两中版本的A*找到等长的不同路径)。

我们选择起点右下方的方格，如下图所示：

这次，当我们检查相邻的方格时，我们发现它右边的方格是墙，忽略掉。上面的也一样。

我们把墙下面的一格也忽略掉。为什么？因为如果不穿越墙角的话，你不能直接从当前方格移动到那个方格。你需要先往下走，然后再移动到那个方格，这样来绕过墙角。(注意：穿越墙角的规则是可选的，依赖于你的节点是怎么放置的)

这样还剩下5个相邻的方格。当前方格下面的2个方格还没有加入open list，所以把它们加入，同时把当前方格设为他们的父亲。在剩下的3个方格中，有2个已经在close list中(一个是起点，一个是当前方格上面的方格，外框被加亮的)，我们忽略它们。最后一个方格，也就是当前方格左边的方格，我们检查经由当前方格到达那里是否具有更小的G值。没有。因此我们准备从open list中选择下一个待处理的方格。

不断重复这个过程，直到把终点也加入到了open list中，此时如下图所示。