Wave Function Collapse（三）

在〈Wave Function Collapse（三）〉中完成了 WaveFunction，用來提供、操作地圖上各個位置的疊加狀態資訊，接著該來進行拼接塊的篩檢了，首先，要從範例地圖上，確定指定的位置拼接塊與鄰居間的相容性：

// 鄰居的方向
function neighborDirs(x, y, width, height) {
    const dirs = [];
    if(x > 0) { 
        dirs.push([-1, 0]); // 左
    }
    if(x < width - 1) {
        dirs.push([1, 0]);  // 右 
    }
    if(y > 0) {
        dirs.push([0, -1]); // 上
    }
    if(y < height - 1) {
        dirs.push([0, 1]);  // 下
    }

    return dirs;
}

function neighborCompatibilities(sample, x, y) {
    const width = sample[0].length;
    const height = sample.length;
    const me = sample[y][x];
    return neighborDirs(x, y, width, height).map(dir => {
        const nbrTile = sample[y + dir[1]][x + dir[0]];
        return `${me},${nbrTile},${dir}`;
    });
}

相容性資訊是由目前拼接塊類型、鄰居拼接塊類型與鄰接方向組成，採用字串的原因在於這個資訊會收集至 Set，JavaScript 標準 API 提供的 Set 在判斷是否重複上，只能處理基本型態及參考（reference），基本上相容性資訊的字串組成是不會重複的，因此採用字串是一個方式。

接著，定義一個函式從範例地圖取得全部的相容資訊：

function compatibilitiesOfTiles(sample) {
    const height = sample.length;
    const width = sample[0].length;
    const compatibilities = new Set();
    for(let y = 0; y < height; y++) {
        for(let x = 0; x < width; x++) {
            neighborCompatibilities(sample, x, y).forEach(c => compatibilities.add(c));         
        }
    }
    return compatibilities;
}

為了便於輸出地圖，來設計一個 TileMap，可以指定輸出地圖的寬、高與範例地圖：

class TileMap {
    constructor(width, height, sample) {
        this.width = width;
        this.height = height;   
        this.compatibilities = compatibilitiesOfTiles(sample);
        this.waveFunction = new WaveFunction(width, height, weightsOfTiles(sample));
    }

    generate() {
        while(!this.waveFunction.isAllCollapsed()) {
            const {x, y} = this.waveFunction.coordinateOfMinEntropy();
            this.waveFunction.collapse(x, y);
            this.propagate(x, y);
        }
        return collapsedTiles(this.waveFunction);
    }

    ...
}

function collapsedTiles(waveFunction) {
    const tiles = [];
    for(let y = 0; y < waveFunction.height; y++) {
        const row = [];
        for(let x = 0; x < waveFunction.width; x++) {
            row.push(waveFunction.getEigenstates(x, y)[0]);
        }
        tiles.push(row);
    }
    return tiles;
}

generate 方法用來產生地圖，流程很簡單，看看地圖各位置的疊加狀態是否都塌縮了，若否就找出最小熵值位置進行塌縮，然後傳播塌縮資訊，當全部位置都塌縮了，取得每個位置留下的唯一狀態傳回。

接著要來處理傳播，直接看註解中的說明吧！

class TileMap {
    ...
    propagate(x, y) {
        // 從指定的位置開始
        const stack = [{x, y}];
        while(stack.length > 0) {
            // 傳播這個位置的塌縮
            const currentCoord = stack.pop();
            // 這個位置目前剩餘的拼接塊
            const currentTiles = this.waveFunction.getEigenstates(currentCoord.x, currentCoord.y);
            // 對於每一個鄰居
            for(let dir of neighborDirs(currentCoord.x, currentCoord.y, this.width, this.height)) {
                // 鄰居座標
                const nbrX = currentCoord.x + dir[0];
                const nbrY = currentCoord.y + dir[1];
                // 鄰居擁有的拼接塊
                const nbrTiles = this.waveFunction.getEigenstates(nbrX, nbrY);
                // 鄰居與我不相容的拼接塊
                const notCompatibleNbrTiles = nbrTiles.filter(nbrTile => notCompatibleNbrTile(this, currentTiles, nbrTile, dir));
                // 有不相容的拼接塊的話
                if(notCompatibleNbrTiles.length !== 0) {
                    // 將鄰居不相容的拼接塊移除
                    this.waveFunction.remove(nbrX, nbrY, notCompatibleNbrTiles);
					// 拼接是有可能失敗的，失敗的話，最簡單的處理方式就是再來一次 XD
					if(this.waveFunction.getEigenstates(nbrX, nbrY).length == 0) {
						throw new Error('拼接失敗，請重試！');
					}
                    // 鄰居加入傳播行列
                    stack.push({x: nbrX, y: nbrY});
                }
            }
        }
    }

