Scratch之自動走迷宮

陳新龍

如何讓程序自己走迷宮是一個挺深奧的問題，涉及生成迷宮的prim算法、深度優先算法，走迷宮的廣度優先算法、深度優先算法等。不過那些都有一定難度，我們還是先從最簡單的一種算法開始吧，這種自動走迷宮的算法其實是把自己當成盲人走迷宮。這就是“左手法則”，這種法則只針對有墻壁且出口在墻壁上的迷宮（如果出口在大廳中心的情況就不適用了），只要順著墻壁走，都能走出去。因為出口和入口的墻壁都是閉合曲線，所以這種“法則”在這類迷宮中是通用的。不過“左手法則”的效率太低，只適用于小范圍的固定迷宮，而大范圍的迷宮用這種算法會耗費大量的時間。未來我也會和大家分享“深度優先”等算法和如何自動生成隨機迷宮。

最經典的“左（右）手法則”算法：在一張連通的迷宮圖中我們用左右任意一只手一直摸著墻就一定可以走出這個迷宮，也稱為繞墻走算法（或摸墻算法），是一種迷宮搜索的初級算法。左手法則的關鍵點：

1. 走到墻邊

2. 監測左邊是否有墻壁

3. 監測前面是否有墻壁

4. 左右轉向

下面我們把左手摸墻的走法用流程圖表示出來，更加方便讓大家理解。

代碼分析：

程序以網上找到的一個簡單迷宮為背景，迷宮墻壁為黑色。圓球角色Ball走迷宮，Bell鈴鐺為迷宮出口。

我們需要自定義三個函數模塊積木，對應左手法則的三個判斷（走到墻邊，判斷左邊是否有墻，判斷前邊是否有墻）。

1. 走到墻邊

這個功能就是讓角色一直沿著既定的方向前進，直到碰到墻壁。這里可以使用偵測中的“碰到顏色”積木來實現。

2. 判斷左邊是否有墻

根據流程圖結合代碼，要求角色每行動一步就要判斷一次左邊是否存在墻壁。在這個自定義函數中，我們還要定義一個“左邊是否有墻”的變量，如果左邊存在墻壁，就將這個變量設為1，否則這個變量值就是0（一直重復判斷直到角色最終走出迷宮）。如何判斷左邊是否存在墻壁呢？我們可以讓角色往左邊移動一步，然后再偵測一下是否碰到了墻壁（在本例中，墻壁顏色是黑色的，可以使用“碰到顏色黑”作為檢測條件）就可以了。當左移一步碰到墻壁，則說明左側存在墻壁，如果沒有碰到墻壁，則說明左邊沒有墻壁。

因為左移動作只是為了做偵測，并不能真的移過去，所以在檢測完畢后還要將角色進行復位。把移動的步數退回來，轉過的角度也要轉回來。

3. 判斷前方是否有墻

這個功能和判斷左邊是否有墻的方法一致，也需要添加“前邊是否有墻”變量，用“碰到顏色黑”為條件。當前進一步碰到墻壁，則說明前方存在墻壁，變量值為1，如果沒有碰到墻壁，則說明左邊沒有墻壁，變量值為0。并退回到原處。

接下來看分析主程序的代碼部分，設置變量初始值為0，恢復角色初始位置，設置角色大小方向。走到墻邊，然后開始進行角色移動過程的兩種判斷，重復執行直到角色到達終點也就是碰到Bell，結束循環。在循環的過程中先判斷左邊是否有墻壁，當左邊沒墻時向左轉，且角色前進一步。這個前進移動非常重要，如果忘記寫前進代碼的話，會造成角色原地打轉的Bug。當左邊有墻時，才可以進行前方是否有墻壁的判斷。如果前方存在墻壁，因為這時左邊前面都有墻壁，我們只能右轉，注意只是右轉并沒有前進。如果判斷前方沒有墻壁，那么此時就可以放心地前進一步。最終角色會一直沿自己左邊的墻壁運動直到終點，走出迷宮。

今天用最簡單的左手法則算法完成了自動走迷宮的目標，對算法有了一點最基礎的了解，在未來的時間里，我也會和大家分享深度優先算法和遞歸的算法，更快地走出迷宮。并學會自動生成隨機迷宮地圖。