樹狀線迷宮(如下圖)，專指一個由直交線段組成的迷宮中，不包含「迴圈」的路徑。在每年教育部主辦的「電腦鼠暨智慧輪型機器人競賽」中，屬於國中小組的「線迷宮鼠」競賽活動。規則請參考以下連結 https://sites.google.com/gm.lhu.edu.tw/2021tmirc/Home/Line-maze。
這一類的「樹狀」線迷宮，我們可以藉由既定的 (https://www.pololu.com/file/0J195/line-maze-algorithm.pdf) 左手優先(左轉路徑優先、中間次之，右轉最後)，或者是右手優先法則(右轉路徑優先、中間次之，左轉最後)，讓輪型機器人從起點出發，紀錄每一個路口執行的動作(如左轉為’L’，直走為’S’，右轉為’R’)，最後可以找到迷宮的終點。
以上圖為例，在每一個路口採用左手優先(左轉路徑優先、中間次之，右轉最後)的終點搜尋方法，出發時一定是直走，當第一次碰到路口時，選擇左轉，所以圖中會有「1L」的文字標示。依此類推，當左轉後第二次碰到路口時，還是選擇左轉，所以會有「2L」的文字標示。第三次碰到路口時，因為是死路，所以迴轉後，紀錄是「3B」的文字標示。最終找到終點時，以文字「28E」做為結尾。因此，每一個路口的動作記錄下來後，由起點到終點的路徑結果就是「LLBLSBLBLSLLLBLSBLLBLSLLBRLE」。
但上圖「樹狀」線迷宮中，由左手優先法則所記錄下來，由起點到終點的路徑，並非最簡單、最短的路徑，因為中間有太多不必要的迴轉(B)動作。因此，針對迴轉(B)動作，可以找出以下幾個簡化的規則，去除掉該路徑上的迴轉(B)動作，從而簡化出一個由起點到終點的「最短路徑」。
第一個規則是當碰到「左卜」路口，而且左轉的路徑為死路時，左手優先法則所得到的動作會是「LBL」，此時可以簡化為直走「S」，不需要左轉。
第二個規則是當碰到「左彎」路口，而且左轉的路徑為死路時，左手優先法則所得到的動作會是「LBR」，此時的路口，就可以簡化為迴轉「B」，不需要左轉。
第三個規則是當碰到「T字」路口，而且左轉的路徑為死路時，左手優先法則所得到的動作會是「LBS」，此時的路口，就可以簡化為右轉「R」，不需要左轉。
第四個規則是當碰到「右卜」路口，而且直走的路徑為死路時，左手優先搜尋法則所得到的動作會是「SBL」，此時的路口，就可以簡化為右轉「R」，不需要直走。
第五個規則是當碰到「右彎」路口，而且右轉的路徑為死路時，左手優先搜尋法則所得到的動作會是「RBL」，此時的路口，就可以簡化為迴轉「B」，不需要右轉。
第六個規則是在路徑簡化時才會碰到，相當於路口僅有直走路徑，而且直走後的路徑為死路，左手優先搜尋法則所得到的動作會是「SBS」，此時的路口，就可以簡化為迴轉「B」，不需要直走。
或許有人會有疑問，難道只有這六個規則嗎？的確是的，因為在路口時， BitRacer 能夠採取的動作只有「直走(S)」、「左轉(L)」、「右轉(R)」，以及「迴轉(B)」四種動作。如果要針對「迴轉(B)」的前一個動作，以及後一個動作，這三個動作組合來簡化，那麼只會有包含在六個規則中的「SBS」、「SBL」、「LBS」、「LBL」、「LBR」、「RBL」，以及沒有在規則中的「SBR」、「RBS」、「RBR」三種。只是沒有在規則中的這三種，在左手優先搜尋法則中，是不可能會出現的組合。
接下來利用 MakeCode 的環境來實現這一個做法。
步驟一：將「樹狀」線迷宮的範例路徑「LLBLSBLBLSLLLBLSBLLBLSLLBRLE」，記錄到「地圖資料」的文字變數中。並以按鈕B啟動本實作對應的主程式。完成主程式的條件有二個，1) 所有包含迴轉(B)的動作組合，皆已被六個路徑簡化規則取代，2) 路徑中不再包含迴轉(B)的動作。因此，主程式中以「地圖資料」的文字變數中包含文字 ”B” 作為執行迴圈的依據，然後再以「替換地圖資料」函式，來執行六個路徑簡化規則。
步驟二：完成「替換地圖資料」函式。這一個函式有「地圖」、「簡化路口」，以及「替換資料」三個輸入參數，還有一個傳遞結果的「Path」輸出參數。其中「地圖」變數，是用來傳遞現有可能需要簡化的紀錄路徑，「簡化路口」是用來傳遞簡化規則中的三個動作組合，而「替換資料」則代表用來取代「簡化路口」的動作資料。
函式一開始先將當「地圖」這一個輸入參數指定給「Path」變數，並且以「Path」變數中含有「簡化路口」的情況，作為持續執行迴圈的依據。
如果「Path」變數中含有「簡化路口」，那麼「簡化index」變數，用來記錄「簡化路口」第一次出現在「Path」變數中的最小索引值。舉例來說，如果「Path = ‘LLBLSBLBLSLLLBLSBLLBLSLLBRLE’」，而且「簡化路口 = ‘LBL’」，那麼「簡化index」這一個變數就會是 1，因為「Path」文字變數中第一次出現的 LBL，是從第2個字元開始，但是對於陣列(文字變數相當於字元陣列)而言，第2個字元的陣列索引值是 1。
接下來就是要將「Path」變數拆開成三部分，第一部分是「簡化路口」變數內容之前的內容，也就是陣列索引值由0開始，長度是「簡化index」數值的大小，將它指定給「TempPath1」變數。第二部分是「簡化路口」變數的內容，第三部分是「Path」變數去除第一與第二部分的內容，也就是陣列索引值由「簡化index」數值加上「簡化路口」變數的長度開始，長度是原有「Path」變數的長度減去「簡化index」數值，再減去「簡化路口」變數的長度，並且將這第三部分指定給「TempPath2」變數。
最後再將「Path」簡化成「TempPath1」、「替換資料」，以及「TempPath2」三個變數的組合。並重複以上的步驟，直到「Path」變數中不再含有「簡化路口」的內容。
思維與挑戰
在「替換地圖資料」函式中，用了不少程式碼，在「Path」變數中找出含有「簡化路口」規則的文字，並且將它替換成對應的文字，但有沒有更簡單的方法呢？
在 MakeCode 的環境中，其實也可以利用 JavaScript 來寫程式。在 JavaScript 中，針對文字變數，有提供一個取代(replace)的方法，正好是我們所需要的功能。
以下圖為例，「Route」變數為 ”LLBLSE”， 「Best_route」變數用來儲存「Route」變數中，將 ”LBL” 文字替換成 “S” 的結果。在按鈕A按下後的程式內容中，有一個灰色的積木方塊，代表它是在JavaScript 的編寫環境下完成的。我們也可以利用MakeCode 環境中的偵錯模式，來檢查執行的結果是否如我們所預期喔。
用功的同學，你可以用這一個方法來重寫這一個實作的程式嗎？
沒有留言:
張貼留言