A 星算法
介绍
javascript 实现 A 星寻路算法
在游戏中常有需要主角 / 敌人去移动到某个物品或者追寻敌人的时候，这个时候，可以使用寻路算法
为了实现 canvas 游戏，需要寻路算法，于是便自己用 JS 实现了一下
原理思路
简化搜索区域：
为了减少资源消耗，首先需要我们将地图分割为区块，如下图
2. 建立起点和终点坐标，用于寻路
维护 open 和 close 列表
我们新建两个列表，一个 open 表，它记录了所有被考虑的寻路点；一个 close 表，它记录了所有不再被考虑的点
我们要做的是接下来对两个表的维护
搜索路径
如何寻路呢，首先我们引入 3 个量
G 值，也就是当前点到起始点所需的代价
H 值，不考虑所有障碍等要素，该点到终点非斜线方式的估算量，也就是 x + y 的值
F 值，也就是该点的 G + H 的值
如图所示，左上角为 F，右上角为 H，左下为 G：
接下来是寻路具体实现
首先最小 F 值的点加入 open，点暂记为 curr 点
将 curr 点移除 open，加入 close
对于 curr 相邻点，都有以下步骤
在 close 或者是障碍，不管它
不在 open 中，则计算它的各项值，加入 open
在 open 中，则计算我们当前这条路径到达这个点是否有更小 F 值，是则更新它的 F 值
检测到当前路径点和终点一致时候则结束寻路；如果 open 中为空，则代表没有合适的寻路方案，寻路失败
JS 实现的具体方案
首先建立一个 Sopt 的类，它里面包含以下信息
属性：x,y,f,g,h,isWall,neighbors,parents，
方法 addNeighbors, 用于添加周围 8 个格子可以添加的点
初始化地图所有点，运行 addNeighbors 方法，将 neighbors 数组初始化
建立寻路流程
初始化地点、终点，将起点加入 openlist
建立一个递归函数用于寻找路径
寻路递归函数
首先判断 openlist 是否长度为 0，是则寻路失败
建立一个 curr 代表当前点初始为 null，和 currIndex 序列号初始为 0
let currIndex = 0;
let curr = null;
for(let i = 0; i < openList.length; i++) {
if(openList[i].f < openList[currIndex].f) {
currIndex = i;
}
}
curr = openList[currIndex];
if(curr === endSopt) {
drawPath(curr);
return true;
}
removeFromArray(openList, curr);
closedList.push(curr);
3. 遍历 curr 的 neighbors，将合适点的 parent 设为 curr
for(let i = 0; i < curr.neighbors.length; i++) {
let neighbor = curr.neighbors[i];
if(!closedList.includes(neighbor) && !neighbor.wall) {
let tmpF = curr.g + getG(curr, neighbor) + getH(neighbor);
let newPath = false; // 是否是更好的路线
if(openList.includes(neighbor)) {
if(tmpF <= neighbor.f) {
neighbor.f = tmpF;
newPath = true;
}
} else {
neighbor.g = curr.g + getG(curr, neighbor);
neighbor.h = getH(neighbor);
neighbor.f = neighbor.g + neighbor.h;
newPath = true;
openList.push(neighbor);
}
if(newPath) {
neighbor.parent = curr;
}
}
}
4. 递归这个函数，当点和终点一致时，返回这个点，然后递归它的 parent 属性，则能找到路线
最后附上案例地址：a 星算法