基于Scratch3.0實現迷宮生成與尋路程序

陳靜

摘要：迷宮本質上是一個關于圖的遍歷算法的應用問題，即在給定的一張合理的迷宮地圖上，找出正確的道路，走出迷宮。本文首先介紹生成隨機迷宮的常見算法，其次介紹自動走迷宮的常見算法，最后介紹使用Scratch編程語言實現迷宮自動生成與走迷宮的核心程序。

關鍵詞：Scratch;迷宮;算法

中圖分類號：G642 文獻標識碼：A 文章編號：1007-9416（2020）09-0096-03

0 引言

迷宮可看做是一組連通圖。對于生成迷宮，首先初始化所有的點都為墻，接下來需要做的就是在不重復訪問的前提下遍歷整個圖中的所有點，在遍歷圖的過程中將相鄰（指的是當前點的上下左右的鄰接點）的兩個點間的墻隨機打通，也就是將當前點和鄰接點都設置為路。生成迷宮的常見算法有：普利姆算法（Prim），深度優先算法（DFS），克魯斯卡爾算法（Kruskal），廣度優先算法（BFS）。這里以Prim和DFS為主介紹自動生成迷宮的步驟。對于走迷宮，最簡單的思路就是依據圖的搜索遍歷算法對生成的迷宮地圖進行遍歷，尋找一條從起點到終點全是“路”的路線，常見的走迷宮算法有：左手法則、DFS、BFS。

1 生成隨機迷宮

1.1 Prim算法

Prim算法本質是最小生成樹，具體用Prim算法生成迷宮的步驟是：（1）初始化迷宮地圖。即將地圖中所有的點都設為墻;（2）任意選擇迷宮地圖中的一個點作為起點，將該點設置為路，以該點開始進行遍歷，打通墻壁;（3）將起點周圍（上下左右）是墻的點加入待處理墻隊列中;（4）當待處理墻隊列不為空時，進行循環，任選待處理墻隊列中的一個點，將其設置為當前點;（5）判斷當前點是否可以設置為路（依據是當前點的上下左右四個位置是否只有一個位置是路，也就是要保證迷宮路徑沒有環路且任意兩條路徑之間不交叉）;（6）若當前點可以設置為路，首先將當前點設置為路，即打通墻壁，然后將當前點周圍所有是墻的點加入到待處理墻隊列中，接著從待處理墻隊列中刪除與當前點相等的點，若無法設置為路，直接從待處理墻隊列中刪除與當前點相等的點;（7）執行步驟（4），直至待處理墻隊列為空。

1.2 DFS算法

DFS算法是一種“不撞南墻不回頭”的算法。DFS算法的核心思路可簡單概括為遞歸下去、回溯上來。顧名思義，遞歸下去是指以深度為基準，先一條路走到底，直至到達目標。若沒有到達目標并且無路可走，那么返回到上一步的位置，走其他的路，這就是回溯上來。DFS算法采用遞歸回溯的方式，用到了數據結構棧，先進后出。使用DFS算法生成迷宮的具體步驟是：（1）首先初始化建立一個迷宮，此時要求所有的迷宮單元都是墻且是未訪問狀態;（2）隨機選擇一個迷宮單元作為起點，加入棧并標記為已訪問;（3）當棧非空時，從棧頂取出一個迷宮單元（不用出棧）賦給當前迷宮單元，進行循環，循環的內容為：如果當前迷宮單元有未被訪問過的相鄰迷宮單元（上下左右），隨機選擇一個未訪問的相鄰迷宮單元，連通當前迷宮單元與相鄰迷宮單元，標記相鄰迷宮單元為已訪問，并將其加入棧;若當前迷宮單元沒有未訪問的相鄰迷宮單元，則棧頂的迷宮單元出棧;執行步驟（3），直至棧為空。

2 自動走迷宮

2.1 左手法則

左手法則是最簡單、最易想到的走迷宮方法，該方法符合人的日常思維，對應的還有右手法則。都是針對有墻壁的迷宮，沿著墻壁走，最終都能走出去。左手（右手）法則只適用于小范圍的固定迷宮，而大范圍的迷宮雖然一定能找到出口但是很耗費時間。左手法則的具體思路是先走到左側墻邊;接下來每走一步都需要首先檢測左側是否有墻，如果有則直走，否則左轉走到墻邊;然后再檢測前方是否有墻，如果有則右轉，否則繼續往前走，直到走出迷宮為止。

2.2 DFS算法

DFS算法實現走迷宮的思路與生成迷宮是一樣的。具體步驟是：（1）對已生成的迷宮地圖中的所有的迷宮單元設置為未訪問狀態，設置迷宮地圖的起點和終點位置，將起點壓入棧;（2）重復執行，直到當前單元的位置等于終點位置時結束循環，循環的內容為：1）獲取棧頂元素（不出棧），將其賦值給當前單元，把當前單元所在迷宮位置標記為已訪問狀態;2）將當前單元周圍情況（上下左右是“路”并且“未訪問”的相鄰單元）加入到待處理列表中，加入的順序是“右-下-左-上”;3）若當前單元的待處理列表內容不為空，選取第一個，將其壓入棧，否則棧頂元素出棧。

