想免費學編程，就請點擊上面的藍字：跟我學Scratch編程，關注CC哥。

翻一下CC哥做的教學帖子，應該是自動走迷宮這個帖子最受歡迎。不過這個游戲里的迷宮是CC哥在網上下的。當時就想應該自己做個自動生成迷宮的程序，只是一直沒動手，這星期終于把這個程序給做出來了，分享給大家。下一講我們再做如何用新的算法自動走迷宮。

是不是很沒有動畫效果，CC哥特意在做的時候把刷屏給關了，所以看著就是秒成地圖了。

紅色的方塊表示起點。終點我們可以假設在右下角。

自動畫迷宮最關鍵的就是算法，CC哥用的是Prim算法做的迷宮算法，這種算法畫出來的迷宮更適合游戲使用。

在這個游戲里我們把綠色當成路，把淺紅色當成墻。也就是一個角色的兩種造型。我還是喜歡用克隆做，而不是用畫圖的形式去做。其實區別不大，因為所有的計算都是通過算法完成的，角色之間沒什么互動，我們可以根據算法計算出來的迷宮結果，用克隆去畫這個迷宮，也可以用圖章去畫。每個人習慣不同。

讓我們看看程序怎么做的吧：

生成一個只有墻的迷宮

這個簡單，代碼也不用講了，大家把位置和坐標只要確定好，畫得漂亮一些就行。在克隆的時候要注意，我引入了一個編號的私有變量，也就是要標明每一個克隆體的編號。確保后面的行動能找到對應的克隆體。我之所以用自定義命令去生成方陣，主要的目的還是不想有刷屏效果，這樣方陣可以秒成。這個技巧前面的帖子里反復都講過，就不重復了。

另外我還引入了一個列表，標明每一個克隆體的狀態，是墻還是路，列表的順序號對應的就是克隆體的編號，列表的內容對應的是墻還是路，墻為零，路為1。

全部都是墻，所以都是零。

迷宮生成算法

下面就是本次講座的關鍵部分，就是迷宮的算法。CC哥另外導入一個角色，用來做算法的程序，沒有放到迷宮方塊的角色里。

算法概述：

1.建立兩個數組，一個是用于存儲地圖的二維數組α，另一個是用于存儲待處理的墻的數組β。

2.將α的所有方格全部初始化為墻。

????? 3.選定起點，并將該位置的墻變為路，將其四周的四塊置入β數組中（出界的直接篩掉，就不說了）。

4.當β數組不為空時，循環以下步驟

1）從β數組中隨機選擇一塊，暫且叫他A。

2）遍歷該方塊四周，并選定其中的某一塊為路的方塊，暫且叫他B。

3）判斷相對于A，在B的對側的方塊C是否為墻（假如B在A左側，就判定A右邊的方塊；B在A上方，就判定A下方的方塊；以此類推……），若為墻，則：

????????①將A、C均置為路。

????????②將C周圍是墻的所有方塊，均置入β數組中。

?4）將A從β數組中去掉。

這段算法就是迷宮的生成算法，CC哥從網上找的，下面我們看看Scratch怎么做：

1和2步剛才基本上已經做了，我們設置了一個列表，用來存儲迷宮地圖上所有的方塊，另外我也把這個列表里的每一個變量設置成零，代表全部初始化成墻。同時另外再建臨時待處理的墻的列表。

所以關鍵是第三步和第四步：

第三步：選定起點，起點我們定為第一個方塊，然后把周邊的方塊放到待處理的墻列表中。

這里面有一個自定義的命令，“返回周邊情況”，這個命令是用來檢測指定的方塊周邊的路和墻的狀況。會將周邊的墻和路分別放到兩個臨時的列表中：“周邊墻”和“周邊路”這兩個列表。

我們把第一個方塊進行檢測，然后把返回都周邊墻的數據填入到待處理墻列表中。

（這個返回周邊情況的代碼有點長，主要是要測試上下左右的四個方塊是路還是墻，同時還要對方塊的位置進行判斷，處理好當方塊位于邊界的情況。代碼并不復雜，就是找到四邊的方塊的編號，然后去全路徑狀態列表里讀取這個方塊是墻還是路，分別放到不同的列表里。）

第四步：

接下來就是做算法中的第四步，也是關鍵的一步：

為了跟算法描述對應，我也用了ABC三個變量來對應算法描述，方便大家閱讀代碼。

1：先從待處理的墻列表中隨機抽取一個數據，也就是隨機選一個方塊A。

2：對這個方塊的四周進行檢測，返回這個方塊周邊為路的列表。

3：從方塊A周邊路的列表中隨機選擇一個路的方塊定義為B。

4：然后根據算法描述，找到C的位置，判斷C是否為墻，如果為墻，就把他四周的所有的墻都放到待處理的墻列表中去，同時把A和C都設置成路。如果不是就什么也不做。

為了找C的位置，我單獨做了一條命令，代碼有點長，其實就是判斷A和B的位置的特殊情況，比如B在A的左邊，而又A在最后面一列，那就沒有C了。

（有點長就不全部截屏了）

找到C的位置后，我又做了一條自定義的命令來處理剩下的操作。

5：處理完了C，然后就把A從待處理列表中刪除掉。

重復這5步過程，直到待處理的列表中沒有數據，那么迷宮就生成完畢了。

通過迷宮算法，最后的全路徑狀態列表中就有了整個迷宮的數據，每一個方塊應該是路還是墻都清清楚楚。隨后，我們只需要發一條消息刷新一下克隆體的狀態，讓克隆體的造型跟我們的迷宮列表一一對應就好了。

（當然，這部分代碼是在迷宮方塊的角色里，用消息來控制克隆體真是一個方便的方法。）

今天的程序相對來說不復雜，關鍵是讓大家知道有這么一套自動生成迷宮的算法，用這個方法可以自由的生成各種難度的迷宮，是不是很有意思。

輸入標題

上次做自動走迷宮其實沒什么算法，就是一直沿著左邊走的瞎子走法，CC哥一直想做睜著眼睛的走法，也就是用算法來盡量很快的走出迷宮。那么下一講CC哥就跟大家試試用遞歸回溯的方法來快速睜著眼睛走出迷宮。

聲明：本文章由網友投稿作為教育分享用途，如有侵權原作者可通過郵件及時和我們聯系刪除