Labyrinth
陣法大師
2022第四屆科工館
競賽地圖
節點、方向、法則。
節點:共計4條進入路線,每條進入路線對映3條出路。
方向區分:0直走、1左轉、2右轉。
行走法則:『左手法則』或『右手法則』。
『右手法則』方向判斷:
先看右邊,有路則方向=2。否則
看前方,有路則方向=0。否則
看左邊,有路則方向=1。否則
方向=3,往回走重新判斷方向。
『左手法則』方向判斷:
先看左邊,有路則方向=1。否則
看前方,有路則方向=0。否則
看右邊,有路則方向=2。否則
方向=3,往回走重新判斷方向。
到此處都是簡單的問題處理,只要決定好方向法則,就一定能找到出口,除非遇到了「死」迷宮。接下來,就是要試圖解決,在走過一次之後,就知道最短路徑(紀錄走過的節點資訊)。最後,也可以挑戰一下,如果遇到了「死」迷宮無法走出來,「死」迷宮怎麼判斷?
Shortcut 捷徑
記錄走過的節點最短路徑資訊
將每次『法則』所找出的「方向」資訊,寫入清單『節點方向』。
以底下迷宮為例:
以『右手法則』執行後的陣列內容:
共經過20個節點,(Counter=20)
節點方向:23002200101320221212
經過次數:14221122323412113131
最短路徑:1022011212,第1、第6方向必須更改(有底線的部分)。
及時處理法
解析:底線部分為必須處理的節點,以『節點方向』3為中心,刪除3的 節點之後,合併兩旁的節點成為一個節點,若合併的節點也等於3,則重複執行刪除、合併。
『節點方向』3為中心:不紀錄3這個節點,回頭處理上一個節點紀錄2。
原先第一個節點紀錄=2(經過次數為1),下一個節點遇到3必須回來。0與2是同一個節點,依『右手法則』,經檢查判斷之後,應該更改為方向為1,還是只保留一個節點紀錄。
接下來的也依上例處理,重點是:「回上一節點」重新判斷並做出改變。
『節點方向』紀錄過程如下:
2→[23]→更改2為1捨棄3→10→
102→1022→10220→102200→1022001→10220010→102200101→
10220010[13]→更改1為3捨棄3→1022001[03]→更改0為3刪除3→102200[13]→更改1為3刪除3→10220[03]→ 更改0為1刪除102201→
1022011→10220112→102201121→1022011212
※此法屬於及時處理,遇到「死角」馬上處理。※
陣列處理法
『經過次數』4為中心,刪除4的節點,合併左右兩個節點,若合併後節點經過次數也等於4,則重複刪除、合併。
上述方法,使用迴圈存取、刪除、更改陣列資料就能辦到,陣列處理變化如下所列。
次數陣列:14221122323412113131、 方向陣列:23002200101320221212
次數陣列:321122323412113131、 方向陣列:102200101320221212
次數陣列:3211223242113131、 方向陣列:1022001030221212
次數陣列:32112234113131、 方向陣列:10220010221212
次數陣列:321122413131、 方向陣列:102200321212
次數陣列:3211233131、 方向陣列:1022011212
輸出最短路徑:1022011212 (方向陣列)
※這種方法屬於事後處理,必須多花一些時間。※
以『左手法則』執行後的陣列內容:
共經過12個節點,
節點方向:102031011212
經過次數:123241211313
最佳方向:1022011212
及時處理法
『節點方向』紀錄過程如下:
1→10→102→102[03]→更改0為2捨棄3→1022→
10220→102201→1022011→10220112→102201121→1022011212
陣列處理法
以次數陣列4為中心:刪除4的節點,合併左右兩個節點。
次數陣列:123241211313、 方向陣列:102031011212
次數陣列:1233211313、 方向陣列:1022011212
『死巷』探討
(...?死相?...)
第一個想到的方法是,以「方向=3」作為處理條件,=3的節點不做紀錄,回上一個節點再做判斷,可能是「更改上一節點方向」,或是「刪除上一節點紀錄」,暫且稱之為「節點處理法」。另一種方法是,把陣列內容=3的紀錄拿掉,剩下前後的兩筆紀錄其實是同一個節點,必須更新方向、或刪除,這個方法姑且稱為「陣列刪除、合併法」。
底下先討論「節點處理法」,很煩、而且有Bug,因為往回走必須處理不特定數量節點,這個方法只能處理一個ㄇ字,太長的ㄇ型就真的『死相』了。
『節點處理法』
發生節點方向=3時,應回頭查看「上一節點」方向,代表由不同方向進入死巷的不同狀況及處理方式,「上一節點」方向可以概分為0、1、2三種,依『右手法則』、『左手法則』列舉如下。
『右手法則』的節點方向分析
右手法則,上次方向=0。
偵測隔板(右邊),有1,2兩種情況。
1.右邊無隔板:右轉、新方向=1、UpdateNode。
右手法則,上次方向=0。
2.右邊有隔板:delete node、
方向=3、上次方向=上一節點方向。
右手法則,上次方向=1。
3.右側無隔板是唯一情況:右轉,刪除節點 delete node、
方向=3、上次方向=上一節點方向。
右手法則,上次方向=2。
偵測隔板(右邊),有4,5,6三種情況。
4.右邊無隔板:右轉,新方向=0、UpdateNode。
※有隔板時,再偵測前方,又可分為5,6兩種情況:
右手法則,上次方向=2。
5.前方無隔板:新方向=1、UpdateNode。
右手法則,上次方向=2。
6.前方有隔板:左轉、delete node、
更新:方向=3,上次方向=上一節點方向。
※結果發現,這種長ㄇ字型,要刪除的節點可能不只一個,必須一路往回刪除。※
『左手法則』的節點方向分析
左手法則,上次方向=0。
回程偵測隔板(左),1,2兩種情況:
1.左側無隔板:左轉、新方向=2、UpdateNode。
左手法則,上次方向=0。
2.左側有隔板:delete node、方向=3,上次方向=上一節點方向。
左手法則,上次方向=1。
回程偵測隔板(左),三種情況(3,4,5):
3.左側無隔板:左轉、新方向=0、UpdateNode。
左手法則,上次方向=1。
左側有隔板,再偵測隔板(前)。
4.且前方無隔板:新方向=2、UpdateNode。
左手法則,上次方向=1。
左側有隔板
5.且前方有隔板:右轉,delete node、
方向=3,上次方向=上一節點方向。
左手法則,上次方向=2。
6.左側無隔板是唯一情況:左轉、delete node、
方向=3,上次方向=上一節點方向。
經過一番測試,綜合以上分析結果發現,以『及時處理法』是真的可以順利計算出『最短路徑』的,程式碼公布如下,程式可以拿來參賽了,測試影片稍後也會公布。
比賽時只要會寫「左手法則」或「右手法則」就可以,並不需要有計算最短路徑功能,『最短路徑』純粹是我為了教學生時多加入的。比賽程式初版此連結:https://sites.google.com/qtm.ks.edu.tw/qtmrobot/mbot-ii/fixmaze
,這個版本未最佳化、尚有改進空間,話雖如此,應該也能順利執行。
左手法則
固定迷宮捷徑記憶實測影片
『左手法則』紀錄捷徑程式碼
分段加速、前進節點、偵測隔板程式碼請參閱固定迷宮。
右手法則
固定迷宮捷徑記憶實測影片
『右手法則』紀錄捷徑程式碼
分段加速、前進節點、偵測隔板程式碼請參閱固定迷宮。
處理清單『節點方向』程式碼