執行上述步驟后，棧內留下的元素就是從起點到終點能夠連通的點。

2.3 BFS算法

BFS算法與DFS算法的區別在于：DFS旨在不管有多少條岔路，先一條路走到底，不成功就返回上一個路口，然后選擇下一條岔路，而BFS旨在面臨一個路口時，把所有的岔路口都記下來，然后選擇其中一個進入，將它的分路情況記錄下來，再返回來進入另外一個岔路，再把當前岔路的分路情況記錄下來，重復這樣的操作。BFS算法按照層次關系逐層遍歷每個“路”結點，直至到達迷宮出口，借助數據結構隊列，先進先出。BFS算法走迷宮的具體步驟是：（1）將起點壓入隊列;（2）重復以下步驟，直到隊列為空。1）彈出隊列第一個元素，將其設置為當前單元格，并將其標記為已訪問;2）將其周圍鄰接節點（是路且未訪問）壓入隊列;

為了確定從起點到終點的最佳路徑，在循環過程中還需要將遍歷過的節點和父節點分別存入到節點列表和父節點列表中。尋找最佳路徑的做法是從終點開始查找它的父節點，將其存入最佳路徑列表中，然后再找到父節點的父節點，再存放最佳路徑列表中……，直至起點的父節點（假設起點的父節點為“-”，開始時將“-”加入到父節點列表）。

3 Scratch語言實現迷宮程序

以上兩個部分分別介紹了生成迷宮與走迷宮的常見算法步驟，本節通過使用Scratch編程語言結合Prim算法實現生成迷宮，結合DFS算法實現走迷宮。

3.1 生成迷宮

（1）定義相關變量與列表。變量有行數、列數、迷宮格大小（初始化迷宮地圖時涉及的變量），當前迷宮格（標識當前搜索到哪個迷宮格），周邊格子（當前迷宮格的上下左右相鄰迷宮格），迷宮格id（私有變量，對克隆出每個迷宮格進行標記）、起點（標識從哪個迷宮格開始），下標i（用于遍歷列表）。定義的列表有迷宮地圖狀態列表（迷宮地圖中每個迷宮格的狀態，標明迷宮格（克隆體）是路還是墻，列表的序號對應克隆體的編號，1代表墻，0代表路，初始時默認都是墻，即1），待處理墻列表（將當前迷宮格的周邊墻列表內容依次加入到該列表中），周邊路列表（當前迷宮格周邊是路的加入到列表中），周邊墻列表（當前迷宮格周邊是墻的加入到列表中）。

（2）依據Prim算法描述編寫程序，其中“繪制迷宮大小，行列迷宮格大小”是初始化迷宮地圖的函數。通過克隆繪制行乘以列個迷宮格，初始時每個迷宮格都是墻（即設置迷宮地圖狀態列表為1），最終由克隆體（根據迷宮格id區分每個克隆體）依據迷宮地圖狀態具體顯示迷宮格是墻還是路，需要注意的是隨著迷宮地圖的生成，迷宮地圖狀態列表中的數據是不斷變化的。“返回第X個迷宮格周圍情況”是獲取X迷宮格上下左右迷宮格的函數，X周邊是墻的加入周邊墻列表，是路加入周邊路列表。“將當前迷宮格周圍墻加入待處理墻列表”是指由“返回第X個迷宮格周圍情況”函數得到的周邊墻列表內容依次加入到待處理墻列表中。

假設左上角（第一個迷宮格）是起點，右下角（第行數乘以列數的迷宮格）是終點，將左上角和右下角的迷宮格設置為路。生成迷宮的核心程序如圖1所示。

3.2 走迷宮

依據上述DFS算法描述編寫程序，在上述變量基礎上增加終點變量，路且未被訪問列表（存儲當前迷宮格右下左上是路且未訪問的迷宮格），迷宮單元訪問狀態列表（初始時每個迷宮單元都為未訪問狀態，0表示未訪問，1表示已訪問），棧列表。走迷宮的核心程序如圖2所示。

以上主要是借助最簡單的圖的搜索遍歷算法實現迷宮程序，對于解決迷宮問題還應該從提高迷宮搜索效率和最優路徑等方面考慮，如基于A*算法改進的向心法法則[1]（將Dijkstra和BFS兩種算法結合，兼顧速度與最優路徑）、基于概率距離的算法[2]（縮短迷宮搜索時間）。

參考文獻

[1] 高源，凌翌，呂鵬.基于A*算法的迷宮搜索向心法法則[J].電子設計工程，2019，27（9）：37-40.

[2] 王磊，董珊，潘洪友.基于概率距離的電腦鼠迷宮搜索算法[J].科技創新導報，2016，13（3）：93-95.