欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

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

程序员文章站 2022-06-22 16:34:45
本文实例讲述了js/html5游戏常用算法之路径搜索算法 a*寻路算法。分享给大家供大家参考，具体如下： 原理可参考： 完整实例代码如下：

本文实例讲述了js/html5游戏常用算法之路径搜索算法 a*寻路算法。分享给大家供大家参考，具体如下：

原理可参考：

完整实例代码如下：

<!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程序设计有所帮助。

上一篇： JavaScript实现的鼠标跟随特效示例【2则实例】

下一篇： 移动端如何用下拉刷新的方式实现上拉加载

推荐阅读