迷宮製作的演算法與圖例

且鼓起勇氣，試著談談「電腦平面迷宮」製作的技術細節。

需要勇氣，是因為談技術，通常容易流於枯燥與沈悶。然而，若我想要寫一篇關於「迷宮」主題的文章，卻非得督促自己去嘗試描述技術細節。因此，就讓我試著接續先前對迷宮的製作，做些更深入的描述與討論吧。

先前提過，可以用樹狀結構來產生迷宮。現在，我們可以將演算法（產生迷宮的方法）說得更仔細些。注意到，在這兒一個節點就是一個迷宮的格子；而相鄰的兩個節點間，如果沒有連結，我們說兩個格子間有一道「牆」。

1. 一開始，任選一個節點。
2. 將這個節點四周「可被打通的牆」（不含迷宮的外圍），放入一個「連結集合」C 裡。
3. 將此節點，放入「已處理之節點」集合 T 裡。
4. 如果 C 為空集合，表示迷宮已經產生完畢，我們停止程式。若 C 不為空集合，從中任意挑選一道牆（假設這道牆連結節點 n₁ 與 n₂，而 n₁ 在集合 T 裡），並打通它。
5. 如果 T 的節點與節點 n₂ 間，有連結在 C 裡，則將這些連結從 C 裡移除。
6. 將 n₂ 標示為「已處理」（放入集合 T 裡），並回到步驟 (4)。

直接看以上的演算法，可能會有「霧煞煞」的感覺。配合著一個實例來對照，應該會比較清楚。

首先，假設我們要產生一個 3x3 的小迷宮。為了方便說明，我們將迷宮的格子標上號碼（英文字母 A~I），如右圖 (a) 所示。現在，且讓我們跟著演算法的步驟走一回：

1. 任選一個節點。假設我們選到 B。
2. 將節點 B 四周「可打通的牆」放入集合 C。參考下圖 (1) 中的黑色虛線。
3. 將節點 B 放入「已處理」的節點集合 T（含有圓點的格子）。如下圖 (1) 所示。
4. 執行演算法步驟 (4)。因為 C 不為空集合（圖 (1) 中有黑色虛線存在），所以我們從中任意挑選一道牆，例如 B-E（n₂ 為節點 E）間的牆，把它打通。
5. 接下來，進行演算法的步驟 (5) 與 (6)，可以得到下圖 (2).


6. 接著，我們再次進行演算法的步驟 (4)，假設這回從 C 選出 A-B 間的牆來打通。進行步驟 (5) 與 (6) 之後，我們得到下圖 (3)。
7. 重覆執行步驟 (4)，假設這回選出 D-E（n₂ 為節點 D）間的牆來打通。
8. 執行步驟 (5)。注意到，節點 D 與 A 之間，原本有「可被打通的牆」，但因為 A 已經被放入「已處理」的節點集合 T 裡，我們在此必須把 D-A 之間的牆從集合 C 裡移除（用紅色虛線表示已由 C 移除的牆）。
9. 執行步驟 (6)，將節點 D 加入集合 T 之中。至此我們得到下圖 (4)。
10. 仿前步驟 (4)、(5)、(6)，破除 E-H 的牆，將 H 加入 T 後，得到下圖 (5)。



11. 依循步驟 (4)、(5)、(6)，破除 H-I 的牆，將 I 加入 T 後，得到上圖 (6)。
12. 依循步驟 (4)、(5)、(6)，破除 I-F 的牆，將 F 加入 T 後，得到上圖 (7)。
13. 依循步驟 (4)、(5)、(6)，破除 F-C 的牆，將 C 加入 T 後，得到上圖 (8)。
14. 依循步驟 (4)、(5)、(6)，破除 D-G 的牆，將 G 加入 T 後，得到上圖 (9)。
15. 至此，C 已經變成空集合（圖 (9) 裡，已經沒有黑色的虛線，表示已經沒有「可被打破的牆」）了，因此程式停止。我們最後產生的 3x3 迷宮，就如上圖 (b) 所示。

有時，會很訝異於自己是如此地沒有效率：即使是這麼短短的一小段內容，也需要自己好幾天的時間來構思、繪圖、撰寫、修改呢。