無限隨機地圖生成 Wang Tiles
Wang Tiles ---------------- 在研究關於可用於地圖生成的 波函數坍縮 演算法(Wave Function Collapse，底下簡寫WFC)的時候，又看到關於 王式磚 的資料(Wang Tiles，底下簡寫WT)。跟WFC比起來，WT比較容易理解和實作，所以我就先根據WT的原理實作了一個無限隨機地圖生成的測試。 關於WT，這個 網站 有詳細的介紹，同時也有許多tilesets可以用來作為測試資源。WT是數學家發明的遊戲，主要概念是邊緣匹配的tile連通拚接。每一個矩形tile有4個邊和4個角，所以有2種拼法，一種是邊匹配的拼法，一種是角匹配的拼法。 邊匹配 2Edge --------------------- 以邊匹配的拼法為例，每一個矩形tile的4個邊裡面，每個邊如果用0或1表示不同顏色，則總共有2x2x2x2共16種不同的tile。如下圖，生成tilemap時，如果一個tileA的上方的tileB的下邊是1，則tileA的上邊必須也是1，才能連通。同理，右方的tileC的左邊是1的話tileA的右邊也要是1，等等。整個tilemap的每一個tile都符合這個規則，就是一個符合WT的tilemap。 生成隨機tilemap的方式不只一種，一個簡單的方法是從左到右從上到下，一個一個tile生成。每一個新tile生成時，針對它的上方及左方2個己生成的tile的邊建立連通狀態(上方tile的下邊是1則新tile的上邊也需為1，左方tile的右邊為1則新tile的左邊也需為1)，而新tile的右方及下方的邊則隨機選擇0或1。 如下圖，針對tileX的4個邊依序上右下左以2進制編碼為1,2,4,8，這樣在生成tilemap時可以使用bit運算操作方便判斷。 這樣16種tile的編號也同時是它的編碼。如tile0表示4個邊都是0，tile8表示左邊是1其餘3邊是0，tile13表示上左下邊是1右邊是0，等等。底下是生成邊匹配的tilemap的虛擬碼。 void gen2EdgeWangTilesmap(cx, cy) { foreach tile i of tilemap { tile = 0; if (tilemap[upper] & 4) { // Match upper edge.