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
letcurrIndex=0;
letcurr=null;
for(leti=0;i<openList.length;i++) {
if(openList[i].f<openList[currIndex].f) {
currIndex=i;
}
}
curr=openList[currIndex];
if(curr===endSopt) {
drawPath(curr);
returntrue;
}
removeFromArray(openList,curr);
closedList.push(curr);
3.遍历curr的neighbors，将合适点的parent设为curr
for(leti=0;i<curr.neighbors.length;i++) {
letneighbor=curr.neighbors[i];
if(!closedList.includes(neighbor)&&!neighbor.wall) {
lettmpF=curr.g+getG(curr,neighbor)+getH(neighbor);
letnewPath=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属性，则能找到路线
网友评论