Labyrinth
陣法大師
2022第四屆科工館
Embedded Files
競賽地圖
節點、方向、法則。
節點：共計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
，這個版本未最佳化、尚有改進空間，話雖如此，應該也能順利執行。
左手法則
左手法則
固定迷宮捷徑記憶實測影片
『左手法則』紀錄捷徑程式碼
分段加速、前進節點、偵測隔板程式碼請參閱固定迷宮。
右手法則
右手法則
固定迷宮捷徑記憶實測影片
『右手法則』紀錄捷徑程式碼
分段加速、前進節點、偵測隔板程式碼請參閱固定迷宮。
處理清單『節點方向』程式碼
Page updated
Report abuse