520,花一夜給女神寫走迷宮遊戲

語言: CN / TW / HK

以前雖然寫過走迷宮,很多人反映沒找到代碼不會部署,沒看明白原理,這次把更詳細寫出優化並將代碼放到github,趁着520可以自己放一些圖片獻給女神!

起因

先看效果圖(文末有動態圖)(在線電腦嘗試地址http://biggsai.com/maze.html):

項目github地址:https://github.com/javasmall/mazegame

image-20210520104455552

作為程序猿,常常因為身務繁忙,經常忙於coding很少閒暇來顧及女朋友,也常被吐槽為渣男。

image-20210519214838723

但是,渣着渣着,卻發現520到了。卧槽,520?!

image-20210519220610165

我們常常後悔自己衝動時候説過的話,我準備個毛線,啥都沒準備,但好面子的我也不可能隨隨便便欺騙人家女孩子(雖然已經騙了😭),

習慣性打開淘寶,逛着看看有沒有啥合適的,一想今天已經19號了,卧槽要涼了難道?

image-20210519223732133

一想還有美團補救一下可以送的到,打開美團發現都是吃喝玩,完蛋,真的要涼了。

5038382FEBB0BA27588AA6947C122B38

深夜,我在懺悔自己説過的大話,沒本事不能瞎説啊,一晚上啥也幹不了啥哇。

等等,還有一晚上耶!

此時我突然眼前一亮,對於程序猿,一晚上也能製造屬於他的浪漫!

翻開各種搜索引擎、博客搜素一番:程序員520表白神器 代碼 果然不出我所料!有東西,哈哈哈ctrl+c,ctrl+v我可太會了,浪漫要來了!

找了幾個代碼,發現哇塞好牛哇,還能跑起來,但是發現好多雷同我也找不到原作者是誰,但我心中非常崇拜作者的才華(救命之恩)。

image-20210519234837689

這時我的頭腦又浮現她時長對我説的一句話:"一點都不上心"!這些可能確實都已經很老套和小兒科了,不行,我要以我自己的方式來!我要有點我自己的特色。

我琢磨着怎麼用熟悉的數據結構與算法搞個有趣的東西。

追憶着我知道的數據結構與算法:鏈表、隊列、棧、圖、dfs、bfs、並查集、Dijkstra、Prime……

以前隱隱約約好像記得有人用Java Swing配合並查集算法畫迷宮,我是否可以寫一個走迷宮的小遊戲呢?但我搜了一下並未發現有HTML、JavaScript版本的,但Swing那玩意除了特定場景基本沒人用我要整一個不一樣的,雖然JavaScript和HTML我不太熟,但我應該可以,加油💪!

image-20210520004304691

分析

我需要從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>

實現效果 image-20210520085614456

畫迷宮

隨機迷宮怎麼生成?怎麼搞?又陷入一臉懵逼。

因為我們想要迷宮,那麼就需要這個迷宮出口和入口有連通路徑,不研究的話很難知道用什麼算法生成這個迷宮。這時耳角傳來熟悉的聲音:並查集(不相交集合)

迷宮和不相交集合有什麼聯繫呢?(規則)

之前筆者在前面數據結構與算法系列中曾經介紹過並查集(不相交集合),它的主要功能是森林的合併、查找:不聯通的通過並查集能夠快速將兩個森林合併,並且能夠快速查詢兩個節點是否在同一個森林(集合)中!

而隨機迷宮生成正也利用了這個思想:在每個方格都不聯通的情況下,是一個棋盤方格,每個迷宮格子相對獨立,這是它的初始狀態;後面生成可能需要若干相鄰節點進行聯通(合併為一個集合),且這個節點可以跟鄰居可能相連,也可能不相連。我們可以通過並查集實現其底層數據結構的支撐。

在這裏面,我們把每個格子當成一個個集合元素,而每個集合與周圍的牆則是證明其是否直接聯通,我們就是要通過聯通一部分方格(擦掉部分牆)實現整個隨機迷宮。

具體思路為:(主要理解並查集)

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>

這樣,離勝利又進了一步,實現效果:

image-20210520094600087

方塊移動

這部分我採用的方法不是動態真的移動(關鍵我不會哈哈),而是一格一格的跳躍,也就是當走到下一個格子將當前格子的方塊擦掉,在移動的那個格子中再畫一個方塊,選擇方塊是因為方塊更方便擦除繪畫計算,可以根據像素大小精準擦除。當然熟悉JavaScript的可以弄個小人進去玩玩。

另外,在移動中要注意不能隔空穿牆、越界。那麼怎麼判斷呢?很好辦,移動前目標方格,我們判斷其是否直接聯通,注意是直接聯通而不是聯通(很可能繞一圈聯通但不能直接越過去,所以這裏並查集不能壓縮路徑哦),如果直接不連通,那麼不進行操作,否則進行方塊移動。

另外,事件的監聽上下左右自己百度查一查就可以得到,添加按鈕對一些事件監聽,完成整個遊戲這些不是最主要的。

為了豐富遊戲可玩性,將方法封裝,可以設置關卡(只需改變迷宮大小),這樣就可以實現通關了。

結語

在線嘗試地址 http://biggsai.com/maze.html,代碼可以到githubhttps://github.com/javasmall/mazegame:上下載或到bigsai公眾號回覆: ** 迷宮** 即可獲得! 下載項目之後修改圖片和自己想説的話,放到自己服務器上,就可以給女神看了。

在這裏插入圖片描述

避免吃狗糧,動態圖圖片換了一下(排行榜功能被閹割了):

在這裏插入圖片描述

筆者前端能力和算法能力有限,寫的可能不是特別好,還請見諒!當然,筆者歡迎和一起熱愛學習的人共同進步、學習!歡迎關注筆者公眾號:bigsai,歡迎關注、點贊!蟹蟹!