大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处.
如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;)
免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途。同时,转载时不要移除本申明。如产生任何纠纷,均与本博客所有人、发表该翻译稿之人无任何关系。谢谢合作!
步骤3
我们再一次选择最小F值(5)的瓦块去继续迭代:
这时,只有一个可能的瓦块被添加到开放列表中,因为一个瓦块已经存在于闭合列表,两个瓦块是墙壁.
步骤4
现在我们遇到了一个有趣的情况.正如你在前一张图中看到的,这里有4个方块,它们的F值都是相同的7 — 我们该怎么办呢?!
这里有很多种解决方案可以使用,但是一个简单(也是快速的)的方法是保持跟随最近被添加到开放列表中的瓦块.所以我们从最近的瓦块继续:
这次有2快瓦块是邻接且可到达的,我们像往常那样计算它们的分值.
步骤5
我们再一次面临选择最小分值的(7)瓦块,同样选择最近添加的瓦块:
只有1个可能的瓦块被添加.我们离终点越来越近了!
步骤6
你现在已经有经验了!我打赌你可以像下图那样猜出接下里的步骤:
我们几乎完成了,但是这次你可以看到,这里实际我们可以从2条到骨头的最短路径中选择:
在我们的例子中有2条不同的最短路径:
- 1-2-3-4-5-6
- 1-2-3-4-5-7
我们选择哪条无所谓,由后面实际的实现代码来决定.
步骤7
让我们再一次枚举一遍这些方块:
Aha,骨头现在在开放列表中了!
步骤8
此时目的方块在开放列表中,算法将其添加到闭合列表中去:
然后算法要做的只是回退去计算出最终的路径!