JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法详解【普里姆算法】
导读：本文共4762字符，通常情况下阅读需要16分钟。同时您也可以点击右侧朗读，来听本文内容。按键盘←（左） →（右） 方向键可以翻页。
摘要： 本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法。分享给大家供大家参考，具体如下：路径搜索算法在游戏中非常常见，特别是在 RPG、SLG 中经常用到。在这些游戏中，通过鼠标指定行走目的地，人物或者NPC就会自动行走到目标地点，这就是通过路径搜索或者称为寻路算法来实现的。通俗地说，就是在一张地图中，如何让主角自动行走到指定的地点，如图6-2... ...
目录
(为您整理了一些要点),点击可以直达。本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法。分享给大家供大家参考，具体如下：
路径搜索算法在游戏中非常常见，特别是在 RPG、SLG 中经常用到。在这些游戏中，通过鼠标指定行走目的地，人物或者NPC就会自动行走到目标地点，这就是通过路径搜索或者称为寻路算法来实现的。通俗地说，就是在一张地图中，如何让主角自动行走到指定的地点，如图6-21所示，假设主角在A处，然后玩家在地图中点击B处，要求主角能够从A点自动找寻一条到 B 点的路径，然后自动移动到 B处，要求就这么简单。
在前面的碰撞检测算法中，我们提到，现在的游戏中的地图一般采用格子的方式，虽然表面地图上无法看到实际的格子，但在地图的结构中专门有一个逻辑层，这个层和地图大小等大，划分出很多小的格子，然后在可以通过的地方使用0表示，有障碍的且不能通过的地方使用 1 或其他数字表示。如下图所示，左边的游戏中的地图，程序中会以右边的一个二维数组保存一个逻辑层，专门用来设定障碍。有了这个逻辑层之后，实际上自动寻路就转化成了，如何在一个二维的数组中找到一条从逻辑值为 0 的地点移动到目标地点的路径。
在介绍如何使用自动寻路算法前，我们先来看另外一个游戏常用的算法，即随机产生地图（迷宫）算法，用于结合寻路算法。
【随机迷宫算法】
根据前面的地图的理论，本质上，地图的障碍逻辑层是由一个二维数组保存，障碍标记在二维数组中的数据值以0或1表示，我们需要做的就是随机产生这个二维的数组。当然，最简单的办法就是循环这个二维数组然后在每一个位置随机地产生 0 或者 1，但这种算法产生的图形比较难看，并且不一定保证图中的任意两点可以相连通。
（1）下图所示为一个6×6的迷宫，先假设迷宫中所有的通路都是完全封闭的，白色的格子表示可以通过，黑色的表示墙壁，表示无法通过。
（2）随机选择一个白色的格子作为当前正在访问的格子，同时，把该格子放进一个表示已经访问的列表。
（3）循环以下操作直到所有的格子都被访问。
通过以上的迷宫生成算法，可以生成一个自然随机的迷宫。
下面的代码根据以上的算法将产生一个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代码运行工具：http://tools.jb51.net/code/HtmlJsRun 测试上述代码运行效果如下：
github地址：https://github.com/krapnikkk/JS-gameMathematics
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法详解【普里姆算法】的详细内容，希望对您有所帮助，信息来源于网络。