JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算

编程学习 2021-07-04 16:47www.dzhlxh.cn编程入门
这篇文章主要介绍了JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法,结合实例形式详细分析了针对迷宫游戏路径搜索算法的普里姆算法相关原理、实现方法及操作注意事项,需要的朋友可以参考下

本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法。分享给大家供大家参考,具体如下:

路径搜索算法在游戏中非常常见,特别是在 RPG、SLG 中经常用到。在这些游戏中,通过鼠标指定行走目的地,人物或者NPC就会自动行走到目标地点,这就是通过路径搜索或者称为寻路算法来实现的。通俗地说,就是在一张地图中,如何让主角自动行走到指定的地点,如图6-21所示,假设主角在A处,然后玩家在地图中点击B处,要求主角能够从A点自动找寻一条到 B 点的路径,然后自动移动到 B处,要求就这么简单。

在前面的碰撞检测算法中,我们提到,现在的游戏中的地图一般采用格子的方式,虽然表面地图上无法看到实际的格子,但在地图的结构中专门有一个逻辑层,这个层和地图大小等大,划分出很多小的格子,然后在可以通过的地方使用0表示,有障碍的且不能通过的地方使用 1 或其他数字表示。如下图所示,左边的游戏中的地图,程序中会以右边的一个二维数组保存一个逻辑层,专门用来设定障碍。有了这个逻辑层之后,实际上自动寻路就转化成了,如何在一个二维的数组中找到一条从逻辑值为 0 的地点移动到目标地点的路径。

在介绍如何使用自动寻路算法前,我们先来看另外一个游戏常用的算法,即随机产生地图(迷宫)算法,用于结合寻路算法。

【随机迷宫算法】

根据前面的地图的理论,本质上,地图的障碍逻辑层是由一个二维数组保存,障碍标记在二维数组中的数据值以0或1表示,我们需要做的就是随机产生这个二维的数组。当然,最简单的办法就是循环这个二维数组然后在每一个位置随机地产生 0 或者 1,但这种算法产生的图形比较难看,并且不一定保证图中的任意两点可以相连通。

(1)下图所示为一个6×6的迷宫,先假设迷宫中所有的通路都是完全封闭的,白色的格子表示可以通过,黑色的表示墙壁,表示无法通过。

(2)随机选择一个白色的格子作为当前正在访问的格子,同时,把该格子放进一个表示已经访问的列表。

(3)循环以下操作直到所有的格子都被访问。

  • 得到当前访问格子四周(上、下、左、右)的格子,在这些格子中随机选择一个没有在访问列表中的格子,如果找到,则把该格子和当前访问格子中间的墙"打通"置0,把该格子作为当前访问的格子,并放入访问列表。
  • 如果周围所有的格子都已访问过,则从已访问列表中随机选取一个作为当前访问的格子。

通过以上的迷宫生成算法,可以生成一个自然随机的迷宫。

狼蚁网站SEO优化的代码根据以上的算法将产生一个R行N列大小的迷宫,需要注意的是R行表示的是刚开始空白格子的行数,由于要算上墙壁的数据,最终产生二维数组实际上的的行数为2R+1,列数为2N+1:

<!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>01_随机迷宫算法</title>
  <style>
    #stage {
      border: 1px solid lightgray;
    }
    .rebuild{
      width:160px;
      height:40px;
      line-height: 40px;
      text-align: center;
      background-color:#000000;
      color:#fff;
      font-size: 24px;
      margin-bottom: 20px;
      cursor: pointer;
    }
  </style>
</head>
<body>
<div class="rebuild">点击更新</div>
<canvas id="stage"></canvas>
</body>
<script>
  window.onload = function () {
    var stage = document.querySelector('#stage'),
      ctx = stage.getContext('2d');
    stage.width = 600;
    stage.height = 600;
    //取区域随机数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();
    }
    function update() {
      ctx.clearRect(0, 0, 600, 600);
      drawGrid(ctx, 'lightgray', 40, 40);
      var mapArr = primMaze(7,7);
      console.log(mapArr);
      //根据地图二维数组创建色块
      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(i * 40, j * 40, 40, "black");
          }
        }
      }
    }
    update();
    document.querySelector('.rebuild').addEventListener('click', update);
  };
</script>
</html>

这里使用在线HTML/CSS/JavaScript代码运行工具: 测试上述代码运行效果如下:

github地址:

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《》、《》、《》、《》、《》、《》及《》

希望本文所述对大家JavaScript程序设计有所帮助。

Copyright © 2016-2025 www.dzhlxh.cn 金源码 版权所有 Power by

网站模板下载|网络推广|微博营销|seo优化|视频营销|网络营销|微信营销|网站建设|织梦模板|小程序模板