大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处.
如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;)
免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途。同时,转载时不要移除本申明。如产生任何纠纷,均与本博客所有人、发表该翻译稿之人无任何关系。谢谢合作!
现在你该知道如何计算每一个方块的分值了(我们将称之为F,它等于G+H),让我们看看A*算法是如何工作的.
这只猫咪将用以下重复的步骤来找到最短路径:
如果你有点混乱也不用担心 — 我们将用一个例子一步步的像你展示它是如何工作的! :]
让我们通过一个例子看看这只懒猫咪是如何找到骨头的.
在下面的图示中,我已经将对应的值列出来了(F = G + H):
同样,箭头显示出到达该方块的移动方向(指向其父方块.猫猪注).
最终,对于每一步来说,红色方块指示闭合列表,绿色方块指示开发列表.
OK,让我们开始吧!
在第一步中,这只猫咪确定其起始位置(点A)的可到的达邻居方块,计算他们的F分值,然后将它们添加到开放列表中:
你可以看到每一个方块中列出了H值(2个为6,一个为4).我建议根据”街区距离”算法自己计算一下,确保你理解这部分是如何工作的.
同样要注意的是F值(左上角)正好是G+H的和(左下角和右下角).
接下来,猫咪选择最小分值的方块,将其添加到闭合列表中去,并且获得他的邻居方块.
所以你将看到最小分值方块的F值为4,我们试图将所有它的邻居瓦块添加到开发列表中(并且计算它们的分值),除非它不能被添加(因为它已经在闭合列表中了)或者它是不可到达的(比如墙壁).
注意这里有2个新的瓦块被添加到开放列表中,G值被加1,因为从起始位置到它们有2个瓦块的距离.你可能想去用”街区距离”算法计算一下以确保你懂了了这些新添加瓦块的H值是如何计算的.
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。