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

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這類的演算。

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

作者簡介

熱門新聞


Advertisement