A*寻路算法入门(二)

时间:2023-03-08 15:54:48

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处.

如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;)


免责申明:本博客提供的所有翻译文章原稿均来自互联网,仅供学习交流之用,请勿进行商业用途。同时,转载时不要移除本申明。如产生任何纠纷,均与本博客所有人、发表该翻译稿之人无任何关系。谢谢合作!

一只寻路的猫咪(本猫猪也是路痴,猫猪注.)

让我们想象我们有一个游戏,游戏中一只猫咪想要找到得到骨头的路径.

“为毛一只在世界上的猫咪想要一根骨头呢?!”你可能会这样想.好吧,在我们的游戏中,这是一只狡猾的猫咪,它想将骨头交给狗狗们,所以狗狗们不会咬它啦! :]

所以想象下图中的猫咪想要找到到达骨头的最短路径:

A*寻路算法入门(二)

不幸的是,这只猫咪不能直接从当前位置到达骨头,因为途中有坚固的墙壁,因为它在游戏中不是幽灵猫咪!

而且这只猫咪非常的懒,它总是像找到最短的路径,以便还有劲回家去找它的母猫缠绵 ;-)

但是我们如何写一个算法来使猫咪得偿所愿呢?救世主A*算法来啦!

简化搜索区域

在寻路中的第一步是使得整个搜索区域简化的可被简单操作.

这将取决于具体的游戏.举个栗子,我们可以按像素来划分搜索区域,但是它对于我们基于瓦块地图的游戏来说的粒度太高(而且毫无必要).

作为替代,我们将使用瓦块(一个正方形)作为寻路算法的基本单元.用其他形状也是可以的(比如三角形或者六边形),但是正方形在这里对于我们的需求来说最适合并且也最简单.