在〈Wave Function Collapse（一）〉認識了 Wave Function Collapse 演算的基本原理後，接下來就是看看程式如何實作了，首先需要準備一張範例地圖，例如：
這張範例圖若根據〈Wave Function Collapse（一）〉中的拼接塊標示，整理為二維陣列，會是以下的資料：
const sample = [
['S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S'],
['S', 'S', 'C0', 'CN', 'CN', 'CN', 'CN', 'CN', 'CN', 'CN', 'C3', 'S', 'S'],
['S', 'S', 'CW', 'L', 'L', 'L', 'L', 'L', 'L', 'L', 'CE', 'S', 'S'],
['S', 'S', 'CW', 'L', 'L', 'L', 'L', 'L', 'L', 'L', 'CE', 'S', 'S'],
['S', 'S', 'CW', 'L', 'L', 'L', 'L', 'L', 'L', 'L', 'CE', 'S', 'S'],
['S', 'S', 'CW', 'L', 'L', 'L', 'L', 'L', 'L', 'L', 'CE', 'S', 'S'],
['S', 'S', 'CW', 'L', 'L', 'L', 'L', 'L', 'L', 'L', 'CE', 'S', 'S'],
['S', 'S', 'CW', 'L', 'L', 'L', 'L', 'L', 'L', 'L', 'CE', 'S', 'S'],
['S', 'S', 'CW', 'L', 'L', 'L', 'L', 'L', 'L', 'L', 'CE', 'S', 'S'],
['S', 'S', 'C1', 'CS', 'CS', 'CS', 'CS', 'CS', 'CS', 'CS', 'C2', 'S', 'S'],
['S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S', 'S']
];
若單一拼接塊的權重是 1，範例地圖中有多少同類型的拼接塊，就代表輸出的地圖，必須參考的權重有多少，那麼可以實作出以下的權重計算函式：
function weightsOfTiles(sample) {
const weights = new Map();
for(let y = 0; y < sample.length; y++) {
for(let x = 0; x < sample[y].length; x++) {
const tile = sample[y][x];
if(weights.get(tile) === undefined) {
weights.set(tile, 0);
}
weights.set(tile, weights.get(tile) + 1);
}
}
return weights;
}
透過這個權重計算函式，可以得到範例地圖中每個拼接塊加總後的權重如下：
C0: 1
C1: 1
C2: 1
C3: 1
CW: 7
CS: 7
CE: 7
CN: 7
S : 62
L : 49
看來這是個海洋佔多數面積、陸地次之的範例地圖，輸出的地圖也應該要是海洋佔多數面積、陸地次之。
接下來，需要有個可以初始輸出地圖中各位置疊加狀態的函式，因為計算後的權重會儲存在 Map，其中鍵就是使用到的拼接塊類型，使用該 Map 就可以初始輸出地圖的疊加狀態：
function initialEigenstates(width, height, weights) {
const eigenstates = [];
for(let y = 0; y < height; y++) {
const row = [];
for(let x = 0; x < width; x++) {
row.push(Array.from(weights.keys()));
}
eigenstates.push(row);
}
return eigenstates;
}
從〈Wave Function Collapse（一）〉可以知道，從任何某個已塌縮的位置開始，都可以藉由傳播來擴充輸出地圖，從而產生無盡拼接的地圖，然而因為這邊只是做個範，為了簡化，這邊還是指定了輸出地圖的大小，在這邊可以看到，每個位置的疊加狀態，是由該位置的一組類型與權重決定。
各位置的疊加狀態儲存在二維陣列中，存取時的索引 eigenstates[y][x] 代表了座標 (x, y)，之後會一直處理這個二維陣列，因此封裝為一個類別是個不錯的選擇：
class WaveFunction {
constructor(width, height, weights) {
this.width = width;
this.height = height;
this.weights = weights;
this.eigenstates = initialEigenstates(width, height, weights);
}
getEigenstates(x, y) {
return this.eigenstates[y][x];
}
isAllCollapsed() {
for(let row of this.eigenstates) {
if(row.some(states => states.length > 1)) {
return false;
}
}
return true;
}
remove(x, y, removedStates) {
const states = this.eigenstates[y][x];
this.eigenstates[y][x] = states.filter(state => !removedStates.includes(state));
}
...
}
WaveFunction 接受輸出地圖的大小以及範例地圖的拼接塊權重關係，為了便於存取某位置的疊加狀態，定義了 getEigenstates 方法；為了判斷地圖中每個位置是否都塌縮為一個狀態，定義了 isAllCollapsed 方法，單純地判斷是不是有某位置的狀態數量超過 1；由於塌縮會傳播，為了移除傳播過程中不相容的疊加狀態，定義了 remove 方法，removedTiles 會被濾掉，剩餘的狀態再指定回 (x, y) 位置。
現在要選擇將某位置的疊加狀態，塌縮為一個狀態，只是這一個狀態該怎麼選擇呢？單純地從疊加狀態中隨機選出一個，顯然就無法輸出類似範例地圖的結果，以範例地圖海洋居多、陸地次之為例，若疊加狀態中有海洋拼接塊，應該給予較高選中的機會。
可以先找出指定位置的疊加狀態與權重關係，先計算出總權重，然後取個 0 到總權重間的值作為閥值，接著總權重逐一減去各狀態的權重，直到低於閥值：
class WaveFunction {
...
collapse(x, y) {
const statesWeights = new Map(
Array.from(this.weights.keys())
.filter(state => this.eigenstates[y][x].includes(state))
.map(state => [state, this.weights.get(state)])
);
const totalWeights = Array.from(statesWeights.values()).reduce((r, w) => r + w);
let threshold = random() * totalWeights;
for(let [state, weight] of statesWeights) {
threshold -= weight;
if(threshold < 0) {
this.eigenstates[y][x] = [state];
return;
}
}
}
...
}
若疊加狀態中有權重較大的狀態，減去其權重後，有較大的機會低於閥值，說是較大的機會是因為，總權重還是乘上了 0 到 1 的隨機值，若調整閥值的上下界，也就是調整 random 的上下界引數，就會影響狀態的選擇，例如，使用 random(0.8, 1) 的話，因為閥值高，減去小權重後，很有可能就低於閥值，這表示你可能產生較多小或零落的島嶼。
在〈Wave Function Collapse（一）〉談到，選擇哪個位置，令其塌縮成一個狀態，可以是疊加的狀態數、權重或是其他計算方式，在 Maxim Gumin 的 WaveFunctionCollapse 中採用的是具有最小 Shannon entropy 的位置，Shannon entropy 是？
entropy 源於熱力學，我試著從科普的角度調查後的認識是，它本為熱量除以溫度的商數，entropy 中文常譯為熵，本無此字，物理學家胡剛復在「商」字旁加上「火」而創造此字以便於聯想；物理學家 Ludwig Boltzmann 發現，系統的熵跟構成熱力學性質的微觀狀態數量有關（例如，容器中氣體分子的位置及動量構成之狀態數量），也就是說，熵是個跟狀態有關的函數。
熵後來被作為系統混亂程度的度量，系統中的狀態數量越多，系統越混亂，例如在維基百科〈熵〉條目中有個丟硬幣的比喻，若有 10 個硬幣，丟硬幣時得到最有規律的狀態是 10 個都為正面或反面，硬幣排列上只會構成兩種狀態，若是最混亂的情況，有 5 個正面、5 個反面，硬幣排列上就會有 252 種。
Claude Shannon 將熵引入了資訊理論（Information theory）的領域，作為不確定性的量度，熵越大表示不確定性越大，根據維基百科〈Entropy (information theory)〉條目，Shannon 熵的計算方式是：
其中 X 是變數，可能的值為 (x1, x2, …., Xn)，P(xi) 是 xi 出現的機率，對數的底 b 視使用的 Shannon 熵單位而定，單位為 bits 時使用 2，nats 使用 e，bans 使用 10。
例如，Shannon 熵常用在計算密碼強度，熵值越大表示密碼組合的混亂程度越大，也就越難以組合出正確的密碼，若允許使用的字元有 N 個，密碼長度為 L，密碼的可能組合就是 1/NL，某組密碼出現的機率是 1/NL，對應至以上公式，n 就是 1/NL，P(xi) 是 1/NL，採用 bits 為 Shannon 熵單位，b 是 2，整理一下公式後，密碼強度的計算公式就是 Entropy as a measure of password strength 中列出的：
在 Maxim Gumin 的 WaveFunctionCollapse 中，Comments 談到了採用 Shannon 熵的理由，是來自於他觀察到，人們解決這類繪圖問題時，經常採用了最小熵值的概念。
例如，〈Wave Function Collapse（一）〉談到，若某位置的拼接塊數量少，其周圍的拼接塊數量也不會多，選擇該位置塌縮成一個拼接塊，在傳播時對各位置的拼接塊衝擊較小，也就是傳播過程，各位置的拼接塊可以保有較多的選擇性，後續選擇某個拼接塊，發生死胡同的可能性會比較低。
也就是說，一個方式是選擇剩餘類型數量少的位置，這也可以理解為，類型數量少的位置，代表它受到周圍位置的限制較多，也就是它接收到周圍位置的資訊較多，才會擁有較少的類型。
不過，類型的數量不是狀態，畢竟在數量相同的情況下，有可能擁有不同的權重加總，然而反之，權重加總也不是狀態的全部，畢竟相同權重加總下，也可能有不同的類型數量，最好的方式是兩者都考慮，記得一開始說的嗎？每個位置的疊加狀態，是由該位置的一組類型與權重決定。
Shannon 熵是個與狀態有關的值，公式在計算過程考量了類型數量，若將權重設計進去來求得熵值，就可以作為疊加狀態的代表，也就是可以尋找最小熵值的位置來塌縮，WaveFunctionCollapse 中就是採用權重作為 Shannon 熵的計算依據，若某位置狀態總權重是 sumOfWeights，某類型的權重為 wi，該位置出現該 wi 權重的類型機率 P(wi) 是 wi / sumOfWeights，套用到 Shannon 熵公式，整理一下公式，如果 sumOfWeightLogWeights 代表每個 wi * log(wi) 的加總，那麼最後的公式會是：
log(sumOfWeights) - (sumOfWeightLogWeights / sumOfWeights)
將之實作為程式碼就會是：
class WaveFunction {
...
entropy(x, y) {
let sumOfWeights = 0;
let sumOfWeightLogWeights = 0;
for(let opt of this.getEigenstates(x, y)) {
const weight = this.weights.get(opt);
sumOfWeights += weight;
sumOfWeightLogWeights += weight * log(weight);
}
return log(sumOfWeights) - (sumOfWeightLogWeights / sumOfWeights);
}
...
}
為了方便取得具有最小熵值的位置，來定義一個 coordinateOfMinEntropy 方法：
class WaveFunction {
...
coordinateOfMinEntropy() {
let entropy;
let entropyCoord;
for(let {x, y} of this.notCollapsedCoords()) {
// 加上一點小小的擾動，增加一點多樣性
const noisedEntropy = this.entropy(x, y) - (random() / 1000);
if(entropy === undefined || noisedEntropy < entropy) {
entropy = noisedEntropy;
entropyCoord = {x, y};
}
}
return entropyCoord;
}
// 取得尚未完全塌縮成一個狀態的位置
notCollapsedCoords() {
const coords = [];
for(let y = 0; y < this.height; y++) {
for(let x = 0; x < this.width; x++) {
if(this.getEigenstates(x, y).length !== 1) {
coords.push({x, y});
}
}
}
return coords;
}
}
在實作中可以看到 noisedEntropy，將取得的熵值加上了一點小擾動，這是根據 WaveFunctionCollapse 的範例原始碼而來，應該是為了增加一些輸出地圖的多樣性，不做這種擾動，基本上也是可以輸出隨機地圖就是了。
到這邊為止，完成了 WaveFunction 的定義，它只用來提供或更新地圖上各位置的狀態，至於怎麼找出拼接塊的相容性、傳播等，會交由另一個 TileMap 來處理，這就留在下一篇文件再來談…