前言：
眼前你们对“js迷宫源码”大约比较关注，朋友们都需要剖析一些“js迷宫源码”的相关知识。那么小编也在网络上收集了一些关于“js迷宫源码””的相关资讯，希望小伙伴们能喜欢，朋友们快快来了解一下吧！很多小朋友喜欢用笔在纸上画线进行走迷宫游戏。
比如下图这种迷宫：从标注了S（Start-起点）的位置出发，走到终点E（End）就算成功。
那么，如何随机生成上图这种迷宫地图呢？
我在github上部署了一个迷宫地图生成应用：
每次进入这个应用或者按F5刷新，就会随机生成一张新的迷宫地图：
这个应用仅仅需要使用到两个JavaScript脚本文件和一个html文件。
html文件的源代码：
<!doctype html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<meta http-equiv="Pragma" content="no-cache" />
<meta http-equiv="Expires" content="-1" />
<meta http-equiv="Cache-Control" content="no-cache" />
<meta charset="utf-8">
<title>Maze Demo</title>
<!-- <meta name="viewport" content="width=device-width, height=device-height, initial-scale=1, minimum-scale=1, maximum-scale=1, user-scalable=no, target-densitydpi=device-dpi" /> -->
<meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1, maximum-scale=1, user-scalable=no" />
<meta name="apple-mobile-web-app-title" content="H5Game">
<meta name="apple-touch-fullscreen" content="yes" >
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name='format-detection' content='telephone=no'>
<meta name="screen-orientation" content="portrait">
<meta name="full-screen" content="yes">
<meta name="x5-fullscreen" content="true">
<meta name="360-fullscreen" content="true">
<script type="text/javascript" src="maze//Maze.js"></script>
<script type="text/javascript" src="maze/main.js"></script>
<script type="text/javascript">
</script>
<style>
#toolbar {
position: absolute;
padding:2px;
top:0;
right:0;
width:180px;
}
#toolbar button {
padding:10px;
font-size:16px;
margin:5px;
}
</style>
</head>
<body>
<div id="container" class="splash">
<canvas id="canvas"></canvas>
<div id="info"></div>
</div>
</body>
</html>
迷宫的轮廓模型生成逻辑位于代码Maze.js里：
"use strict";
var Maze = function(options) {
for (var p in options) {
this[p] = options[p];
}
};
Maze.prototype = {
constructor: Maze,
width: 0,
height: 0,
grid: null,
startNode: null,
endNode: null,
// 是否每走一步, 都尝试回溯.
alwaysBacktrace: false,
init: function() {
this.trace = [];
this.size = this.width * this.height;
this.initGrid();
this.onInit();
},
initGrid: function() {
var grid = this.grid = [];
for (var r = 0; r < this.height; r++) {
var row = [];
grid.push(row);
for (var c = 0; c < this.width; c++) {
var node = {
x: c,
y: r,
value: 0,
};
row.push(node);
}
}
},
onInit: function() {},
random: function(min, max) {
return ((max - min + 1) * Math.random() + min) >> 0;
},
getNode: function(c, r) {
return this.grid[r][c];
},
getRandomNode: function() {
var r = this.random(0, this.height - 1);
var c = this.random(0, this.width - 1);
return this.grid[r][c];
},
setMark: function(node, value) {
return node.value |= value;
},
removeMark: function(node, value) {
return node.value &= ~value;
},
isMarked: function(node, value) {
return (node.value & value) === value;
},
setStart: function(c, r) {
var node = this.grid[r][c];
this.startNode = node;
},
setEnd: function(c, r) {
var node = this.grid[r][c];
this.endNode = node;
},
setCurrent: function(node) {
this.current = node;
this.neighbors = this.getValidNeighbors(node);
if (this.neighbors && node.value === 0) {
this.trace.push(node);
this.onTrace(node);
}
},
onTrace: function(node) {
},
moveTo: function(node, dir) {
this.beforeMove(node);
this.current.value |= dir;
this.setCurrent(node);
node.value |= Maze.Direction.opposite[dir];
this.afterMove(node);
},
beforeMove: function(node) {
},
afterMove: function(node) {
},
start: function() {
this.beforeStart();
this.setCurrent(this.startNode);
this.stepCount = 0;
while (this.nextStep()) {
this.stepCount++;
if (this.isOver() === true) {
break;
}
// console.log(step);
}
console.log("Step Count : " + this.stepCount);
},
beforeStart: function() {},
// 生成迷宫时的提前终止条件
isOver: function() {},
nextStep: function() {
if (!this.neighbors) {
return this.backtrace();
}
var n = this.getNeighbor();
this.moveTo(n[0], n[1]);
this.updateCurrent();
return true;
},
backtrace: function() {
var len = this.trace.length;
while (len > 0) {
var idx = this.getTraceIndex();
var node = this.trace[idx];
var n = this.getValidNeighbors(node);
if (n) {
this.current = node;
this.neighbors = n;
return true;
} else {
this.trace.splice(idx, 1);
len--;
}
}
return false;
},
/***************************************
通过重写以下几个方法, 可以实现不同的迷宫效果
**************************************/
getValidNeighbors: function(node) {
var n = [];
var c = node.x;
var r = node.y;
var nearNode, dir;
nearNode = r > 0 ? this.grid[r - 1][c] : null;
dir = Maze.Direction.N;
this.isValid(nearNode, node, dir) && n.push([nearNode, dir]);
nearNode = this.grid[r][c + 1];
dir = Maze.Direction.E;
this.isValid(nearNode, node, dir) && n.push([nearNode, dir]);
nearNode = r < this.height - 1 ? this.grid[r + 1][c] : null;
dir = Maze.Direction.S;
this.isValid(nearNode, node, dir) && n.push([nearNode, dir]);
nearNode = this.grid[r][c - 1];
dir = Maze.Direction.W;
this.isValid(nearNode, node, dir) && n.push([nearNode, dir]);
n = this.updateNeighbors(node, n);
return n.length > 0 ? n : null;
},
updateNeighbors: function(node, neighbors) {
return neighbors;
},
isValid: function(nearNode, node, dir) {
return nearNode && nearNode.value === 0;
},
updateCurrent: function() {
if (this.alwaysBacktrace) {
this.backtrace();
}
},
getNeighbor: function() {
var n = this.neighbors[this.neighbors.length * Math.random() >> 0];
return n;
},
getTraceIndex: function() {
var idx = this.trace.length - 1;
return idx;
},
};
Maze.Direction = {
N: 1,
S: 2,
E: 4,
W: 8,
opposite: {
1: 2,
2: 1,
4: 8,
8: 4
},
stepX: {
1: 0,
2: 0,
4: 1,
8: -1
},
stepY: {
1: -1,
2: 1,
4: 0,
8: 0
},
};
迷宫的渲染位于脚本文件main.js里：
var maze = new Maze({
width: 60,
height: 40,
perfect: true,
onInit: function() {
this.checkCount = {};
this.foundEndNode = false;
},
isValid: function(nearNode, node, dir) {
if (!nearNode) {
return false;
}
if (nearNode && nearNode.value === 0) {
return true;
}
if (this.perfect) {
return false;
}
var c = nearNode.x,
r = nearNode.y;
// 用于生成一种非Perfect迷宫
this.checkCount[c + "-" + r] = this.checkCount[c + "-" + r] || 0;
var count = ++this.checkCount[c + "-" + r];
return Math.random() < 0.3 && count < 3;
},
updateCurrent: function() {
// 每步有 10% 的概率 进行回溯
if (Math.random() <= 0.10) {
this.backtrace();
}
},
getTraceIndex: function() {
// 按一定的概率随机选择回溯策略
var r = Math.random();
var len = this.trace.length;
var idx = 0;
if (r < 0.5) {
idx = len - 1;
} else if (r < 0.7) {
idx = len >> 1;
} else if (r < 0.8) {
idx = len * Math.random() >> 0;
}
return idx;
},
isOver: function() {
if (this.current == this.endNode) {
this.foundEndNode = true;
}
// 当探索到迷宫终点, 且探索了至少一半的区域时,终止迷宫的生成
if (this.foundEndNode && this.stepCount >= this.size / 2) {
return true;
}
return false;
}
});
window.onload = function() {
start();
}
function createPerfectMaze() {
createMaze(true);
}
function createMaze(perfect) {
maze.perfect = perfect || false;
maze.init();
// maze.setStart(0, 0);
// maze.setEnd(4, 4);
maze.startNode = maze.getRandomNode();
do {
maze.endNode = maze.getRandomNode();
} while (maze.startNode == maze.endNode);
maze.start();
renderMaze(context, maze);
}
function $id(id) {
return document.getElementById(id);
}
var canvas, context;
function start() {
canvas = $id("canvas");
context = canvas.getContext("2d");
createMaze(true);
}
function renderMaze(context, maze) {
// var grid = JSON.parse(JSON.stringify(maze.grid));
var grid = maze.grid;
var wallWidth = 2;
var cellSize = 15;
var width = cellSize * maze.width;
var height = cellSize * maze.height;
var x = 10,
y = 10;
canvas.width = width + wallWidth + x * 2;
canvas.height = height + wallWidth + y * 2;
context.fillStyle = "#eeeeee";
context.fillRect(0, 0, canvas.width, canvas.height);
context.fillStyle = "#334466";
context.strokeStyle = "#334466";
context.font = "12px Arial";
context.lineWidth = wallWidth;
for (var r = 0; r < grid.length; r++) {
var row = grid[r];
for (var c = 0; c < row.length; c++) {
var node = row[c];
var cx = c * cellSize + x;
var cy = r * cellSize + y;
if (!node.value) {
context.fillRect(cx, cy, cellSize, cellSize);
continue;
}
if (node == maze.startNode) {
context.fillText("S", cx + cellSize * 1 / 3, cy + cellSize - 2);
} else if (node == maze.endNode) {
context.fillText("E", cx + cellSize * 1 / 3, cy + cellSize - 2);
} else {
}
var left = (node.value & Maze.Direction.W) !== Maze.Direction.W;
var top = (node.value & Maze.Direction.N) !== Maze.Direction.N;
if (left && top) {
context.fillRect(cx, cy, wallWidth, cellSize);
context.fillRect(cx, cy, cellSize, wallWidth);
} else if (left) {
context.fillRect(cx, cy, wallWidth, cellSize);
} else if (top) {
context.fillRect(cx, cy, cellSize, wallWidth);
} else {
var w = false;
if (r > 0) {
w = (grid[r - 1][c].value & Maze.Direction.W) !== Maze.Direction.W;
}
if (w && c > 0) {
w = (grid[r][c - 1].value & Maze.Direction.N) !== Maze.Direction.N;
}
var ltc = w ? 1 : 0;
if (ltc) {
context.fillRect(cx, cy, wallWidth, wallWidth);
}
}
}
}
context.fillRect(x, cellSize * maze.height + y, cellSize * maze.width, wallWidth);
context.fillRect(cellSize * maze.width + x, y, wallWidth, cellSize * maze.height + wallWidth);
}
标签： #js迷宫源码
