A星算法

介绍

javascript实现A星寻路算法

1. 在游戏中常有需要主角/敌人去移动到某个物品或者追寻敌人的时候，这个时候，可以使用寻路算法
2. 为了实现canvas游戏，需要寻路算法，于是便自己用JS实现了一下

原理思路

简化搜索区域：

1. 为了减少资源消耗，首先需要我们将地图分割为区块，如下图

   

   2.建立起点和终点坐标，用于寻路

维护open和close列表

1. 我们新建两个列表，一个open表，它记录了所有被考虑的寻路点；一个close表，它记录了所有不再被考虑的点
2. 我们要做的是接下来对两个表的维护

搜索路径

1. 如何寻路呢，首先我们引入3个量

   1. G值，也就是当前点到起始点所需的代价
   2. H值，不考虑所有障碍等要素，该点到终点非斜线方式的估算量，也就是x+y的值
   3. F值，也就是该点的G+H的值
   4. 如图所示，左上角为F，右上角为H，左下为G：
      

2. 接下来是寻路具体实现

   1. 首先最小F值的点加入open，点暂记为curr点
   2. 将curr点移除open，加入close

   3. 对于curr相邻点，都有以下步骤

      1. 在close或者是障碍，不管它
      2. 不在open中，则计算它的各项值，加入open
      3. 在open中，则计算我们当前这条路径到达这个点是否有更小F值，是则更新它的F值
   4. 检测到当前路径点和终点一致时候则结束寻路；如果open中为空，则代表没有合适的寻路方案，寻路失败

3. JS实现的具体方案

   1. 首先建立一个Sopt的类，它里面包含以下信息

      1. 属性：x,y,f,g,h,isWall,neighbors,parents，
      2. 方法addNeighbors,用于添加周围8个格子可以添加的点
   2. 初始化地图所有点，运行addNeighbors方法，将neighbors数组初始化

   3. 建立寻路流程

      1. 初始化地点、终点，将起点加入openlist
      2. 建立一个递归函数用于寻找路径

   4. 寻路递归函数

      1. 首先判断openlist是否长度为0，是则寻路失败

      2. 建立一个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星算法