迷宫程序 链接，
迷宫生成：
解迷宫：
迷宫生成算法的可视化演示，使用 React 来实现。
迷宫的生成，涉及在图中找出生成树相关算法。
解迷宫，就是在生成的树上，进行深度遍历，寻找链接指定两个点的唯一可达路线。
以下为具体的部分关键实现代码。
import React, { Component } from 'react';
import './maze.css';
import Grid from './Grid';
class AppDemo extends Component {
constructor(proprs) {
super(proprs);
var column = 20;//默认列数
var row = 15;//默认行数
var pixel = 35;//默认单位方格像素数
var staticMatrix = this.initStaticMatrix(column, row);//静态二维数组，第一维度是位置编号，第二维度是当下位置的邻居编号
var dynamicMatrix = this.initDynamicMatrix(column, row);//动态二维数组，第一维度是位置编号，第二维度是当下位置已连接的方向信息
var elements = this.initElements(column, row);
var arr = this.initArr(column, row);
var start = Math.floor(Math.random() * column * row + 1);//随机初始位置
this.state = {
staticMatrix: staticMatrix,
dynamicMatrix: dynamicMatrix,
now: start,//当下位置*
begin: start,//开始位置
end: start,//最后一个位置
column: column,//列数
row: row,//行数
timeID: 0,//定时器ID
speed: 100,//速度（毫秒）
speedtype: "中",//用于界面速度显示
pixel: pixel,//方格像素数
step: false,//是否参与过单步
time: 0,//用时显示
begintime: 0,//起始时间
stoptime: 0,//完成时间
reverse: [0, 3, 4, 1, 2], //用于快速反向
elements: elements,//边界元素集合
over: column * row,
maxwidth: 900,//最大宽度像素数
maxheight: 600,//最大高度像素数
arr: arr,//路径元素编号信息
historyPath: [],//路径栈
findtime: 0,//用时显示
findbegintime: 0,//起始时间
findstoptime: 0,//完成时间
findtimeID: 0,//定时器ID
findover: false,//寻路完毕
findStep: false,//是否参与过单步
hide: false //是否隐藏界面中的标记
}
}
/**
* 每一步的处理算法，调用一次，迷宫界面就会向前走一步，方向是随机的
*/
handle() {
var elements = this.state.elements;
var r = this.around(this.state.now, this.state.dynamicMatrix);//返回未涉足邻居编号集合
if (r.length < 1) {//若未涉足邻居个数小于1（即从当下位置出发已经无路可走），则随机切换到边界集合中的其他位置
if (this.state.over <= 1) {
this.stop();
//this.info("迷宫已经生成完毕。");
return;
}
var randomNow = this.randomElement(elements);
this.setState({
time: (new Date().getTime() - this.state.begintime) / 1000,
now: randomNow
});
} else {
//方向随机1表示向上，2表示向右，3表示向下，4表示向左
var direction = this.randomDirection(r);//随机取一个方向
var next = this.state.staticMatrix[this.state.now][direction];//下一个位置编号
if (this.around(next, this.state.dynamicMatrix).length >= 2) {//如果下一个位置的未涉足邻居个数大于等于2，则标记为边界。
elements[next] = 1;
}
var dynamicMatrix = this.state.dynamicMatrix;//动态生成的“树”
this.connect(this.state.now, direction, next, dynamicMatrix);//连接now和next
this.setState({
time: (new Date().getTime() - this.state.begintime) / 1000,
now: next,
elements: this.freshElements(elements, next, dynamicMatrix),
dynamicMatrix: dynamicMatrix,
over: this.state.over - 1
});
}
}
findPath() {
if (this.state.findover === false && this.state.over <= 1) {
var historyPath = this.state.historyPath;//历史路径
var dynamicMatrix = this.state.dynamicMatrix;
var arr = this.state.arr;//路径编号
var staticMatrix = this.state.staticMatrix;
if (historyPath.length === 0) {
historyPath.push(dynamicMatrix[1].concat());
//arr[historyPath[historyPath.length - 1][0]][] = 1;
}
var nowRow = historyPath[historyPath.length - 1][0];//获取当下的位置编号
var b = false;
for (var i = 1; i <= 4; i++) {
var p = historyPath[historyPath.length - 1][i];
if (p === 1) {
var next = staticMatrix[nowRow][i];
historyPath.push(dynamicMatrix[next].concat());
historyPath[historyPath.length - 1][this.state.reverse[i]] = 0;
arr[next][this.state.reverse[i]] = 1;
arr[nowRow][i] = 1;
this.setState({
findtime: (new Date().getTime() - this.state.findbegintime) / 1000,
historyPath: historyPath,
arr: arr
});
if (next === this.state.column * this.state.row) {
this.findStop();
this.setState({
findover: true
});
//this.info("迷宫路径已找到（暂时只支持从左上到右下）。");
return;
}
b = true;
break;
}
}
if (!b) {//如果无路可走
//判断当下路径（未退步之前）是否包含于历史记录。
var nown = historyPath[historyPath.length - 1][0];
var last = historyPath[historyPath.length - 2][0];
arr[nown] = [nown,0,0,0,0];
historyPath.pop();
for (var j = 1; j <= 4; j++) {
var p2 = historyPath[historyPath.length - 1][j];
if (p2 === 1) {
arr[last][j] = 0;
historyPath[historyPath.length - 1][j] = 0;
this.setState({
findtime: (new Date().getTime() - this.state.findbegintime) / 1000,
historyPath: historyPath,
arr: arr
});
break;
}
}
}
} else {
this.findStop();
}
}
/**
* 启动解迷宫程序
*/
findStart() {
if (this.state.over <= 1) {//若迷宫已经生成完毕，才可以解迷宫
var findtimeID = this.state.findtimeID;
if (findtimeID === 0) {//若 当下定时器不为0，则启动新定时器（防止重复启动多个定时器）
findtimeID = setInterval(
() => this.findPath(),
this.state.speed
);
this.setState({
findbegintime: new Date().getTime() - this.state.findtime * 1000,
findtimeID: findtimeID,
now: 0
});
}
}else{
this.info("需要先生成迷宫，才能解迷宫的！笨蛋");
}
}
findStop() {
var findtimeID = this.state.findtimeID;
if (findtimeID !== 0) {
clearInterval(findtimeID);
this.setState({
findtimeID: 0
});
}
}
findStep() {
this.findStop();
this.findPath();
this.setState({
findStep: true
});
}
hide(){
this.setState({
hide: !this.state.hide
});
}
render() {
return (
<div className="maze">
<div className="aaa">
<Grid
pixel={this.state.pixel}
width={this.state.column}
height={this.state.row}
dynamicMatrix={this.state.dynamicMatrix}
now={this.state.now}
elements={this.state.elements}
begin={this.state.begin}
end={this.state.end}
arr={this.state.arr}
hide={this.state.hide}
/>
</div>
<div className="bbb">
<div className="control navbar navbar-default">
<span className="title">生成迷宫：（用时{this.state.step ? "单步参与后不再计时" : (this.state.time + "s")}）</span><br />
<span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.start()}>开始</button><span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.stop()}>暂停</button><span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.start()}>继续</button><span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.step()}>单步</button><span > </span>
</div>
<div className="control navbar navbar-default">
<span className="title">解迷宫：（用时{this.state.findStep ? "单步参与后不再计时" : (this.state.findtime + "s")}）<span > </span>{this.state.findover?("找到，路径长度为："+this.state.historyPath.length)+"":"迷宫入口为左上角，出口为右下角。"}</span><br />
<span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.findStart()}>开始</button><span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.findStop()}>暂停</button><span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.findStart()}>继续</button><span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.findStep()}>单步</button><span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.resetFind()}>清除</button>
</div>
<div className="control navbar navbar-default">
<span className="title">速度：{this.state.speedtype}</span><br />
<span > </span>
<button className="btn btn-primary navbar-btn" type="button" onClick={() => this.speed(1000)}>极慢</button><span > </span>
<button className="btn btn-primary navbar-btn" type="button" onClick={() => this.speed(500)}>慢</button><span > </span>
<button className="btn btn-primary navbar-btn" type="button" onClick={() => this.speed(100)}>中</button><span > </span>
<button className="btn btn-primary navbar-btn" type="button" onClick={() => this.speed(50)}>快</button><span > </span>
<button className="btn btn-primary navbar-btn" type="button" onClick={() => this.speed(10)}>极���</button>
</div>
<div className="control navbar navbar-default">
<span className="title">列数：{this.state.column}</span><br />
<span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.addwidth(1)}>列+1</button><span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.addwidth(-1)}>列-1</button>
<span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.addwidth(5)}>列+5</button><span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.addwidth(-5)}>列-5</button><br />
</div>
<div className="control navbar navbar-default">
<span className="title">行数：{this.state.row}</span><br />
<span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.addheight(1)}>行+1</button><span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.addheight(-1)}>行-1</button>
<span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.addheight(5)}>行+5</button><span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.addheight(-5)}>行-5</button><br />
</div>
<div className="control navbar navbar-default">
<span className="title">大小：{this.state.column * this.state.pixel}px : {this.state.row * this.state.pixel}px</span><br />
<span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.big(1)}>放大+1</button><span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.big(-1)}>缩小-1</button>
<span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.big(5)}>放大+5</button><span > </span>
<button className="btn btn-primary navbar-btn" style={{ width: "80px" }} type="button" onClick={() => this.big(-5)}>缩小-5</button><br />
</div>
<div className="control navbar navbar-default">
<span className="title">其他：</span><br />
<span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.hide()}>{this.state.hide?"显示标记":"隐藏标记"}</button><span > </span>
<button type="button" className="btn btn-primary navbar-btn" onClick={() => this.resetAll()}>全部重置</button>
</div>
</div>
</div >
)
}
/**
* 连接now和next两个位置
* @param {*} now
* @param {*} direction
* @param {*} next
* @param {*} dynamicMatrix
*/
connect(now, direction, next, dynamicMatrix) {
dynamicMatrix[now][direction] = 1;//连接下一个位置
dynamicMatrix[next][this.state.reverse[direction]] = 1;//连接下一个位置
}
/**
* 从边界集合中随机选择一个返回
* @param {} elements
*/
randomElement(elements) {
var u = this.state.column * this.state.row
var n = Math.floor(Math.random() * u);
var i = 0;
while (elements[n] !== 1) {
i++;
n++;
if (n > u) {
n = 1;
}
if (i > u) {
n = 0;
break;
}
}
return n;
}
/**
* 初始化StaticMatrix
* @param {*} width
* @param {*} height
*/
initStaticMatrix(width, height) {
var matrix = [[0, 1, 2, 3, 4]];
for (var numb = 1; numb <= width * height; numb++) {
var up = numb > width ? numb - width : 0;
var right = (numb % width) !== 0 ? numb + 1 : 0;
var down = numb <= width * (height - 1) ? numb + width : 0;
var left = ((numb - 1) % width) !== 0 ? numb - 1 : 0;
var arr = [numb];
arr.push(up);
arr.push(right);
arr.push(down);
arr.push(left);
matrix.push(arr);
}
return matrix;
}
/**
* 初始化DynamicMatrix
* @param {*} width
* @param {*} height
*/
initDynamicMatrix(width, height) {
var dynamicMatrix = [[0, 1, 2, 3, 4]];
for (var numb = 1; numb <= width * height; numb++) {
var up = 0;
var right = 0;
var down = 0;
var left = 0;
var arr = [numb];
arr.push(up);
arr.push(right);
arr.push(down);
arr.push(left);
dynamicMatrix.push(arr);
}
return dynamicMatrix;
}
initArr(width, height) {
var dynamicMatrix = [[0, 1, 2, 3, 4]];
for (var numb = 1; numb <= width * height; numb++) {
var up = 0;
var right = 0;
var down = 0;
var left = 0;
var arr = [numb];
arr.push(up);
arr.push(right);
arr.push(down);
arr.push(left);
dynamicMatrix.push(arr);
}
return dynamicMatrix;
}
/**
* 初始化Elements边界集合
* @param {*} column
* @param {*} row
*/
initElements(column, row) {
var arr = new Array(column * row + 1);
for (var i = 0; i < arr.length; i++) {
arr[i] = 0;
}
return arr;
}
/**
* 返回未涉足邻居编号集合
* 参数new,是当下位置的编号
*/
around(now, dynamicMatrix) {
var r = [];
for (var j = 1; j <= 4; j++) {//每个位置周边共四个“邻居”
var runod = this.state.staticMatrix[now][j];//其中一个邻居
//判断“邻居”是否已经被涉足，若没有，则将此邻居方向编号加入将要返回的集合中
if (runod !== 0 && (dynamicMatrix[runod][1] === 0
&& dynamicMatrix[runod][2] === 0
&& dynamicMatrix[runod][3] === 0
&& dynamicMatrix[runod][4] === 0)) {
r.push(j);
}
}
return r;//返回未涉足邻居方向编号集合
}
/**
* 从邻居中随机选出一个作为下一个位置
* @param {*} r
*/
randomDirection(r) {
if (r.length === 1) {
return r[r.length - 1];
}
return r[Math.floor(Math.random() * r.length)];
}
/**
* 刷新边界集合，（每前进一步，整个盘面唯有一个位置有所改变，所以只扫面更新此位置四周即可）
* @param {*} elements
* @param {*} next
* @param {*} dynamicMatrix
*/
freshElements(elements, next, dynamicMatrix) {
for (var n = 1; n <= 4; n++) {
var runod = this.state.staticMatrix[next][n];//其中一个邻居
//判断“邻居”是否已经被涉足，若没有，则将此邻居编号加入将要返回的集合中
if (elements[runod] !== 0 && this.around(runod, dynamicMatrix).length === 0) {//如果elements[n]周围没有未涉足区域，则从边缘集合中去掉
elements[runod] = 0;
}
}
return elements;
}
/**
* 添加列数，n为添加的列数
* @param {*} n
*/
addwidth(n) {
this.stop();
var column = this.state.column;
column = column + n;
if (column > 0 && column * this.state.pixel <= this.state.maxwidth) {
var staticMatrix = this.initStaticMatrix(column, this.state.row);
var dynamicMatrix = this.initDynamicMatrix(column, this.state.row);
var elements = this.initElements(column, this.state.row);
var arr = this.initArr(column, this.state.row);
var start = Math.floor(Math.random() * column * this.state.row + 1);
this.setState({
staticMatrix: staticMatrix,
dynamicMatrix: dynamicMatrix,
begin: start,
now: start,
column: column,
time: 0,
elements: elements,
over: column * this.state.row,
arr: arr,
historyPath: [],
findtime: 0,
findover: false
});
} else {
var maxColumn = Math.floor(this.state.maxwidth / this.state.pixel);
var staticMatrix1 = this.initStaticMatrix(maxColumn, this.state.row);
var dynamicMatrix1 = this.initDynamicMatrix(maxColumn, this.state.row);
var elements1 = this.initElements(maxColumn, this.state.row);
var arr1 = this.initArr(maxColumn, this.state.row);
var newstart = Math.floor(Math.random() * maxColumn * this.state.row + 1);
this.setState({
staticMatrix: staticMatrix1,
dynamicMatrix: dynamicMatrix1,
begin: newstart,
now: newstart,
column: maxColumn,
time: 0,
elements: elements1,
over: maxColumn * this.state.row,
arr: arr1,
historyPath: [],
findtime: 0,
findover: false
});
}
}
/**
* 添加行数，n为添加的行数
* @param {*} n
*/
addheight(n) {
this.stop();
var row = this.state.row;
row = row + n;
if (row > 0 && row * this.state.pixel <= this.state.maxheight) {
var staticMatrix = this.initStaticMatrix(this.state.column, row);
var dynamicMatrix = this.initDynamicMatrix(this.state.column, row);
var elements = this.initElements(this.state.column, row);
var arr = this.initArr(this.state.column, row);
var start = Math.floor(Math.random() * this.state.column * row + 1);
this.setState({
staticMatrix: staticMatrix,
dynamicMatrix: dynamicMatrix,
begin: start,
now: start,
row: row,
time: 0,
elements: elements,
over: this.state.column * row,
arr: arr,
historyPath: [],
findtime: 0,
findover: false
});
} else {
var maxRow = Math.floor(this.state.maxheight / this.state.pixel);
var staticMatrix1 = this.initStaticMatrix(this.state.column, maxRow);
var dynamicMatrix1 = this.initDynamicMatrix(this.state.column, maxRow);
var elements1 = this.initElements(this.state.column, maxRow);
var arr1 = this.initArr(this.state.column, maxRow);
var newstart = Math.floor(Math.random() * this.state.column * maxRow + 1);
this.setState({
staticMatrix: staticMatrix1,
dynamicMatrix: dynamicMatrix1,
begin: newstart,
now: newstart,
time: 0,
row: maxRow,
elements: elements1,
over: this.state.column * maxRow,
arr: arr1,
historyPath: [],
findtime: 0,
findover: false
});
}
}
/**
* 缩放界面大小，n为每个单位方格改变的像素数
* @param {*} n
*/
big(n) {
var pixel = this.state.pixel;
pixel = pixel + n;
if (pixel >= 5 && ((pixel * this.state.column <= this.state.maxwidth) && (pixel * this.state.row <= this.state.maxheight))) {
this.setState({
pixel: pixel
});
return;
}
if(pixel < 5 ){
this.info("已经最小，再小你就看不见了，你以为你是显微镜呀！");
this.setState({
pixel: 5
});
}else {
this.info("不能再大了，笨蛋");
this.setState({
pixel: Math.floor((pixel * this.state.column / this.state.maxwidth > pixel * this.state.row / this.state.maxheight) ? (this.state.maxwidth / this.state.column) : (this.state.maxheight / this.state.row))
});
}
}
/**
* 重置应用，使其除行列和大小外，其他因素设置成初始状态
*/
resetAll() {
this.stop();
var staticMatrix = this.initStaticMatrix(this.state.column, this.state.row);
var dynamicMatrix = this.initDynamicMatrix(this.state.column, this.state.row);
var elements = this.initElements(this.state.column, this.state.row);
var arr = this.initArr(this.state.column, this.state.row);
var start = Math.floor(Math.random() * this.state.column * this.state.row + 1);
this.setState({
staticMatrix: staticMatrix,
dynamicMatrix: dynamicMatrix,
begin: start,
now: start,
time: 0,
elements: elements,
over: this.state.column * this.state.row,
arr: arr,//路径元素编号信息
historyPath: [],//路径栈
findtime: 0,//用时显示
findbegintime: 0,//起始时间
findstoptime: 0,//完成时间
findtimeID: 0,//定时器ID
findover: false,//寻路完毕
findStep: false,//是否参与过单步
hide: false //是否隐藏界面中的标记
});
}
/**
* 重置应用，使其除行列和大小外，其他因素设置成初始状态
*/
resetFind() {
this.findStop();
var arr = this.initArr(this.state.column, this.state.row);
this.setState({
arr: arr,//路径元素编号信息
historyPath: [],//路径栈
findtime: 0,//用时显示
findbegintime: 0,//起始时间
findstoptime: 0,//完成时间
findtimeID: 0,//定时器ID
findover: false,//寻路完毕
findStep: false,//是否参与过单步
hide: false //是否隐藏界面中的标记
});
}
/**
* 单步
*/
step() {
this.stop();
this.handle();
this.setState({
step: true
});
}
/**
* 开始
*/
start() {
var timeID = this.state.timeID;
if (timeID === 0) {
timeID = setInterval(
() => this.handle(),
this.state.speed
);
this.setState({
begintime: new Date().getTime() - this.state.time * 1000,
timeID: timeID
});
}
}
/**
* 暂停
*/
stop() {
var timeID = this.state.timeID;
if (timeID !== 0) {
clearInterval(timeID);
this.setState({
timeID: 0
});
}
}
/**
* 改变速度，n为新的时间间隔，单位ms，每隔n ms时间，定时器调用一次相关方法
* @param {*} n
*/
speed(n) {
var timeID = this.state.timeID;
if (timeID !== 0) {
clearInterval(timeID);
timeID = 0;
timeID = setInterval(
() => this.handle(),
n
);
}
var findtimeID = this.state.findtimeID;
if (findtimeID !== 0) {
clearInterval(findtimeID);
findtimeID = 0;
findtimeID = setInterval(
() => this.findPath(),
n
);
}
var speedtype = "";
if (n === 10) {
speedtype = "极快";
}
if (n === 50) {
speedtype = "快";
}
if (n === 100) {
speedtype = "中";
}
if (n === 500) {
speedtype = "慢";
}
if (n === 1000) {
speedtype = "极慢";
}
this.setState({
timeID: timeID,
findtimeID: findtimeID,
speed: n,
speedtype: speedtype
});
}
info(info){
alert(info);
}
}
export default AppDemo;
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于