共计 7385 个字符，预计需要花费 19 分钟才能阅读完成。
以前尽管写过走迷宫，很多人反映没找到代码不会部署，没看明确原理，这次把更具体写出优化并将代码放到 github，趁着 520,521 能够本人放一些图片献给女神！
起因
先看效果图 ( 文末有动态图)(在线电脑尝试地址 http://biggsai.com/maze.html)：
我的项目 github 地址：https://github.com/javasmall/mazegame：
作为程序猿，经常因为身务忙碌，常常忙于 coding 很少空闲来顾及女朋友，也常被吐槽为渣男。
然而，渣着渣着，却发现 520 到了。卧槽，520？！
咱们经常悔恨本人激动时候说过的话，我筹备个毛线，啥都没筹备，但好体面的我也不可能随随便便坑骗人家女孩子(尽管曾经骗了😭)，
习惯性关上淘宝，逛着看看有没有啥适合的，一想明天曾经 19 号了，卧槽要凉了难道？
一想还有美团补救一下能够送的到，关上美团发现都是吃喝玩，完蛋，真的要凉了。
深夜，我在忏悔本人说过的大话，没本事不能瞎说啊，一早晨啥也干不了啥哇。
等等，还有一早晨耶！
此时我忽然眼前一亮，对于程序猿，一早晨也能制作属于他的浪漫！
打开各种搜索引擎、博客搜素一番：程序员 520 表白神器 代码 果然不出我所料！有货色，哈哈哈ctrl+c,ctrl+v 我可太会了，浪漫要来了！
找了几个代码，发现哇塞好牛哇，还能跑起来，然而发现好多雷同我也找不到原作者是谁，但我心中十分崇拜作者的才华(救命之恩)。
这时我的头脑又浮现她时长对我说的一句话：“ 一点都不上心 ”！这些可能的确都曾经很老套和小儿科了，不行，我要以我本人的形式来！我要有点我本人的特色。
我推敲着怎么用相熟的数据结构与算法搞个乏味的货色。
追忆着我晓得的数据结构与算法：链表、队列、栈、图、dfs、bfs、并查集、Dijkstra、Prime……
以前模摸糊糊如同记得有人用 Java Swing 配合并查集算法画迷宫，我是否能够写一个走迷宫的小游戏呢？但我搜了一下并未发现有 HTML、JavaScript 版本的，但 Swing 那玩意除了特定场景根本没人用我要整一个不一样的，尽管 JavaScript 和 HTML 我不太熟，但我应该能够，加油💪！
剖析
我须要从 0 到 1 的设计实现一个走迷宫游戏，但这外面肯定是艰难阻阻，不过凡是问题都能够先拆开分步，而后一一击破合并。
对于一个走迷宫的小游戏，我想了一下可能须要把握以下的常识：
- 搞懂一个初始地位至完结地位有达到门路的迷宫生成算法
- 用 JavaScript 在 canvas 上画棋盘(迷宫初始状态)
- 利用迷宫生成算法生成一个迷宫(擦除须要擦掉的线)
- 利用 JavaScript、事件监听和 canvas 画图实现方块挪动(要思考不出界、不穿墙)
推敲的过程大略是：
- 画单条线—> 画多个线—> 擦线(造成迷宫)—> 方块挪动、挪动束缚(不出界不穿墙)—> 实现游戏。
画线(棋盘)
对于 html+js(canvas)画的货色以前没接触过，但之前学过 Java Swing 写过五子棋游戏、翻卡牌游戏和这个有点相似，在 html 中有个canvas 的画布，能够在下面画一些货色和申明一些监听(键盘监听)。
对于这种 canvas、Java Swing、QT 等画图库，如果你应用它进行画图，要分明你 画下来的货色 其实就是一条条线，没有理论的属性，你只不过须要在编程语言中依据数据结构与算法去操作画布，让 canvas 画布的内容是对你写的数据结构或算法是一个正确 正当的展示。
所以对于迷宫来说，一个个线条 线条是没有属性 的，只有地位 x,y，你操作这个画布时候，可能和咱们习惯的面相对象思维不一样，设计的线或者点的时候，要可能通过计算推理这些点、线在什么地位，在后续画线、擦线、挪动方格的时候依据这个地位进行操作让整个迷宫在 视觉效果上是残缺对立 的。
对于这个画棋盘的步骤也很简略，首先尝试画一条线，当时想好迷宫每个方格格的大小和方格总个数，之后依照起始 (左上) 坐标程序画程度方向、竖直方向的线(平行线之间起末点地位上有法则的)，最终就能够实现一个视觉上的迷宫。
<!DOCTYPE html>
<html>
<head>
<title>MyHtml.html</title>
</head>
<body>
<canvas id="mycanvas" width="600px" height="600px"></canvas>
</body>
<script type="text/javascript">
var chessboradsize=14;// 棋盘大小
var chess = document.getElementById("mycanvas");
var context = chess.getContext('2d');
function drawChessBoard(){// 绘画
for(var i=0;i<chessboradsize+1;i++){
context.strokeStyle='gray';// 可选区域
context.moveTo(15+i*30,15);// 垂直方向画 15 根线，相距 30px;
context.lineTo(15+i*30,15+30*chessboradsize);
context.stroke();
context.moveTo(15,15+i*30);// 程度方向画 15 根线，相距 30px; 棋盘为 14*14；context.lineTo(15+30*chessboradsize,15+i*30);
context.stroke();}
}
drawChessBoard();// 绘制棋盘
</script>
</html>实现成果
画迷宫
随机迷宫怎么生成？怎么搞？又陷入一脸懵逼。
因为咱们想要迷宫，那么就须要这个迷宫进口和入口有连通门路，不钻研的话很难晓得用什么算法生成这个迷宫。这时耳角传来相熟的声音：用并查集(不相交汇合)。
迷宫和不相交汇合有什么分割呢？(规定)
之前笔者在后面数据结构与算法系列中已经介绍过 并查集 (不相交汇合)，它的次要性能是森林的合并、查找：不联通的通过并查集可能疾速将两个森林合并，并且可能疾速查问两个节点是否在同一个森林(汇合) 中！
而随机迷宫生成正也利用了这个思维：在每个方格都不联通的状况下，是一个 棋盘方格 ，每个迷宫格子绝对独立，这是它的初始状态；前面生成可能须要若干相邻节点进行联通(合并为一个汇合)，且这个节点能够跟街坊可能相连，也可能不相连。咱们能够通过 并查集 实现其底层数据结构的撑持。
在这外面，咱们把每个格子当成一个个汇合元素，而每个汇合与四周的墙则是证实其是否间接联通，咱们就是要通过联通一部分方格 (擦掉局部墙) 实现整个随机迷宫。
具体思路为：(次要了解并查集)
1：定义好不想交汇合的根本类和办法（search,union等）
2：数组初始化，每一个数组元素都是一个汇合，值为 -1
3：随机查找一个格子（一维数据要转换成二维，有点麻烦），在随机找一面墙（也就是找这个格子的上下左右），还要判断找的格子出没出界是否为一个非法的格子。
- 具体生成一个随机数 m(小于迷宫总格子数)
- 将一维随机数 m 转成在迷宫横纵二维地位地位 p，具体为：
[m/ 长,m% 长]这里的 长示意迷宫的行数或者列数。 - 在地位 p 的上下左右随机找一个地位 q
[m/ 长 +1,m% 长]或[m/ 长 -1,m% 长]或[m/ 长,m% 长 +1]或[m/ 长,m% 长 -1] - 判断是否越界，如果越界从新查找，否则进行下一步。
4：判断两个格子 p 和 q(这时候要将二维坐标转成其一维数组编号)是否在一个汇合 ( 并查集查找 )。如果在，则返回第三步从新找，如果不在，那么把墙挖去。
5： 把墙挖去 (合并) 有点繁琐 ，就算两个方格不连通，须要再通过地位判断它那种墙(高低隔离还是左右隔离)，而后再通过计算精确定位到这个墙终点末点地位而后擦掉(须要思考相当多的细节)。
6：反复下面工作，直到第一个(1,1) 和(n,n)联通进行失去一个残缺的迷宫。尽管采纳随机数找方格找墙，然而这个数据量效率和后果都还是挺不错的。
在其中要搞清一维二维数组的关系。一维是实在数据，进行并查集查找、合并操作。转化为二维更多是为了查找地位。要搞懂转化！
留神：防止混同，搞清数组的地址和逻辑矩阵地位。数组从 0 开始的，逻辑上你本人判断，别搞混同！
你可能会问，这个算法为什么最终能生成一个起始开端联通迷宫，因为咱们的终止就是以它为条件，不连通的话就会让迷宫内随机联通一个本不联通的迷宫，而这种可能性是很无限的, 所以到不了最坏状况就能满足迷宫联通，而后又是随机找点，能够让迷宫看起来更匀称一些。
次要逻辑为：
while(search(0)!=search(aa*aa-1))// 次要思路
{var num = parseInt(Math.random() * aa*aa );// 产生一个小于 196 的随机数
var neihbour=getnei(num);
if(search(num)==search(neihbour)){continue;}
else// 不在一个上
{isling[num][neihbour]=1;isling[neihbour][num]=1;
drawline(num,neihbour);// 划线
union(num,neihbour);
}
}那么在后面的代码为
<!DOCTYPE html>
<html>
<head>
<title>MyHtml.html</title>
</head>
<body>
<canvas id="mycanvas" width="600px" height="600px"></canvas>
</body>
<script type="text/javascript">
var chessboradSize=14;
var chess = document.getElementById("mycanvas");
var context = chess.getContext('2d');
var tree = [];// 寄存是否联通
var isling=[];// 判断是否相连
for(var i=0;i<chessboradSize;i++){tree[i]=[];
for(var j=0;j<chessboradSize;j++){tree[i][j]=-1;// 初始值为 0
}
} for(var i=0;i<chessboradSize*chessboradSize;i++){isling[i]=[];
for(var j=0;j<chessboradSize*chessboradSize;j++){isling[i][j]=-1;// 初始值为 0
}
}
function drawChessBoard(){// 绘画
for(var i=0;i<chessboradSize+1;i++){
context.strokeStyle='gray';// 可选区域
context.moveTo(15+i*30,15);// 垂直方向画 15 根线，相距 30px;
context.lineTo(15+i*30,15+30*chessboradSize);
context.stroke();
context.moveTo(15,15+i*30);// 程度方向画 15 根线，相距 30px; 棋盘为 14*14；context.lineTo(15+30*chessboradSize,15+i*30);
context.stroke();}
}
drawChessBoard();// 绘制棋盘
function getnei(a)// 取得街坊号 random
{var x=parseInt(a/chessboradSize);// 要准确成整数
var y=a%chessboradSize;
var mynei=new Array();// 贮存街坊
if(x-1>=0){mynei.push((x-1)*chessboradSize+y);}// 上节点
if(x+1<14){mynei.push((x+1)*chessboradSize+y);}// 下节点
if(y+1<14){mynei.push(x*chessboradSize+y+1);}// 有节点
if(y-1>=0){mynei.push(x*chessboradSize+y-1);}// 下节点
var ran=parseInt(Math.random() * mynei.length );
return mynei[ran];
}
function search(a)// 找到根节点
{if(tree[parseInt(a/chessboradSize)][a%chessboradSize]>0)// 阐明是子节点
{return search(tree[parseInt(a/chessboradSize)][a%chessboradSize]);// 不能压缩门路门路压缩
}
else
return a;
}
function value(a)// 找到树的大小
{if(tree[parseInt(a/chessboradSize)][a%chessboradSize]>0)// 阐明是子节点
{return tree[parseInt(a/chessboradSize)][a%chessboradSize]=value(tree[parseInt(a/chessboradSize)][a%chessboradSize]);// 不能门路压缩
}
else
return -tree[parseInt(a/chessboradSize)][a%chessboradSize];
}
function union(a,b)// 合并
{var a1=search(a);// a 根
var b1=search(b);// b 根
if(a1==b1){}
else
{if(tree[parseInt(a1/chessboradSize)][a1%chessboradSize]<tree[parseInt(b1/chessboradSize)][b1%chessboradSize])// 这个是正数()，为了简略缩小计算，不在调用 value 函数
{tree[parseInt(a1/chessboradSize)][a1%chessboradSize]+=tree[parseInt(b1/chessboradSize)][b1%chessboradSize];// 个数相加 留神是正数相加
tree[parseInt(b1/chessboradSize)][b1%chessboradSize]=a1; // b 树成为 a 树的子树，b 的根 b1 间接指向 a；}
else
{tree[parseInt(b1/chessboradSize)][b1%chessboradSize]+=tree[parseInt(a1/chessboradSize)][a1%chessboradSize];
tree[parseInt(a1/chessboradSize)][a1%chessboradSize]=b1;// a 所在树成为 b 所在树的子树
}
}
}
function drawline(a,b)// 划线，要判断是高低还是左右
{var x1=parseInt(a/chessboradSize);
var y1=a%chessboradSize;
var x2=parseInt(b/chessboradSize);
var y2=b%chessboradSize;
var x3=(x1+x2)/2;
var y3=(y1+y2)/2;
if(x1-x2==1||x1-x2==-1)// 左右方向的点 须要上下划线
{
context.strokeStyle = 'white';
context.clearRect(29+x3*30, y3*30+16,2,28);
}
else
{
context.strokeStyle = 'white';
context.clearRect(x3*30+16, 29+y3*30,28,2);
}
}
while(search(0)!=search(chessboradSize*chessboradSize-1))// 次要思路
{var num = parseInt(Math.random() * chessboradSize*chessboradSize );// 产生一个小于 196 的随机数
var neihbour=getnei(num);
if(search(num)==search(neihbour)){continue;}
else// 不在一个上
{isling[num][neihbour]=1;isling[neihbour][num]=1;
drawline(num,neihbour);// 划线
union(num,neihbour);
}
}
</script>
</html>
这样，离胜利又进了一步，实现成果：
方块挪动
这部分我采纳的办法不是 动静真的挪动(要害我不会哈哈)，而是一格一格的跳跃，也就是当走到下一个格子将以后格子的方块擦掉，在挪动的那个格子中再画一个方块，抉择方块是因为方块更不便擦除绘画计算，能够依据像素大小精准擦除。当然相熟 JavaScript 的能够弄个君子进去玩玩。
另外，在挪动中要留神 不能隔空穿墙、越界 。那么怎么判断呢？很好办，挪动前指标方格，咱们 判断其是否间接联通 ，留神是间接联通而不是联通(很可能绕一圈联通但不能间接越过来，所以这里 并查集不能压缩门路 哦)，如果间接不连通，那么不进行操作，否则进行方块挪动。
另外，事件的监听上下左右本人百度查一查就能够失去，增加按钮对一些事件监听，实现整个游戏这些不是最次要的。
为了丰盛游戏可玩性，将办法封装，能够设置关卡(只需扭转迷宫大小)，这样就能够实现通关了。
结语
在线尝试地址 http://biggsai.com/maze.html，代码能够到 githubhttps://github.com/javasmall/mazegame：上下载或到 bigsai 公众号回复： 迷宫 即可取得！下载我的项目之后批改图片和本人想说的话，放到本人服务器上，就能够给女神看了。
防止吃狗粮，动态图图片换了一下(排行榜性能被阉割了)：
笔者前端能力和算法能力无限，写的可能不是特地好，还请见谅！当然，笔者欢送和一起酷爱学习的人共同进步、学习！欢送关注笔者公众号：bigsai，欢送关注、点赞！蟹蟹！
