從節點編碼看迷宮

迷宮演算法就是為樹的每個節點編碼，同時，節點的資料結構可獨立於迷宮的外觀之外，我們也可以將節點資料轉換，對應至另一組節點資料，從而創造出各式各樣的迷宮，甚至是迷宮之外的應用。

0與1的驚奇

談到迷宮，最簡單的演算法應該是二元樹演算，在先前專欄〈迷宮產生演算法之美妙〉曾經談過，若是方形迷宮，只要在每個格子丟硬幣，決定要打掉上牆或右牆，就可以形成迷宮，從編碼的角度來看，每個格子只會被賦予0或1的結果，卻能產生令人驚嘆的圖樣。

暫且離開迷宮的主題，只看0與1的賦予，或許你會想起一個古老的文字模式繪圖，每一列（row）的各個文字，是根據隨機產生的數字為奇數或偶數，顯示／或＼（正方形任一對角線），重複個幾列，就會產生類似迷宮的圖樣，你可以自己畫畫看，或者是參考〈隨機圖樣〉中的繪圖結果。

單純地每次丟硬幣是一種編碼的方式，另一種方式是，先丟硬幣產生一組x軸的結果，再丟硬幣產生一組y軸的結果，這樣每個(x,y)交界處，就會有16個可能性，對於(x,y)為左上角的格子來說，這決定出16種牆面狀態，這可以畫出什麼圖案呢？結果也是個類似迷宮的圖樣。

有趣的是，這其實是一種古老的日本刺繡法（hitomezashi stitching），而且，實際上，我們也不用找出16種牆面狀態，在x軸丟硬幣時，正面就接著x軸畫、由上往下畫虛線，反面就往下跳一格再畫虛線，在y軸丟硬幣時同理，只不過是往右畫虛線，繪製的過程可以在〈hitomezashi pattern〉實際看到。

每個格子編碼對應的意義不同，就會有不同的結果，以二元樹迷宮為例，每個格子雖然只被賦予0或1，然而若將每格看成是樹節點，就代表了從上、右鄰接節點二選一作為父節點，將節點連接後的結果，就是二元樹了。

牆面與遮罩的編碼

二元樹演算因為只能往右或往上選擇，樹根自然就是最右上角，若用來繪製迷宮，將會產生偏差，而遞迴回溯（recursive backtracker）演算可以避免這個問題，方式是隨機地選擇未造訪的鄰接格子，打通中間的牆後造訪該格，然後重複以上過程；若遇到鄰接格子都造訪過了，退回上一格，試著找出該格未造訪的鄰接格子……將以上流程重複進行至全部格子都造訪完畢為止。

因為每次回溯後可以在上一格再次打牆，這表示，每次選擇格子，就是在選擇子節點，最後形成的也是樹狀結構，而樹根節點就是最先選擇的節點，也因為是樹，所以，任兩個節點之間，必然只有一條路徑連通，因而可構成完美迷宮（Perfect maze）。

就編碼的角度來看，每次可以隨機上、下、左、右前進，這表示每個節點會是四種狀態之一，若要繪製方形迷宮，只要將編碼對應至無牆、上牆、上右牆、右牆四種狀態，那麼，迷宮必定是方形嗎？當然不是！

製造不同形狀的迷宮有多種方式，最簡單的方式是，將迷宮演算結合遮罩，原理很簡單，迷宮是一組細胞組成，事先設定某些細胞不能造訪，就可以將迷宮塑造為不同的形狀，就編碼而言，每個節點就是多了一個狀態的可能性，加上方才的牆面狀態就是有五個狀態。

並非所有迷宮演算法都可以使用遮罩，二元樹演算就不行，理由很簡單，某個節點X的左邊若選擇打通上牆，X就不可能成為父節點，若節點X的上方有遮罩，X也不可能成為子節點，那麼，它就是個懸空的節點，不可能是二元樹的一部份；如果對遮罩的實作有興趣，可以進一步探討〈迷宮與遮罩〉的內容。

轉換編碼結果

若不考慮遮罩的方式，就編碼的角度來看，每次可以隨機上、下、左、右前進，這表示每個節點會是四種狀態之一，若要繪製方形迷宮，只要將編碼對應至無牆、上牆、上右牆、右牆等四種狀態，如果我們想製造不同形狀的迷宮，還可以透過編碼轉換來達成。

例如，圓柱迷宮，單純就是將列的y座標資訊轉換為高度的z資訊，行的x座標轉換為圓的第幾段弧資訊，無牆、上牆、上右牆、右牆四種狀態不變，只要在繪製上牆部份時，改為繪製弧就可以了，也就是，迷宮演算本身不用改變，可以單純地就演算後的編碼結果，進行一對一轉換就能形成，類似的方式也可以構成多種的迷宮。

我們如果要繪製蜂巢狀迷宮呢？這須根據行（column）為奇數行還是偶數行，將無牆、上牆各又衍生出兩種狀態，也就是細胞最後可能會有六種狀態之一。

在〈蜂巢狀迷宮〉，我們可以看到繪製方式，該文中沒有直接改變迷宮演算法的實作，只是在繪圖時針對無牆、上牆各有兩種對應的繪製方式，然而，實際上，就是將既有的編碼結果轉換為另一組編碼。

但是，迷宮的編碼結果，不見得就是轉換為另一種迷宮的編碼。

先來問一個問題，你知道如何走出迷宮嗎？如果是完美迷宮，最簡單的方式是沿壁法，也就是固定一隻手摸著牆壁，手不離牆面地前進，最後一定可以從入口走到出口。就道理而言很簡單，就像我先前談過的，迷宮的路徑會形成一棵樹，如果摸著牆走，等於繞著整棵樹結構畫一圈，這中間必然會通過出口。

也就是說，你可以從迷宮的編碼結果，轉換為走出迷宮的路徑，如果是繞著整棵樹畫一圈，那就是一種哈密頓路徑（Hamiltonian path）；如果我們將迷宮的每個細胞再畫分為四等分，這個路徑必然通過畫分後的每一格，而且，每個格子並不會重複通過。若有興趣看看程式實作，了解如何實作迷宮至哈密頓路徑的轉換，我們可以參考〈哈密頓路徑〉。

圖論的節點與邊

研究迷宮到底有什麼用呢？當你將迷宮的細胞資料與外形分離看待，就是僅看待細胞間如何連結，也就步入圖論（Graph theory）的範圍了，方才的哈密頓路徑已經透露出端倪了，它就是一種無向圖（undirected graph）。

圖論是研究節點與邊的數學，可用來描述某些事物之間的某種特定關係，就社交軟體、人工智慧為熱門話題的今日而言，圖論的重要性不用多做說明，而且，各式的迷宮演算法中，有不少都跟圖論有關係，像是Kruskal、Prim演算等，只是大家先前所探討的迷宮演算，沒有為節點間的連結加上權重限制罷了。

或者從另一個角度來看，圖論中有些演算，可以用來解決迷宮生成的問題，必要時，你也可以為迷宮間的連通加上權重考量，再來採取Kruskal、Prim這類的演算。

若你能獨立地看待節點編碼，也就能更清楚地瞭解圖論中這些演算用於迷宮的意義，屆時就能更靈活地用來衍生更多的迷宮，或用這類演算來解決其他的問題！