A星算法JavaScript实现

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属性，则能找到路线

最后附上案例 http://ancong_admin.gitee.io/a_star_algorithm