若想生成無限大且不重複的地圖,就像我在先前專欄〈理解波函數塌縮演算〉探討過的波函數塌縮,的確是一種方式,只不過為了快速地篩去各個位置上不可能的拼接塊,使用了熵、塌縮、傳播等概念,因而演算的過程較為複雜。

要說波函數塌縮演算這是有條件的暴力法也行,拼接的結果也有可能會失敗,然而,有沒有更簡單的方式呢?

王氏磚的原理

王氏磚(Wang tiles)是數學家王浩於1961年提出,是一組可以彼此鄰接匹配的拼接塊,以正方形為單位,每邊可以有二到四種不同的顏色,拼接時鄰接邊必須是同色,若兩個拼接塊旋轉或翻面後相同,視為不同的拼接塊,例如,若是兩種顏色的王氏磚,上邊黃色另三邊藍色的拼接塊,與右邊黃色另三邊藍色的拼接塊,雖然旋轉後相同,然而視為不同的拼接塊。

對於一組王氏磚,一個問題是,可否在符合拼接時鄰接邊必須是同色的規則下,來密鋪無限大的平面;另一個問題是,若可以密鋪平面,是不是一定存在周期性的密鋪方式,也就是可發現重複圖案的密鋪方式,王浩的猜想是一定存在,不過,他的學生Robert Berger後來證實,存在可密鋪平面然而只能非周期性密鋪的王氏磚。

在這邊我們感興趣的是,目前有哪些王氏磚可用來密鋪平面?例如,〈Wang Tiles〉這個頁面就列出了不少分類,因為可以密鋪平面,表示可產生無限大的圖樣,由於王氏磚的鄰接邊必須是同色,同色代表著兩個拼接塊間擁有共同的屬性,這個屬性可以代表道路、牆面、相同的草地等可能性。

雙邊王氏磚

雙邊王氏磚是邊有兩種顏色可能性的王氏磚,在〈2-edge Wang Tiles〉可以看到,改變圖樣就可以生成隨機的電路板、水管等圖片,就程式演算而言,隨機並不是在每個位置隨便挑一片王氏磚,而是在每個拼接塊的共用邊緣,隨機產生二元結果,例如0或1,代表著有或沒有某種屬性。

因為王氏磚是以正方形為單位,這時表示一個拼接塊的邊緣結果會是0000、0001……1111等16種可能性,因為拼接塊的邊緣共用同一個結果(0或1),為共用邊緣隨機產生二元結果,所以,拼接塊之間必然可以拼接。

為了能快速地對應拼接塊,我們可以將二進位0000直接對應至十進位數字,在不支援位元運算的語言中,則可以將四個位元對應至1、2、4、8,若位元值為1,加總該數字,因此,0000會對應至0,0001會對應至8,0011會對應至12,依此類推,也就是〈Wang Tiles〉頁面中描述的方式

因為編碼的結果必然對應至某個拼接塊,王氏磚拼接時沒有搜尋、不用評估、速度快,一定可以拼接,它需要的是事先設計好拼接塊,由於拼接塊各自會有對應的編碼,因此在管理拼接塊上也比較方便;不過缺點是,在單純的隨機生成下,拼接出來的圖塊會比較呆板,想要有點變化的話,或許可以考慮結合一下其他隨機演算(像是噪聲演算,或是稍後會談的迷宮演算)。

這是與波函數塌縮演算最大的不同,因為,波函數的方式是可以從具有區域相似性的拼接塊中,自動評估有哪些拼接塊並考量權重,因而拼接塊在設計上的自由度會高一些。

例如,拼接塊的鄰居數量可以不受限(因為波函數只考慮拼接塊的相容性),藉由調整範例拼接塊,最後輸出的拼接塊風格也會有很大的差異;不過缺點是,運算速度比較慢,範例拼接塊的定義嚴謹與否,會影響最後拼接的成功與否,必須自行設想如何管理拼接塊等。

雙邊王氏磚隨機生成的電路板,看來有點像是迷宮,實際上將拼接塊的圖換成牆與道路,的確可以構成迷宮圖樣,不過,隨機生成的邊緣0或1,所構成的迷宮不是完美迷宮(Perfect maze),因為,有些道路可能自成一圈,而有些道路可能有迴圈。

然而,如先前專欄〈從節點編碼看迷宮〉談過的,迷宮的生成可以看成是一種編碼的過程,完美迷宮的結果可以轉換為其他編碼,從而構成哈密頓路徑,既然如此,也可以轉換為拼接塊的邊緣編碼,因此,我們在〈'Perfect' Maze Generator〉看到,王氏磚也能構成完美迷宮,也就不是什麼意外之事了。

王氏磚的變化

雖說王氏磚是以二維的平面磚為基礎,不過,略為變化,也是可以構成三維的立體拼接效果,例如,我實作的〈Tube box〉模型,就是基於雙邊王氏竱,建立的隨機的立體水管分布效果。

雖說雙邊王氏磚最多可以有16種拼接塊,不過,如果這16種拼接塊並非靜態圖片或模型,而是透過程式生成的呢?

我所實作出來的〈Random city〉模型,就是個例子,每個拼接塊的建築物都是隨機生成,其實,道路也可以隨機生成,只要邊緣有接合,一樣可以無縫地接成隨機之城,如果再加上個遮罩陣列,還可以生成想要的輪廓,例如臺灣輪廓的隨機城市風貌。

王氏磚是基於鄰接邊,然而方才談過,拼接塊邊緣同色,只是代表兩個拼接塊間會有某種共同的屬性連結,換個角度來看,若連結的位置不是邊而是角落呢?這就是〈2-corner Wang Tiles〉中看到的雙角版本

而王氏磚變化後的雙角版本,雖然就編碼上來看,與雙邊王氏磚是相同的,不過,一個邊只會決定鄰接的兩個拼接塊有共同的屬性,但一個角可以決定鄰接的四個拼接塊有共同的屬性,這也表示,圖樣拼接的結果會有更多的循環性,例如,更多的道路連通。

基本上,王氏磚每邊可以有二到四種不同的顏色,〈Wang Tiles〉談到三邊與四階版本,但重點在於,顏色只是代表著拼接時共同的屬性,更多的邊代表著更多的屬性,也就是更高的維度。

因此,王氏磚雖然是二維的概念,然而三邊顏色相同,可以推廣成三維版本,也就是x、y、z方向各自的兩個面是否有共同屬性,例如,在三維立體空間上下左右隨機蜿蜒的水管或立體迷宮。

拼接中的數學

拼接的應用在日常中其實無所不在,磁磚、衣服、包裝紙等處都可見,一直以來,我對拼接也有著相當的興趣,若你也有興趣,也可從《圖解圖樣設計》這本書入門;

其實對王氏磚做些變化,也有可能從從範本拼接塊中自動擷取規則,若有興趣,我們可以參考〈Wang Tiles for Image and Texture Generation〉

拼接有趣的地方在於,其中不單只是程式演算──有限的範本卻有著無限的可能,更多是數學的成份,這是其中令人著迷的地方。

或許真正令人著迷的地方在於,程式與數學的結合,總是能令人訝異——感嘆不同的時空中,一直有著有許多驚人的想法誕生吧!

作者簡介

 

報名台灣唯一超規格資安盛會

 


熱門新聞

Advertisement