Scratch之自動(dòng)走迷宮

陳新龍

如何讓程序自己走迷宮是一個(gè)挺深?yuàn)W的問(wèn)題，涉及生成迷宮的prim算法、深度優(yōu)先算法，走迷宮的廣度優(yōu)先算法、深度優(yōu)先算法等。不過(guò)那些都有一定難度，我們還是先從最簡(jiǎn)單的一種算法開(kāi)始吧，這種自動(dòng)走迷宮的算法其實(shí)是把自己當(dāng)成盲人走迷宮。這就是“左手法則”，這種法則只針對(duì)有墻壁且出口在墻壁上的迷宮（如果出口在大廳中心的情況就不適用了），只要順著墻壁走，都能走出去。因?yàn)槌隹诤腿肟诘膲Ρ诙际情]合曲線，所以這種“法則”在這類迷宮中是通用的。不過(guò)“左手法則”的效率太低，只適用于小范圍的固定迷宮，而大范圍的迷宮用這種算法會(huì)耗費(fèi)大量的時(shí)間。未來(lái)我也會(huì)和大家分享“深度優(yōu)先”等算法和如何自動(dòng)生成隨機(jī)迷宮。

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

1. 走到墻邊

2. 監(jiān)測(cè)左邊是否有墻壁

3. 監(jiān)測(cè)前面是否有墻壁

4. 左右轉(zhuǎn)向

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

代碼分析：

程序以網(wǎng)上找到的一個(gè)簡(jiǎn)單迷宮為背景，迷宮墻壁為黑色。圓球角色Ball走迷宮，Bell鈴鐺為迷宮出口。

我們需要自定義三個(gè)函數(shù)模塊積木，對(duì)應(yīng)左手法則的三個(gè)判斷（走到墻邊，判斷左邊是否有墻，判斷前邊是否有墻）。

1. 走到墻邊

這個(gè)功能就是讓角色一直沿著既定的方向前進(jìn)，直到碰到墻壁。這里可以使用偵測(cè)中的“碰到顏色”積木來(lái)實(shí)現(xiàn)。

2. 判斷左邊是否有墻

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

因?yàn)樽笠苿?dòng)作只是為了做偵測(cè)，并不能真的移過(guò)去，所以在檢測(cè)完畢后還要將角色進(jìn)行復(fù)位。把移動(dòng)的步數(shù)退回來(lái)，轉(zhuǎn)過(guò)的角度也要轉(zhuǎn)回來(lái)。

3. 判斷前方是否有墻

這個(gè)功能和判斷左邊是否有墻的方法一致，也需要添加“前邊是否有墻”變量，用“碰到顏色黑”為條件。當(dāng)前進(jìn)一步碰到墻壁，則說(shuō)明前方存在墻壁，變量值為1，如果沒(méi)有碰到墻壁，則說(shuō)明左邊沒(méi)有墻壁，變量值為0。并退回到原處。

接下來(lái)看分析主程序的代碼部分，設(shè)置變量初始值為0，恢復(fù)角色初始位置，設(shè)置角色大小方向。走到墻邊，然后開(kāi)始進(jìn)行角色移動(dòng)過(guò)程的兩種判斷，重復(fù)執(zhí)行直到角色到達(dá)終點(diǎn)也就是碰到Bell，結(jié)束循環(huán)。在循環(huán)的過(guò)程中先判斷左邊是否有墻壁，當(dāng)左邊沒(méi)墻時(shí)向左轉(zhuǎn)，且角色前進(jìn)一步。這個(gè)前進(jìn)移動(dòng)非常重要，如果忘記寫前進(jìn)代碼的話，會(huì)造成角色原地打轉(zhuǎn)的Bug。當(dāng)左邊有墻時(shí)，才可以進(jìn)行前方是否有墻壁的判斷。如果前方存在墻壁，因?yàn)檫@時(shí)左邊前面都有墻壁，我們只能右轉(zhuǎn)，注意只是右轉(zhuǎn)并沒(méi)有前進(jìn)。如果判斷前方?jīng)]有墻壁，那么此時(shí)就可以放心地前進(jìn)一步。最終角色會(huì)一直沿自己左邊的墻壁運(yùn)動(dòng)直到終點(diǎn)，走出迷宮。

今天用最簡(jiǎn)單的左手法則算法完成了自動(dòng)走迷宮的目標(biāo)，對(duì)算法有了一點(diǎn)最基礎(chǔ)的了解，在未來(lái)的時(shí)間里，我也會(huì)和大家分享深度優(yōu)先算法和遞歸的算法，更快地走出迷宮。并學(xué)會(huì)自動(dòng)生成隨機(jī)迷宮地圖。