- 云服務(wù)器優(yōu)惠
- 阿里云優(yōu)惠券
- 騰訊云優(yōu)惠券
- 京東云優(yōu)惠券
- 站點(diǎn)信息
- 問(wèn)題反饋
- 郵箱：[email protected]
關(guān)注微信
?2016-2026 Matools All rights reserved,
粵ICP備17059708號(hào)
目錄
* 起因 <https://www.cnblogs.com/bigsai/p/11571715.html#起因>
* 分析 <https://www.cnblogs.com/bigsai/p/11571715.html#分析>
* 畫(huà)線(棋盤(pán)) <https://www.cnblogs.com/bigsai/p/11571715.html#畫(huà)線棋盤(pán)>
* 畫(huà)迷宮 <https://www.cnblogs.com/bigsai/p/11571715.html#畫(huà)迷宮>
* 方塊移動(dòng) <https://www.cnblogs.com/bigsai/p/11571715.html#方塊移動(dòng)>
* 結(jié)語(yǔ) <https://www.cnblogs.com/bigsai/p/11571715.html#結(jié)語(yǔ)>
@(文章目錄)
先看效果圖(在線電腦嘗試地址http://biggsai.com/maze.html <http://biggsai.com/maze.html>)：
起因
又到深夜了，我按照以往在公眾號(hào)寫(xiě)著數(shù)據(jù)結(jié)構(gòu)！這占用了我大量的時(shí)間！我的超越妹妹嚴(yán)重缺乏陪伴而 怨氣滿滿！
超越妹妹時(shí)常埋怨，認(rèn)為數(shù)據(jù)結(jié)構(gòu)這么抽象難懂的東西沒(méi)啥作用，常會(huì)問(wèn)道：天天寫(xiě)這玩意，有啥作用。而我答道：能干事情多了，比如寫(xiě)個(gè)小游戲啥的！
當(dāng)我碼完字準(zhǔn)備睡覺(jué)時(shí)：寫(xiě)不好別睡覺(jué)！
分析
如果用數(shù)據(jù)結(jié)構(gòu)與算法造出東西來(lái)呢？
* 什么東西簡(jiǎn)單容易呢？我百度一下，我靠，這個(gè)鳥(niǎo)游戲原來(lái)不好搞啊，得接觸一堆不熟悉的東西，搞不來(lái)搞不來(lái)。
有了(靈光一閃)，寫(xiě)個(gè)猜數(shù)字游戲，問(wèn)他加減乘除等于幾。
* 超越妹妹又不是小孩子，糊弄不過(guò)去。
經(jīng)過(guò)一番折騰，終于在半夜12點(diǎn)確定寫(xiě)迷宮小游戲了。大概弄清楚其中的幾個(gè)步驟。
大概是：
* 畫(huà)線—>畫(huà)迷宮(擦線)—>方塊移動(dòng)、移動(dòng)約束(不出界不穿墻)—>完成游戲。
畫(huà)線(棋盤(pán))
對(duì)于html+js(canvas)畫(huà)的東西，之前學(xué)過(guò)javaswing應(yīng)該有點(diǎn)映像。在html中有個(gè)canvas
的畫(huà)布，可以在上面畫(huà)一些東西和聲明一些監(jiān)聽(tīng)(鍵盤(pán)監(jiān)聽(tīng))。
對(duì)于迷宮來(lái)說(shuō)，那些線條是沒(méi)有屬性的，只有位置x,y
，你操作這個(gè)畫(huà)布時(shí)候，可能和我們習(xí)慣的面相對(duì)象思維不一樣。所以，在你設(shè)計(jì)的線或者點(diǎn)的時(shí)候，記得那個(gè)點(diǎn)、線在什么位置，在后續(xù)劃線還是擦線還是移動(dòng)的時(shí)候根據(jù)這個(gè)位置進(jìn)行操作。
<!DOCTYPE html> <html> <head> <title>MyHtml.html</title> </head> <body>
<canvas id="mycanvas" width="600px" height="600px"></canvas> </body> <script
type="text/javascript"> var aa=14; var chess =
document.getElementById("mycanvas"); var context = chess.getContext('2d'); //
var context2 = chess.getContext('2d'); // context.strokeStyle = 'yellow'; var
tree = [];//存放是否聯(lián)通 var isling=[];//判斷是否相連 for(var i=0;i<aa;i++){ tree[i]=[];
for(var j=0;j<aa;j++){ tree[i][j]=-1;//初始值為0 } } for(var i=0;i<aa*aa;i++){
isling[i]=[]; for(var j=0;j<aa*aa;j++){ isling[i][j]=-1;//初始值為0 } } function
drawChessBoard(){//繪畫(huà) for(var i=0;i<aa+1;i++){
context.strokeStyle='gray';//可選區(qū)域
context.moveTo(15+i*30,15);//垂直方向畫(huà)15根線，相距30px;
context.lineTo(15+i*30,15+30*aa); context.stroke();
context.moveTo(15,15+i*30);//水平方向畫(huà)15根線，相距30px;棋盤(pán)為14*14；
context.lineTo(15+30*aa,15+i*30); context.stroke(); } } drawChessBoard();//繪制棋盤(pán)
// var mymap=new Array(36); // for(var i=0;i<36;i++) // {mymap[i]=-1;}
</script> </html>
實(shí)現(xiàn)效果
畫(huà)迷宮
隨機(jī)迷宮怎么生成？怎么搞？一臉懵逼。
* 因?yàn)槲覀兿胍詫m，那么就需要這個(gè)迷宮出口和入口有連通路徑，你可能壓根不知道迷宮改怎么生成，用的什么算法。小聲BB：用并查集(不相交集合)
<https://blog.csdn.net/qq_40693171/article/details/100061983>。
迷宮和不相交集合有什么聯(lián)系呢？(規(guī)則)
* 之前筆者在前面數(shù)據(jù)結(jié)構(gòu)與算法系列中曾經(jīng)介紹過(guò)并查集(不相交集合
<https://blog.csdn.net/qq_40693171/article/details/100061983>)
，它的主要功能是森林的合并，不聯(lián)通的通過(guò)并查集能夠快速將兩個(gè)森林合并，并且能夠快速查詢兩個(gè)節(jié)點(diǎn)是否在同一個(gè)森林中！
而我們的隨機(jī)迷宮：在每個(gè)方格都不聯(lián)通的情況下，是一個(gè)棋盤(pán)方格，這也是它的初始狀態(tài)。而這個(gè)節(jié)點(diǎn)可以跟鄰居可能相連，也可能不相連。我們可以通過(guò)并查集實(shí)現(xiàn)。
具體思路為：(主要理解并查集)
* 1：定義好不想交集合的基本類和方法（search,union等）
2：數(shù)組初始化，每一個(gè)數(shù)組元素都是一個(gè)集合，值為-1
3：隨機(jī)查找一個(gè)格子（一維數(shù)據(jù)要轉(zhuǎn)換成二維，有點(diǎn)麻煩），在隨機(jī)找一面墻（也就是找這個(gè)格子的上下左右），還要判斷找的格子出沒(méi)出界。
具體在格子中找個(gè)隨機(jī)數(shù)m——>隨機(jī)數(shù)m在二維中的位置[m/長(zhǎng),m%長(zhǎng)]——>這個(gè)二維的上下左右隨機(jī)找一個(gè)位置p[m/長(zhǎng)+1,m%長(zhǎng)]或[m/長(zhǎng)-1,m%長(zhǎng)]
或[m/長(zhǎng),m%長(zhǎng)+1]或[m/長(zhǎng),m%長(zhǎng)-1]——>判斷是否越界
4：判斷兩個(gè)格子(一維數(shù)組編號(hào))是否在一個(gè)集合(并查集查找)。如果在，則重新找，如果不在，那么把墻挖去
5
：把墻挖去有點(diǎn)繁瑣，需要考慮奇偶判斷它那種墻(上下還是左右，還要考慮位置)，然后擦掉。（根據(jù)數(shù)組轉(zhuǎn)換成真實(shí)距離）。具體為找一個(gè)節(jié)點(diǎn)，根據(jù)位置關(guān)系找到一維數(shù)組的號(hào)位用并查集判斷是否在一個(gè)集合中。
6
：最終得到一個(gè)完整的迷宮。直到第一個(gè)(1,1)和(n,n)聯(lián)通停止。雖然采用隨機(jī)數(shù)找墻，但是效果并不是特別差。其中要搞清一維二維數(shù)組的關(guān)系。一維是真實(shí)數(shù)據(jù)，并查集操作。二維是位置。要搞懂轉(zhuǎn)化！
注意：避免混淆，搞清數(shù)組的地址和邏輯矩陣位置。數(shù)組從0開(kāi)始的，邏輯上你自己判斷。別搞混淆！
主要邏輯為：
while(search(0)!=search(aa*aa-1))//主要思路 { var num = parseInt(Math.random() *
aa*aa );//產(chǎn)生一個(gè)小于196的隨機(jī)數(shù) var neihbour=getnei(num);
if(search(num)==search(neihbour)){continue;} else//不在一個(gè)上 {
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 mymap=new Array(36); // for(var
i=0;i<36;i++) // {mymap[i]=-1;} function getnei(a)//獲得鄰居號(hào) random { var
x=parseInt(a/aa);//要精確成整數(shù) var y=a%aa; var mynei=new Array();//儲(chǔ)存鄰居
if(x-1>=0){mynei.push((x-1)*aa+y);}//上節(jié)點(diǎn)
if(x+1<14){mynei.push((x+1)*aa+y);}//下節(jié)點(diǎn) if(y+1<14){mynei.push(x*aa+y+1);}//有節(jié)點(diǎn)
if(y-1>=0){mynei.push(x*aa+y-1);}//下節(jié)點(diǎn) var ran=parseInt(Math.random() *
mynei.length ); return mynei[ran]; } function search(a)//找到根節(jié)點(diǎn) {
if(tree[parseInt(a/aa)][a%aa]>0)//說(shuō)明是子節(jié)點(diǎn) { return
search(tree[parseInt(a/aa)][a%aa]);//不能壓縮路徑路徑壓縮 } else return a; } function
value(a)//找到樹(shù)的大小 { if(tree[parseInt(a/aa)][a%aa]>0)//說(shuō)明是子節(jié)點(diǎn) { return
tree[parseInt(a/aa)][a%aa]=value(tree[parseInt(a/aa)][a%aa]);//不能路徑壓縮 } else
return -tree[parseInt(a/aa)][a%aa]; } function union(a,b)//合并 { var
a1=search(a);//a根 var b1=search(b);//b根 if(a1==b1){} else {
if(tree[parseInt(a1/aa)][a1%aa]<tree[parseInt(b1/aa)][b1%aa])//這個(gè)是負(fù)數(shù)()，為了簡(jiǎn)單減少計(jì)算，不在調(diào)用value函數(shù)
{ tree[parseInt(a1/aa)][a1%aa]+=tree[parseInt(b1/aa)][b1%aa];//個(gè)數(shù)相加 注意是負(fù)數(shù)相加
tree[parseInt(b1/aa)][b1%aa]=a1; //b樹(shù)成為a樹(shù)的子樹(shù)，b的根b1直接指向a； } else {
tree[parseInt(b1/aa)][b1%aa]+=tree[parseInt(a1/aa)][a1%aa];
tree[parseInt(a1/aa)][a1%aa]=b1;//a所在樹(shù)成為b所在樹(shù)的子樹(shù) } } } function
drawline(a,b)//劃線，要判斷是上下還是左右 { var x1=parseInt(a/aa); var y1=a%aa; var
x2=parseInt(b/aa); var y2=b%aa; var x3=(x1+x2)/2; var y3=(y1+y2)/2;
if(x1-x2==1||x1-x2==-1)//左右方向的點(diǎn) 需要上下劃線 { //alert(x1); // context.beginPath();
context.strokeStyle = 'white'; // context.moveTo(30+x3*30,y3*30+15);// //
context.lineTo(30+x3*30,y3*30+45); context.clearRect(29+x3*30, y3*30+16,2,28);
// context.stroke(); } else { // context.beginPath(); context.strokeStyle =
'white'; // context.moveTo(x3*30+15,30+y3*30);// //
context.lineTo(45+x3*30,30+y3*30); context.clearRect(x3*30+16, 29+y3*30,28,2);
// context.stroke(); } } while(search(0)!=search(aa*aa-1))//主要思路 { var num =
parseInt(Math.random() * aa*aa );//產(chǎn)生一個(gè)小于196的隨機(jī)數(shù) var neihbour=getnei(num);
if(search(num)==search(neihbour)){continue;} else//不在一個(gè)上 {
isling[num][neihbour]=1;isling[neihbour][num]=1; drawline(num,neihbour);//劃線
union(num,neihbour); } } </script> </html>
實(shí)現(xiàn)效果：
方塊移動(dòng)
這部分我采用的方法不是動(dòng)態(tài)真的移動(dòng)
，而是一格一格的跳躍。也就是當(dāng)走到下一個(gè)格子將當(dāng)前格子的方塊擦掉，在移動(dòng)的那個(gè)格子中再畫(huà)一個(gè)方塊。選擇方塊是因?yàn)榉綁K更方便擦除，可以根據(jù)像素大小精準(zhǔn)擦除。
另外，再移動(dòng)中要注意不能穿墻、越界。那么怎么判斷呢？很好辦，我們?cè)偾懊鏁?huì)判斷兩個(gè)格子是否聯(lián)通，如果不連通我們將把這個(gè)墻拆開(kāi)。再拆的時(shí)候把這個(gè)墻
的時(shí)候記錄這兩點(diǎn)拆墻可走即可(數(shù)組)
另外，事件的監(jiān)聽(tīng)上下左右查一查就可以得到，添加按鈕對(duì)一些事件監(jiān)聽(tīng)，這些不是最主要的。
為了豐富游戲可玩性，將方法封裝，可以設(shè)置關(guān)卡(只需改變迷宮大小)。這樣就可以實(shí)現(xiàn)通關(guān)了。另外，如果寫(xiě)成動(dòng)態(tài)存庫(kù)那就更好了。
結(jié)語(yǔ)
在線嘗試地址 <http://biggsai.com/maze.html>，代碼直接查看網(wǎng)頁(yè)源代碼即可！
筆者前端能力和算法能力有限，寫(xiě)的可能不是特別好，還請(qǐng)見(jiàn)諒！當(dāng)然，筆者歡迎和一起熱愛(ài)學(xué)習(xí)的人共同進(jìn)步、學(xué)習(xí)！歡迎關(guān)注筆者公眾號(hào)：bigsai
，如果感覺(jué)不錯(cuò)，歡迎關(guān)注、點(diǎn)贊！蟹蟹！
熱門(mén)工具 換一換