    // 確定兩個拼接塊間是否相容
    checkCompatibilities(tile1, tile2, direction) {
        return this.compatibilities.has(`${tile1},${tile2},${direction}`);
    }
}

// 鄰居與我不相容的拼接塊
function notCompatibleNbrTile(tileMap, currentTiles, nbrTile, dir) {
    return !currentTiles.some(tile => tileMap.checkCompatibilities(tile, nbrTile, dir));   
}

接著就是把 WaveFunction、TileMap 組合起來，輸出地圖囉！以下是完整範例：

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']
];

const imgs = new Map();

function preload() {
    const types = ['S', 'L', 'C0', 'C1', 'C2', 'C3', 'CE', 'CW', 'CS', 'CN'];
    for(let type of types) {
        imgs.set(type, loadImage(`images/${type}.png`));
    }
}

function setup() {
    createCanvas(300, 300);
    noStroke();
    noLoop();
}

function draw() {
    background(220);
    const w = 10;
    const tileMap = new TileMap(width / w, height / w, sample);
    const output = tileMap.generate();

    for(let y = 0; y < output.length; y++) {
        for(let x = 0; x < output[y].length; x++) {
            image(imgs.get(output[y][x]), x * w, y * w, w, w);
        }
    }
}

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;
}

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;
}

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));
    }

    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;
            }
        }
    }

    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() {
        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;
    }
}


function neighborDirs(x, y, width, height) {
    const dirs = [];
    if(x > 0) { 
        dirs.push([-1, 0]); // 左
    }
    if(x < width - 1) {
        dirs.push([1, 0]);  // 右 
    }
    if(y > 0) {
        dirs.push([0, -1]); // 上
    }
    if(y < height - 1) {
        dirs.push([0, 1]);  // 下
    }

    return dirs;
}

function neighborCompatibilities(sample, x, y) {
    const width = sample[0].length;
    const height = sample.length;
    const me = sample[y][x];
    return neighborDirs(x, y, width, height).map(dir => {
        const nbrTile = sample[y + dir[1]][x + dir[0]];
        return `${me},${nbrTile},${dir}`;
    });
}


function compatibilitiesOfTiles(sample) {
    const height = sample.length;
    const width = sample[0].length;
    const compatibilities = new Set();
    for(let y = 0; y < height; y++) {
        for(let x = 0; x < width; x++) {
            neighborCompatibilities(sample, x, y).forEach(c => compatibilities.add(c));         
        }
    }
    return compatibilities;
}

class TileMap {
    constructor(width, height, sample) {
        this.width = width;
        this.height = height;   
        this.compatibilities = compatibilitiesOfTiles(sample);
        this.waveFunction = new WaveFunction(width, height, weightsOfTiles(sample));
    }

    generate() {
        while(!this.waveFunction.isAllCollapsed()) {
            const {x, y} = this.waveFunction.coordinateOfMinEntropy();
            this.waveFunction.collapse(x, y);
            this.propagate(x, y);
        }
        return collapsedTiles(this.waveFunction);
    }

    propagate(x, y) {
        const stack = [{x, y}];
        while(stack.length > 0) {
            const currentCoord = stack.pop();
            const currentTiles = this.waveFunction.getEigenstates(currentCoord.x, currentCoord.y);
            for(let dir of neighborDirs(currentCoord.x, currentCoord.y, this.width, this.height)) {
                const nbrX = currentCoord.x + dir[0];
                const nbrY = currentCoord.y + dir[1];
                const nbrTiles = this.waveFunction.getEigenstates(nbrX, nbrY);
                const notCompatibleNbrTiles = nbrTiles.filter(nbrTile => notCompatibleNbrTile(this, currentTiles, nbrTile, dir));
                if(notCompatibleNbrTiles.length !== 0) {
                    this.waveFunction.remove(nbrX, nbrY, notCompatibleNbrTiles);
					if(this.waveFunction.getEigenstates(nbrX, nbrY).length == 0) {
						throw new Error('拼接失敗，請重試！');
					}
                    stack.push({x: nbrX, y: nbrY});
                }
            }
        }
    }

    checkCompatibilities(tile1, tile2, direction) {
        return this.compatibilities.has(`${tile1},${tile2},${direction}`);
    }
}

function collapsedTiles(waveFunction) {
    const tiles = [];
    for(let y = 0; y < waveFunction.height; y++) {
        const row = [];
        for(let x = 0; x < waveFunction.width; x++) {
            row.push(waveFunction.getEigenstates(x, y)[0]);
        }
        tiles.push(row);
    }
    return tiles;
}

function notCompatibleNbrTile(tileMap, currentTiles, nbrTile, dir) {
    return !currentTiles.some(tile => tileMap.checkCompatibilities(tile, nbrTile, dir));   
}