迷宮產生演算法之美妙

在學習演算法的過程中，老鼠走迷宮是訓練堆疊或遞迴的經典題型，在給定迷宮的情況下，想要走出迷宮，可以有沿壁法（Wall Following）、深度優先搜尋、廣度優先搜尋等方式……，解決迷宮出路的資料很多，然而，產生迷宮的資料相對就少了。也因為如此，想要系統式搜尋、建立迷宮產生演算法的過程，才會充滿挑戰與趣味。

初次接觸迷宮產生器

第一次接觸到迷宮產生器，是在《Java於演算法與資料結構之應用》中說明遞迴的章節中看到的，初見覺得神奇，該演算法會生成完美迷宮（Perfect maze），也就是只會產生一條可走出迷宮的路徑，因為，演算法為了迷宮的每個格子，建立上牆與右牆，例如：如果向上走，就拆掉目前格子的上牆；向右，就拆掉目前格子的右牆；向下走，則是拆掉下面格子的上牆；向左走，則是拆掉左邊格子的右牆。

當時並沒有細究是什麼樣的思路構成這個演算法，只覺得它將迷宮中每格的上下左右四個牆，歸納至每個格子只有上牆與右牆，是個聰明的作法。後來在接觸3D程式建模時，試著使用OpenSCAD實現迷宮產生演算時，也只是將書中的Java程式碼，試著翻譯為OpenSCAD而已，正如〈挑戰OpenSCAD迷宮產生器〉中寫到的，當時遇到的難題，是必須將命令式的Java程式碼，轉換為函數式的風格，也因此沒有去深究演算法的構成方式。

實際上，迷宮演算法也有許多種。在維基百科〈Maze generation algorithm〉的條目中，就列出了一些，有基於圖論（Graph theory）的方式，像是深度優先搜尋、Prim演算、Kruskal演算等，也有遞迴切分（Recursive Division）演算。而最後這個，比較引起我的注意，一開始是個全空的空間，然後隨機建立牆面來切分空間，牆上建立一個隨機的通道，以連接兩個空間，接下來，對每個切分的空間進行遞迴。

而遞迴切分（Recursive Division）演算之所以會引起我注意，原因在於，每個被切分的空間，都可以再被視為用來產生一個小迷宮的空間，也就是一個大迷宮是由許多小迷宮組成，維基百科上，也有它產生迷宮的過程動畫，讓人很容易理解它的產生過程。然而，我心中一直在想的是，有沒有書或網站，詳細說明了各種由易至難的迷宮產生演算呢？

繪製不同形狀的迷宮

除了尋找各種由易至難的迷宮產生演算之外，迷宮產生還有另一個挑戰，就是繪製不同形狀的迷宮。

這個構想的來源很簡單，常見的迷宮演算，都使用四方形的迷宮來表現，因此通常使用了方陣之類的資料結構，以便記錄已造訪過的格子，以及每個格子擁有的牆面方向，這會是比較方便的做法（而不是一邊造訪，一邊繪製）。在這種作法下，數據與畫面的呈現，實際上是分離的。

因此，第一個想到的作法就是，可以將迷宮立起來，圍成一個圓柱形，這樣就可以創造出迷宮戒指之類的模型；而下一個馬上就想挑戰的，就是圓形迷宮——在沒有任何文件書籍的輔助下，想到的方式是，將原來迷宮最左邊的牆，當成是最內圓，最右方的牆當成是最外圓，上下兩牆繞個圈，連在一起，如此一來，只要在繪製時，分別畫弧與半徑上適當的線段，就可以構成圓形迷宮了。

相同的演算，可以用來構成三角迷宮。乍聽也許覺得神奇，實際上，一個圓可以看成是無數個三角形組成，因此，不僅三角迷宮，就連四角、五角、六角……等正多邊形迷宮，都可以建立。

思考繪製不同形狀的迷宮，實際是個思考幾何圖案如何構成的過程，我的腦中有許多待解的迷宮，而每解決一個，就會在空閒時，思考著下一個迷宮可以如何實現，也就因此累積了許多的迷宮作品（https://goo.gl/XTU0Wv）。

