JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例

发布时间：2020-10-09 18:14:41 作者：krapnik
来源：脚本之家阅读：239
本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法。分享给大家供大家参考，具体如下：
原理可参考：https://www.jb51.net/article/152744.htm
完整实例代码如下：
<!DOCTYPE html>
<html lang="en">
<head>
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
  <meta charset="UTF-8">
  <title>A*寻路算法</title>
  <style>
    #stage {
      border: 1px solid lightgray;
    }
  </style>
</head>
<body>
<canvas id="stage"></canvas>
</body>
<script>
  window.onload = function () {
    var stage = document.querySelector('#stage'),
      ctx = stage.getContext('2d');
    stage.width = 600;
    stage.height = 600;
    var row = 7, column = 7, r = 40;
    //取区域随机数x>=min && x<max
    function randInt(min, max) {
      max = max || 0;
      min = min || 0;
      var step = Math.abs(max - min);
      var st = (arguments.length < 2) ? 0 : min;//参数只有一个的时候，st = 0;
      var result;
      result = st + (Math.ceil(Math.random() * step)) - 1;
      return result;
    }
    //普里姆算法生成连通图的二维数组 row 行 column 列
    function primMaze(r, c) {
      //初始化数组
      function init(r, c) {
        var a = new Array(2 * r + 1);
        //全部置1
        for (let i = 0, len = a.length; i < len; i++) {
          var cols = 2 * c + 1;
          a[i] = new Array(cols);
          for (let j = 0, len1 = a[i].length; j < len1; j++) {
            a[i][j] = 1;
          }
        }
        //中间格子为0
        for (let i = 0; i < r; i++)
          for (let j = 0; j < c; j++) {
            a[2 * i + 1][2 * j + 1] = 0;
          }
        return a;
      }
      //处理数组，产生最终的数组
      function process(arr) {
        //acc存放已访问队列，noacc存放没有访问队列
        var acc = [], noacc = [];
        var r = arr.length >> 1, c = arr[0].length >> 1;
        var count = r * c;
        for (var i = 0; i < count; i++) {
          noacc[i] = 0;
        }
        //定义空单元上下左右偏移
        var offs = [-c, c, -1, 1], offR = [-1, 1, 0, 0], offC = [0, 0, -1, 1];
        //随机从noacc取出一个位置
        var pos = randInt(count);
        noacc[pos] = 1;
        acc.push(pos);
        while (acc.length < count) {
          var ls = -1, offPos = -1;
          offPos = -1;
          //找出pos位置在二维数组中的坐标
          var pr = pos / c | 0, pc = pos % c, co = 0, o = 0;
          //随机取上下左右四个单元
          while (++co < 5) {
            o = randInt(0, 5);
            ls = offs[o] + pos;
            var tpr = pr + offR[o];
            var tpc = pc + offC[o];
            if (tpr >= 0 && tpc >= 0 && tpr <= r - 1 && tpc <= c - 1 && noacc[ls] == 0) {
              offPos = o;
              break;
            }
          }
          if (offPos < 0) {
            pos = acc[randInt(acc.length)];
          }
          else {
            pr = 2 * pr + 1;
            pc = 2 * pc + 1;
            //相邻空单元中间的位置置0
            arr[pr + offR[offPos]][pc + offC[offPos]] = 0;
            pos = ls;
            noacc[pos] = 1;
            acc.push(pos);
          }
        }
      }
      var a = init(r, c);
      process(a);
      return a;
      //返回一个二维数组，行的数据为2r+1个,列的数据为2c+1个
    }
    //栅格线条
    function drawGrid(context, color, stepx, stepy) {
      context.strokeStyle = color;
      context.lineWidth = 0.5;
      for (var i = stepx + 0.5; i < context.canvas.width; i += stepx) {
        context.beginPath();
        context.moveTo(i, 0);
        context.lineTo(i, context.canvas.height);
        context.stroke();
      }
      for (var i = stepy + 0.5; i < context.canvas.height; i += stepy) {
        context.beginPath();
        context.moveTo(0, i);
        context.lineTo(context.canvas.width, i);
        context.stroke();
      }
    }
    //方块创造方法
    function createRect(x, y, r, c) {
      ctx.beginPath();
      ctx.fillStyle = c;
      ctx.rect(x, y, r, r);
      ctx.fill();
    }
    //定义点对象【a*点对象】
    function Point(x, y) {
      this.x = x;
      this.y = y;
      this.parent = null;
      this.f = 0;
      this.g = 0;
      this.h = 0;
      //当前点状态，0：表示在openlist 1:表示closelist,-1表示还没处理
      this.state = -1;
      //flag表明该点是否可通过
      this.flag = 0;
    }
    //把普通二维数组(全部由1，0表示)的转换成a*所需要的点数组
    function convertArrToAS(arr) {
      var r = arr.length, c = arr[0].length;
      var a = new Array(r);
      for (var i = 0; i < r; i++) {
        a[i] = new Array(c);
        for (var j = 0; j < c; j++) {
          var pos = new Point(i, j);
          pos.flag = arr[i][j];
          a[i][j] = pos;
        }
      }
      return a;
    }
    //A*算法,pathArr表示最后返回的路径
    function findPathA(pathArr, start, end, row, col) {
      //添加数据到排序数组中
      function addArrSort(descSortedArr, element, compare) {
        var left = 0;
        var right = descSortedArr.length - 1;
        var mid = (left + right) >> 1;
        while (left <= right) {
          var mid = (left + right) >> 1;
          if (compare(descSortedArr[mid], element) == 1) {
            left = mid + 1;
          }
          else if (compare(descSortedArr[mid], element) == -1) {
            right = mid - 1;
          }
          else {
            break;
          }
        }
        for (var i = descSortedArr.length - 1; i >= left; i--) {
          descSortedArr[i + 1] = descSortedArr[i];
        }
        descSortedArr[left] = element;
      }
      //判断两个点是否相同
      function pEqual(p1, p2) {
        return p1.x == p2.x && p1.y == p2.y;
      }
      //获取两个点距离，采用曼哈顿方法
      function posDist(pos, pos1) {
        return (Math.abs(pos1.x - pos.x) + Math.abs(pos1.y - pos.y));
      }
      function between(val, min, max) {
        return (val >= min && val <= max)
      }
      //比较两个点f值大小
      function compPointF(pt1, pt2) {
        return pt1.f - pt2.f;
      }
      //处理当前节点
      function processCurrpoint(arr, openList, row, col, currPoint, destPoint) {
        //get up,down,left,right direct
        var ltx = currPoint.x - 1;
        var lty = currPoint.y - 1;
        for (var i = 0; i < 3; i++){
          for (var j = 0; j < 3; j++) {
            var cx = ltx + i;
            var cy = lty + j;
            if ((cx === currPoint.x || cy === currPoint.y) && between(ltx, 0, row - 1) && between(lty, 0, col - 1)) {
              var tp = arr[cx][cy];
              if (tp.flag === 0 && tp.state !== 1) {
                if (pEqual(tp, destPoint)) {
                  tp.parent = currPoint;
                  return true;
                }
                if (tp.state === -1) {
                  tp.parent = currPoint;
                  tp.g = 1 + currPoint.g;
                  tp.h = posDist(tp, destPoint);
                  tp.f = tp.h + tp.f;
                  tp.state = 0;
                  addArrSort(openList, tp, compPointF);
                }
                else {
                  var g = 1 + currPoint.g;
                  if (g < tp.g) {
                    tp.parent = currPoint;
                    tp.g = g;
                    tp.f = tp.g + tp.h;
                    openList.quickSort(compPointF);
                  }
                }
              }
            }
          }
        }
        return false;
      }
      //定义openList
      var openList = [];
      //定义closeList
      var closeList = [];
      start = pathArr[start[0]][start[1]];
      end = pathArr[end[0]][end[1]];
      //添加开始节点到openList;
      addArrSort(openList, start, compPointF);
      var finded = false;
      while ((openList.length > 0)) {
        var currPoint = openList.pop();
        currPoint.state = 1;
        closeList.push(currPoint);
        finded = processCurrpoint(pathArr, openList, row, col, currPoint, end);
        if (finded) {
          break;
        }
      }
      if (finded) {
        var farr = [];
        var tp = end.parent;
        farr.push(end);
        while (tp != null) {
          farr.push(tp);
          tp = tp.parent;
        }
        return farr;
      }
      else {
        return null;
      }
    }
    //定位屏幕坐标到数组位置
    function mapSCPos(i, j) {
      return [i / r | 0, j / r | 0];
    }
    //检测数组中的位置是否存在方块
    function mapHasRect(map, i, j) {
      return (map[i][j]);
    }
    var mapArr = primMaze(row, column);
    var startRect = {
      x: function () {
        for (var i = 0, len = mapArr.length; i < len; i++) {
          for (var j = 0, len1 = mapArr[i].length; j < len1; j++) {
            if (!mapArr[i][j]) {
              return j * r;
              break;
            }
          }
        }
      }(),
      y: function () {
        for (var i = 0, len = mapArr.length; i < len; i++) {
          for (var j = 0, len1 = mapArr[i].length; j < len1; j++) {
            if (!mapArr[i][j]) {
              return i * r;
              break;
            }
          }
        }
      }(),
      pos: function () {
        return [this.x, this.y];
      }
    },
      endRect = {
      hasCreate:false,
      x:null,
      y:null,
      pos: function () {
        return [this.x, this.y];
      }
    },
      startPoint = mapSCPos(startRect.pos()[1], startRect.pos()[0]),
      endPoint,
      path = null,
      next = null;
    //计算路经
    function update() {
      ctx.clearRect(0, 0, 600, 600);
      drawGrid(ctx, 'lightgray', r, r);
      //根据地图二维数组创建色块
      for (var i = 0, len = mapArr.length; i < len; i++) {
        for (var j = 0, len1 = mapArr[i].length; j < len1; j++) {
          if (mapArr[i][j]) {
            createRect(j * r, i * r, r, "black");
          }
        }
      }
      //绘制开始方块
      createRect(startRect.x, startRect.y, r, "red");
      if (endRect.hasCreate) {
        //绘制跟随方块
        createRect(endRect.pos()[0], endRect.pos()[1], r, "blue");
        endPoint = mapSCPos(endRect.pos()[1], endRect.pos()[0]);
        if(path === null){
          var ASmap = convertArrToAS(mapArr);
          path = findPathA(ASmap, startPoint, endPoint, ASmap.length, ASmap.length);
        }else{
          next = path.pop();
          startRect.y = next.x * r;
          startRect.x = next.y * r;
          if(path.length===0){
            startPoint = mapSCPos(startRect.pos()[1], startRect.pos()[0]);
            path = null;
            endRect.hasCreate = false;
          }
        }
      }
      requestAnimationFrame(update);
    }
    update();
    stage.addEventListener('click', function () {
      //标准的获取鼠标点击相对于canvas画布的坐标公式
      var x = event.clientX - stage.getBoundingClientRect().left,
        y = event.clientY - stage.getBoundingClientRect().top;
      var endRectPos = mapSCPos(y, x);//[i,j]
      endRect.x = endRectPos[1]*r;
      endRect.y = endRectPos[0]*r;
      if (mapHasRect(mapArr, endRectPos[0], endRectPos[1])) {
        console.log('这个位置已经有方块啦！');
      } else {
        endRect.pos();
        endRect.hasCreate = true;
      }
    })
  };
</script>
</html>
使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun，测试运行上述代码，可得到如下运行效果：
JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例

相关阅读
