趣拼王氏磚

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

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

王氏磚的原理

王氏磚（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〉。

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

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