JS实现的A*寻路算法详解
25 浏览量
2020-12-12
13:50:44
上传
评论 1
收藏 222KB PDF 举报
JS实现的实现的A*寻路算法详解寻路算法详解
本文实例讲述了JS实现的A*寻路算法。分享给大家供大家参考，具体如下：
这两天在做百度前端技术学院的题目，其中有涉及到寻路相关的，于是就找来相关博客进行阅读。
看了Create Chen写的理解A*寻路算法具体过程之后，我很快就理解A*算法的原理。不得不说作者写的很好，通熟易懂，图片
也做的很好，可见作者在这上面是花了心思的。如果让我写，我是写不来这么好的。
唯一的不足就是，因为我学的是js，因此最后给我的源码我是用不了的……因此才有自己写一篇的打算，方面学习js人的学
习。然而前面的描述我就借用他的了，因为如果然我的表达能力实在是太渣了。
简易地图简易地图
如图所示简易地图, 其中绿色方块的是起点 (用 A 表示), 中间蓝色的是障碍物, 红色的方块 (用 B 表示) 是目的地. 为了可以用一
个二维数组来表示地图, 我们将地图划分成一个个的小方块.
二维数组在游戏中的应用是很多的, 比如贪吃蛇和俄罗斯方块基本原理就是移动方块而已. 而大型游戏的地图, 则是将各种”地
貌”铺在这样的小方块上.
寻路步骤寻路步骤
1. 从起点A开始, 把它作为待处理的方格存入一个”开启列表”, 开启列表就是一个等待检查方格的列表.
2. 寻找起点A周围可以到达的方格, 将它们放入”开启列表”, 并设置它们的”父方格”为A.
3. 从”开启列表”中删除起点 A, 并将起点 A 加入”关闭列表”, “关闭列表”中存放的都是不需要再次检查的方格
图中浅绿色描边的方块表示已经加入 “开启列表” 等待检查. 淡蓝色描边的起点 A 表示已经放入 “关闭列表” , 它不需要再执行检
查.
从 “开启列表” 中找出相对最靠谱的方块, 什么是最靠谱? 它们通过公式 F=G+H 来计算.
F = G + H
G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).
H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以上下左右移动).
评论0