例如，蜂巢式迷宮是我待解迷宮當中的一個，因為每個格子都是六角形。一直以來，我始終以為，大概必須將每個格子，歸納為上、右上與右邊等三個牆，因此，不能用方陣來儲存迷宮數據，也就一直未能具體地實現它；直到有朋友介紹了《Maze for Programmers》，其中談到：若仔細觀察的話，實際上，蜂巢式迷宮也是個方陣迷宮，只是左右鄰接的兩行是上下錯落著，才因此恍然大悟。

循序漸進地探討迷宮產生

其實，學習特定演算法，需要一個循序漸進的過程，否則就只會學習到演算法的表面。而學習的重點，其實是不斷地觀察、思考、改進的這個迭代過程，而不是最終的演算法成果，如此，在遭遇到未解決過的問題時，才能循著類似的思路，創造自己的演算方式來解決問題。

單就繪製迷宮這方面，《Maze for Programmers》中談到使用Polar Grid來繪製圓形迷宮時，與我自己想出來的圓形迷宮繪製法非常類似，而我還想要實現的迷宮之一，就是將方陣填入不規則形狀，書中的Masking方式與我也有類似的思路，因此，看到這些相類似的觀點時，其實非常開心。

不過更重要的是，書中從最基本的二元樹演算法開始介紹迷宮，這解開了我對之前使用的迷宮演算法迷惑。若不要管牆面，將每個互通的格子連接起來並拉開，確實是個二元樹啊！在造訪的過程中，只選擇拆掉目前格子的上牆或右牆，相當於選擇一個格子作為父節點，而且，因為是二元樹，樹上任兩個節點之間，都只會有一個路徑可以互通。

然而，基本的二元樹演算法會形成偏差（bias），因為在造訪最右邊時，沒有右牆可拆，只能一直拆上牆，而在最上邊時，因為沒有上牆可拆，就只能一直拆右牆，所以，產生的迷宮最右邊與最上邊，一定就會是直通的路徑；為了改進這個偏差，可試著逐列處理，並在先前造訪過的路徑上，隨機找個格子拆掉上牆（然後結束該條路徑），而這個Sidewinder演算，可以解決最右邊路徑直通的偏差，不過，還留下了最上邊直通路徑的偏差。

為什麼會這樣呢？這就必須進一步去探討演算時會造成偏差的本質。作者將迷宮的探討，限縮至2X2 迷宮的產生，這只會有四種可能的迷宮，因此，迷宮演算法應該要能公平地產生這四種迷宮；但是，事實上，二元樹演算法不公平地只會產生其中兩種，而Sidewinder演算也只會產生其中三種，不公平的演算法就會造成偏差。之後，作者進一步探討了幾個消除偏差的演算法。

重複地觀察、思考、解決問題

回想一下，過去大家是怎麼學習演算法呢？

就以排序為例吧！一開始通常是氣泡排序法，然後文件或書籍就會說明它的缺點，接著提出另一個排序法，說明它何以能改進排序效率，這樣的過程，一直延續到討論完快速排序法為止。

現在假設，排序是個冷門的主題，沒有什麼書籍或文件，一開始沒什麼文件或書籍可以參考，你會怎麼設計排序演算呢？有時候，是需要有這類冷門的主題，來訓練一下我們重複地觀察、思考、解決問題的這個能力，縱使最後尚未能自行構成一個有效的演算法，也能在日後看到相關文件或書籍的同時，獲得豁然開朗、掌握問題核心的感覺。

迷宮產生演算只是我誤打誤撞，從而發現其美妙的一個主題，有興趣的話，可以試著自行設計看看，再參考《Maze for Programmers》，或者是其他的迷宮演算文件；當然，也可以選擇其他主題（像是熱門的機器學習）。如果不急著應用，先用空閒時間試著自行設計看看，假以時日再參考相關文件，這將會是別有一番樂趣的過程。