引言：
上午女兒跟我去逛超市，在文具區看到一本書，總共有10幅圖都是小迷宮游戲，圖什么的都挺漂亮，就是有點貴應該是紙比較好，要30多塊錢，我就覺得劃不來（典型的鐵公雞），我就跟女兒說家里有，買了其他東西就回來了，然后網上查了一下，主要用到的是一個演算法，于是吃完午飯就開始寫了，這就學馬老師來一波回首掏！
有人可能會說你這人真摳門，這點錢都舍不得掏，
我會說：這是錢的問題嗎？這是專業，我們程式員的錢有那么好賺嗎?我待會就跟我老婆要30塊錢，說我買了個迷宮游戲書，我們程式員的錢不就是敲代碼來的嗎，變現有問題？
效果
重繪就可以換一個通道，不比書香，可以一直玩，一直玩一直爽，
演算法（網上抄的)
1.將起點作為當前迷宮單元并標記為已訪問
2.當還存在未標記的迷宮單元，進行回圈
1).如果當前迷宮單元有未被訪問過的的相鄰的迷宮單元
(1).隨機選擇一個未訪問的相鄰迷宮單元
(2).將當前迷宮單元入堆疊
(3).移除當前迷宮單元與相鄰迷宮單元的墻
(4).標記相鄰迷宮單元并用它作為當前迷宮單元
2).如果當前迷宮單元不存在未訪問的相鄰迷宮單元，并且堆疊不空
(1).堆疊頂的迷宮單元出堆疊
(2).令其成為當前迷宮單元
這個演算法叫做“深度優先”，簡單來說，就是從起點開始走，尋找它的上下左右4個鄰居，然后隨機一個走，到走不通的時候就回傳上一步繼續走，直到全部單元都走完，
實作思路（這個自己寫的）
1.創建格子單元物件，
2.通過演算法將這些格子打通，繪制出迷宮的形狀，
3.繪制入口與終點的格子，
4.添加鍵盤的上、下、左、右移動事件，寫好對應的函式，到達終點提示勝利，
相關圖示圖
1.每個單元的墻，分為上墻、右墻、下墻、左墻，把這些墻用長度為4的陣串列示，元素的值為true則表示墻存在，否則墻不存在，代碼里陣列的下標方式來確定墻是否存在，
2.單元是根據行列來創建的，會用到雙回圈，類似表格，比如第二行用 i 來表示的話就是 1，第3列用 j 來表示就是2，那第二行第3列的元素組合起來就是（1,2）
3.那同理它的上鄰居就是（0,2），右鄰居（1,3），下鄰居（2,2），左鄰居（1,1），也就是上下鄰居是 i 減加1，左右鄰居是 j 減加1，
4.正方形4個點的坐標分別為(x1,y1)(x2,y2)(x3,y3)(x4,y4)，計算坐標的公式為：
//左上角坐標
x1=j*w;
y1=i*w;
//右上角坐標
x2=(j+1)*w;
y2=i*w;
//右下角坐標
x3=(j+1)*w;
y3=(i+1)*w;
//左下角坐標
x4=j*w;
y4=(i+1)*w;計算坐標，假如每個正方形的寬高都是40，那么（1,2）這個單元的坐標如下圖：
5.墻的處理，之前說到墻是以一個4個元素的陣列來表示的，比如陣列為：[true,true,true,true]，則圖為：
如果陣列為[false,true,true,true]，則圖為：
6.如果要聯通右邊的鄰居要怎么做呢？當前單元去除右墻，右邊單元去除左墻，這樣就聯通了，
去除后就這樣，以此類推
代碼及講解
新增建構式
此建構式不是直接利用Rect來繪制方形的，而是自己以繪制4條直線的方式來繪制的，既方形的上、右、下、左4條直線，
1.計算坐標，這個上面已經提過，
2.根據墻陣列的值來確定是否繪制這條直線，[true,true,true,true]就繪制完整的方形，[false,true,true,true]的話，上邊就會缺失，
代碼
//用4條直線畫方形的建構式
function LineRect(o){
this.x=0,//x坐標
this.y=0,//y坐標
this.init(o);
this.axis(this.i,this.j);
}
LineRect.prototype.init=function(o){
for(var key in o){
this[key]=o[key];
}
//上右下左4面墻 true就表示要繪制
this.walls=[true,true,true,true];
}
//根據i,j計算出坐標
LineRect.prototype.axis=function(i,j){
var w = this.maze.dis;
//i代表行 j代表列
//左上角坐標
this.x1=j*w;
this.y1=i*w;
//右上角坐標
this.x2=(j+1)*w;
this.y2=i*w;
//右下角坐標
this.x3=(j+1)*w;
this.y3=(i+1)*w;
//左下角坐標
this.x4=j*w;
this.y4=(i+1)*w;
}
//繪制函式
LineRect.prototype.render=function(context){
this.ctx=context;
innerRender(this);
function innerRender(obj){
var ctx=obj.ctx;
ctx.save()
ctx.beginPath();
ctx.translate(obj.x,obj.y);
if(obj.lineWidth){
ctx.lineWidth=obj.lineWidth;
}
//判斷上、右、下、左 的墻，true的話墻就會有，否則墻就沒有
var top = obj.walls[0];
var right = obj.walls[1];
var bottom = obj.walls[2];
var left = obj.walls[3];
if(top){
ctx.moveTo(obj.x1,obj.y1);
ctx.lineTo(obj.x2,obj.y2);
}
if(right){
ctx.moveTo(obj.x2,obj.y2);
ctx.lineTo(obj.x3,obj.y3);
}
if(bottom){
ctx.moveTo(obj.x3,obj.y3);
ctx.lineTo(obj.x4,obj.y4);
}
if(left){
ctx.moveTo(obj.x4,obj.y4);
ctx.lineTo(obj.x1,obj.y1);
}
obj.strokeStyle?(ctx.strokeStyle=obj.strokeStyle):null;
ctx.stroke();
ctx.restore();
}
return this;
}繪制
Maze.prototype.drawGrid=function(){
this.rows = Math.floor(this.h/this.dis);
this.cols = Math.floor(this.w/this.dis);
//根據行數、列數來創建格子
for(var i=0;i<this.rows;i++){
for(var j=0;j<this.cols;j++){
var cell = this.buildCell(i,j);
this.renderArr.push(cell);
}
}
}
//創建格子
Maze.prototype.buildCell=function(i,j){
var param={i:i,j:j,lineWidth:1,maze:this};
//創建格子物件
var cell = new LineRect(param);
return cell;
}
根據演算法打通墻
給每個單元格物件都增加鄰居查找方法
//查找當前單元是否有未被訪問的鄰居單元
LineRect.prototype.findNeighbors=function(){
//鄰居分為上下左右
var maze = this.maze ;
this.arr = maze.renderArr;
var res=[];//回傳的陣列
var top = this.getNeighbor('0');
var right = this.getNeighbor('1');
var bottom = this.getNeighbor('2');
var left = this.getNeighbor('3');
if(top){
res.push(top);
}
if(right){
res.push(right);
}
if(bottom){
res.push(bottom);
}
if(left){
res.push(left);
}
return res;//回傳鄰居陣列
}
//查找鄰居
LineRect.prototype.getNeighbor=function(type,lost_visited){
var key,neighbor;
if(type=='0'){
key = this.assemKey(this.i-1,this.j);
}else if(type=='1'){
key = this.assemKey(this.i,this.j+1);
}else if(type=='2'){
key = this.assemKey(this.i+1,this.j);
}else if(type=='3'){
key = this.assemKey(this.i,this.j-1);
}
if(key){
neighbor = this.arr[key];//首先找到這個鄰居
if(neighbor.visited && !lost_visited){//判斷是否被訪問，如果被訪問了回傳undefined lost_visited表示是否忽略訪問的情況
neighbor = undefined;
}
}
return neighbor;
}
//根據i,j計算陣列單元在陣列中的下標值
LineRect.prototype.assemKey=function(i,j){
if(i<0 || j<0 || i>=this.maze.rows || j>=this.maze.cols){//超出邊界了
return undefined;
}
return i*this.maze.cols+j;//計算出i,j位置單元在陣列中的下標
}計算
跟著演算法來寫的代碼，唯一要注意的是我設定了一個值unVisitedCount，初始值為所有單元的數量，每當一個單元被標記為已訪問后，這個值就遞減1，當值為0后就終止回圈，結束演算法，
Maze.prototype.computed=function(){
/*
1.將起點作為當前迷宮單元并標記為已訪問
2.當還存在未標記的迷宮單元，進行回圈
1).如果當前迷宮單元有未被訪問過的的相鄰的迷宮單元
(1).隨機選擇一個未訪問的相鄰迷宮單元
(2).將當前迷宮單元入堆疊
(3).移除當前迷宮單元與相鄰迷宮單元的墻
(4).標記相鄰迷宮單元并用它作為當前迷宮單元
2).如果當前迷宮單元不存在未訪問的相鄰迷宮單元，并且堆疊不空
(1).堆疊頂的迷宮單元出堆疊
(2).令其成為當前迷宮單元
*/
var stack = this.stack ; //堆疊
var arr = this.renderArr;
var current = arr[0];//取第一個為當前單元
this.pathArr.push(current);
current.visited=true;//標記為已訪問
var unVisitedCount=arr.length-1;//因為第一個已經設定為訪問了
var neighbors ;
while(unVisitedCount>0){
neighbors = current.findNeighbors();//查找鄰居集合(未被訪問的)
if(neighbors.length>0){//如果當前迷宮單元有未被訪問過的的相鄰的迷宮單元
//隨機選擇一個未訪問的相鄰迷宮單元
var index = _.getRandom(0,neighbors.length);
var next = neighbors[index];
//將當前迷宮單元入堆疊
stack.push(current);
//移除當前迷宮單元與相鄰迷宮單元的墻
this.removeWall(current,next);
//標記相鄰迷宮單元并用它作為當前迷宮單元
next.visited=true;
//標記一個為訪問，則計數器遞減1
unVisitedCount--;//遞減
current = next;
}else if(stack.length>0){//如果當前迷宮單元不存在未訪問的相鄰迷宮單元，并且堆疊不空
/*
1.堆疊頂的迷宮單元出堆疊
2.令其成為當前迷宮單元
*/
var cell = stack.pop();
current = cell;
}
//推入路線陣列
this.pathArr.push(current);
}
}移除墻
//移除當前迷宮單元與相鄰迷宮單元的墻
Maze.prototype.removeWall=function(a,b){
if(a.i==b.i){//橫向鄰居
if(a.j>b.j){//匹配到的是左邊鄰居
//左邊鄰居的話，要移除自己的左墻和鄰居的右墻
a.walls[3]=false;
b.walls[1]=false;
}else{//匹配到的是右邊鄰居
//右邊鄰居的話，要移除自己的右墻和鄰居的左墻
a.walls[1]=false;
b.walls[3]=false;
}
}else if(a.j==b.j){//縱向鄰居
if(a.i>b.i){//匹配到的是上邊鄰居
//上邊鄰居的話，要移除自己的上墻和鄰居的下墻
a.walls[0]=false;
b.walls[2]=false;
}else{//匹配到的是下邊鄰居
//下邊鄰居的話，要移除自己的下墻和鄰居的上墻
a.walls[2]=false;
b.walls[0]=false;
}
}
}
繪制入口出口
//創建起點和終點格子
Maze.prototype.drawRunCell=function(i,j){
var end = new _.Rect({
x:(this.cols-1)*this.dis+this.dis2,
y:(this.rows-1)*this.dis+this.dis2,
width:this.dis-2*this.dis2,
height:this.dis-2*this.dis2,
fill:true,
fillStyle:'red'
});
end.i=this.rows-1,end.j=this.cols-1;//設定i,j值，判斷是否終點
this.renderArr2.push(end);
var start = new _.Rect({
x:0+this.dis2,
y:0+this.dis2,
width:this.dis-2*this.dis2,
height:this.dis-2*this.dis2,
fill:true,
fillStyle:'blue'
});
start.i=0,start.j=0;//設定i,j值，控制移動
this.renderArr2.push(start);
}
加入移動監聽
//按鍵的控制
Maze.prototype.control=function(){
var that=this;
global.addEventListener('keydown',function(e){
console.log(that.endFlag)
if(that.endFlag) return ;
var dir;
switch (e.keyCode){
case 87://w
case 38://上
dir=0;//上移動
break;
case 83://s
case 40://下
dir=2;//下移動
break;
case 65://a
case 37://左
dir=3;//左移動
break;
case 68://d
case 39://右
dir=1;//右移動
break;
}
that.move(dir);
//測驗用，記得洗掉
that.render();
});
}加入移動函式
//移動
Maze.prototype.move=function(dir){
var cur = this.renderArr2[1];//當前移動的方塊
var key = this.assemKey(cur);//根據移動方塊的i,j計算出key
var cell = this.renderArr[key];//得到移動方塊對應的單元
var wall = cell.walls[dir];//得到對應的那面墻
if(!wall){//表示是沒有墻能移動
var neighbor = cell.getNeighbor(dir,1);
if(!neighbor){
return ;
}
cur.x=neighbor.x1+this.dis2;
cur.y=neighbor.y1+this.dis2;
cur.i=neighbor.i;
cur.j=neighbor.j;
}
var end = this.renderArr2[0];
if(cur.i==end.i && cur.j==end.j ){
this.endFlag=true;
console.log('完成');
this.endShow();
}
}
Maze.prototype.assemKey=function(e){
return e.i*this.cols+e.j;//計算出i,j位置單元在陣列中的下標
}加入勝利圖
//展示結束的圖片（勝利）
Maze.prototype.endShow=function(){
var image,img,sx=0,sy=0,sWidth=225,sHeight=108,dx=this.w/2-110,dy=this.h/2-100,dWidth=225,dHeight=108;
image = this.imgObj['suc'];
img = new _.ImageDraw({image:image,sx:sx,sy:sy,sWidth:sWidth,sHeight:sHeight, dx:dx, dy:dy ,dWidth:dWidth,dHeight:dHeight});
this.renderArr2.push(img);
this.render();
}
寫出來也花了不少腦細胞，能看到這里的都是大佬，我去找老婆提現去了，
歡迎各位大佬 點贊+評論+關注，謝謝！
原始碼下載
方式1：少量積分，下載代碼
方式2：關注下方公眾號，回復 130 下載代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279894.html
標籤：其他
上一篇：Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2) A B C 題解
下一篇：關于汽車電子測驗工程師