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，把该格子作为当前访问的格子，并放入访问列表。
- 如果周围所有的格子都已访问过，则从已访问列表中随机选取一个作为当前访问的格子。
通过以上的迷宫生成算法，可以生成一个自然随机的迷宫。
下面的代码根据以上的算法将产生一个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程序设计有所帮助。
相关推荐
-
node.js与C语言 实现遍历文件夹下最大的文件，并输出路径，大小
node.js版 遍历文件夹下最大的文件,并输出路径,大小 实现代码: /* 遍历文件夹下最大的文件,并输出路径,大小 */ function findmax(basepath){ //只能执行一次 if(findmax.s) return; findmax.s = true; var fs = require('fs'); var maxfile = 0; var count = 0; var begin = new Date().getTime(); function Travers
-
JS使用Dijkstra算法求解最短路径
一.Dijkstra算法的思路 Dijkstra算法是针对单源点求最短路径的算法. 其主要思路如下: 1. 将顶点分为两部分:已经知道当前最短路径的顶点集合Q和无法到达顶点集合R. 2. 定义一个距离数组(distance)记录源点到各顶点的距离,下标表示顶点,元素值为距离.源点(start)到自身的距离为0,源点无法到达的顶点的距离就是一个大数(比如Infinity). 3. 以距离数组中值为非Infinity的顶点V为中转跳点,假设V跳转至顶点W的距离加上顶点V至源点的距离还小于顶点W至源点
-
JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例
本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法.分享给大家供大家参考,具体如下: 原理可参考:https://www.jb51.net/article/152744.htm 完整实例代码如下: <!DOCTYPE html> <html lang="en"> <head> <meta name="viewport" content="width=device-width, initial-s
-
JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法详解【普里姆算法】
本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法.分享给大家供大家参考,具体如下: 路径搜索算法在游戏中非常常见,特别是在 RPG.SLG 中经常用到.在这些游戏中,通过鼠标指定行走目的地,人物或者NPC就会自动行走到目标地点,这就是通过路径搜索或者称为寻路算法来实现的.通俗地说,就是在一张地图中,如何让主角自动行走到指定的地点,如图6-21所示,假设主角在A处,然后玩家在地图中点击B处,要求主角能够从A点自动找寻一条到 B 点的路径,然后自动移动到 B处,要求就这么简单.
-
JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法详解【凹多边形的分离轴检测算法】
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法.分享给大家供大家参考,具体如下: 概述 分离轴定理是一项用于检测碰撞的算法.其适用范围较广,涵盖检测圆与多边形,多边形与多边形的碰撞:缺点在于无法检测凹多边形的碰撞.本demo使用Js进行算法实现,HTML5 canvas进行渲染. 详细 一.准备工作,熟悉分离轴定理 算法原理 从根本上来讲,分离轴定理(以及其他碰撞算法)的用途就是去检测并判断两个图形之间是否有间隙.分离轴定理中用到的方法使算法本身显得十分独特. 我所听到过分
-
JS/HTML5游戏常用算法之追踪算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之追踪算法.分享给大家供大家参考,具体如下: 追踪算法在动作游戏中非常常见,从很早的游戏<吃豆人>到大型的街机机战类游戏,到处可见追踪效果的身影.一个好的追踪算法将会大大提高游戏的可玩性和玩家的兴趣. [简单算法] 先来看一个简单的跟踪算法,如下图所示,假设在canvas坐标系中存在物体A和B,物体A将把B作为追踪目标,物体在二维空间中的运动可以分解为坐标系中X.Y轴的运动,其在X和Y方向的速度决定了物体运行的方向和速率.别忘了,速度是有方向和大小的,
-
JS/HTML5游戏常用算法之碰撞检测 像素检测算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 像素检测算法.分享给大家供大家参考,具体如下: 使用像素碰撞检测法算是最精确的算法了,当然,带来的代价也是比较明显的,那就是效率上的低下.除非是在极为特殊的情况下,要求使用非常精确的碰撞,否则,一般情况下在游戏中是不建议使用这种算法,特别是在运行效率不太高的HTML5游戏中. 一般来说在使用像素碰撞检测之前会使用AABB矩形包围盒先检测两个精灵是否有碰撞,如果AABB包围盒检测没有碰撞,那一定是没有碰撞到,反之,则不一定,需要进一步进行像素检
-
JS/HTML5游戏常用算法之碰撞检测 地图格子算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 地图格子算法.分享给大家供大家参考,具体如下: 这种算法经常用于RPG(早期的<最终幻想>.<DQ>.<仙剑奇侠传>).SLG(<炎龙骑士团>.<超级机器人大战>).PUZ(<俄罗斯方块>.<宝石谜阵>)类型的游戏.这类游戏中,通常情况下整个地图都是由一些地图块元素组成,在制作的时候首先给制作出地图所需要的最基本的元素进行编号,然后把这些编号的地图块组合起来就可以根据需
-
Prim(普里姆)算法求最小生成树的思想及C语言实例讲解
Prim 算法思想: 从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1,再连接与 T1 最近顶点 v2 构成树 T2, 如此重复直到所有顶点均在所构成树中为止. 最小生成树(MST):权值最小的生成树. 生成树和最小生成树的应用:要连通n个城市需要n-1条边线路.可以把边上的权值解释为线路的造价.则最小生成树表示使其造价最小的生成树. 构造网的最小生成树必须解决下面两个问题: 1.尽可能选取权值小的边,但不能构成回路: 2.选取n-1条恰当的边以连通n个顶点: MST性质:假设G＝(V
-
node.js根据不同请求路径返回不同数据详解流程
目录 1.学习根据不同的请求路径返回:不同数据 2.发送的数据:数据类型,和什么编码:Content-Type 3.关于读入文件的:相对路径和绝对路径: 4.读图片 1.学习根据不同的请求路径返回:不同数据 var url=req.url //获取req.url值(req:是request简写) req.url: 获取的是端口号之后的路径 实现不同路径返回不同数据 我的端口号:3000,网址:http://127.0.0.1:3000 if(url==='/'){ res.end('index
-
国庆节到了,利用JS实现一个生成国庆风头像的小工具 详解实现过程
目录 1. 页面布局 2. 图片上传和展示 3. 初始化画布 4. 切换模板 5. 输出图片 这里用到的技术: HTML+ CSS+ JavaScript: download.js库: fabric.js库: 先上体验链接:g.cuggz.com/. 注:可以点击上方的连接进行使用,不过我的域名被TX屏蔽了,还在申诉中,所以无法在QQ.微信中打开,需要复制链接到浏览器进行查看.使用. 下面是这个小工具的截图: 1. 页面布局 这部分不多说,直接上代码: <div class="wrap
-
Python常用内置函数和关键字使用详解
目录 常用内置方法 查看所有的内置类和内置方法 标准输入输出 数学 序列 进制数转换 ASCII字符编码转换 其它 常用关键字 常见内置属性 常用内置方法 在Python中有许许多多的内置方法,就是一些Python内置的函数,它们是我们日常中经常可以使用的到的一些基础的工具,可以方便我们的工作. 查看所有的内置类和内置方法 # 方法一 built_list = dir(__builtins__) # 方法二 import builtins built_list = dir(builtins) 其