在學習演算法的過程中,老鼠走迷宮是訓練堆疊或遞迴的經典題型,在給定迷宮的情況下,想要走出迷宮,可以有沿壁法(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》,或者是其他的迷宮演算文件;當然,也可以選擇其他主題(像是熱門的機器學習)。如果不急著應用,先用空閒時間試著自行設計看看,假以時日再參考相關文件,這將會是別有一番樂趣的過程。

作者簡介


Advertisement

更多 iThome相關內容