k8w.io
算法实现:将MxN的方格,分割成拼图
2018-11-09作者:k8w

将MxN的方格,分割成俄罗斯方块式的拼图。
使用TypeScript, 在Cocos Creator的实现。

const { ccclass, property } = cc._decorator;

type Cell = [number, number];
type Block = Cell[];

@ccclass
export default class Random extends cc.Component {

    @property(cc.Prefab)
    prefabBox: cc.Prefab = null as any;

    generateRandomBlocks(width: number, height: number, minBlockCells = 2, maxBlockCells = 4) {
        // Cell数组 用于判断Cell的状态
        // 状态:0-Cell空闲  1-已经被归到Block
        let cells = Array.from({ length: width }, () => Array.from({ length: height }, () => 0));
        let output: Block[] = [];

        // 从0,0开始,遍历Cell
        for (let i = 0; i < width; ++i) {
            for (let j = 0; j < height; ++j) {
                // 已使用
                if (cells[i][j] === 1) {
                    continue;
                }

                // 未使用
                // 随机生成Cells数量 min~max
                let numCell = Math.random() * (maxBlockCells - minBlockCells) + minBlockCells + 1 | 0;
                let lastCell: Cell = [i, j];
                let block: Block = [lastCell];
                // 更新Cell状态
                cells[lastCell[0]][lastCell[1]] = 1;
                while (block.length < numCell) {
                    // 如果lastCell 四面八方都占满了 自动结束之                    
                    if (([
                        [lastCell[0] + 1, lastCell[1]],
                        [lastCell[0] - 1, lastCell[1]],
                        [lastCell[0], lastCell[1] + 1],
                        [lastCell[0], lastCell[1] - 1],
                    ] as Cell[]).every(v => !this._isCellValid(width, height, v) || cells[v[0]][v[1]] === 1)) {
                        break;
                    }

                    // 向随机方向扩展尝试
                    let nextCell: Cell = lastCell.slice() as [number, number];
                    // 随机一个方向
                    switch (Math.random() / 0.25 | 0) {
                        case 0:
                            // 上
                            nextCell[1] += 1;
                            break;
                        case 1:
                            // 右
                            nextCell[0] += 1;
                            break;
                        case 2:
                            // 下
                            nextCell[1] -= 1;
                            break;
                        case 3:
                            // 左
                            nextCell[0] -= 1;
                            break;
                    }

                    // Cell不合法
                    if (!this._isCellValid(width, height, nextCell)) {
                        continue;
                    }

                    // 如果这个Cell已经被占用 continue
                    if (cells[nextCell[0]][nextCell[1]] === 1) {
                        continue;
                    }

                    // 如果没有被占用,归到这个Cell里
                    block.push(nextCell);
                    // 更新Cell状态
                    cells[nextCell[0]][nextCell[1]] = 1;

                    lastCell = nextCell;
                }
                output.push(block);
            }
        }

        // 把孤立Cell合并到相邻的Block去
        for (let i = output.length - 1; i > -1; --i) {
            // 这是一个孤立的Block
            if (output[i].length === 1) {
                // 遍历output,寻找相邻的Block
                for (let block of output) {
                    let hasMerged = false;
                    for (let cell of block) {
                        // 排除自己
                        if (cell[0] === output[i][0][0] && cell[1] === output[i][0][1]) {
                            continue;
                        }

                        // 相邻 合并之
                        if (this._isCellNear(cell, output[i][0])) {
                            block.push(output[i][0]);
                            hasMerged = true;
                            break;
                        }
                    }
                    if (hasMerged) {
                        break;
                    }
                }
                output.splice(i, 1);
            }
        }

        return output;
    }

    private _isCellValid(width: number, height: number, cell: Cell) {
        if (cell[0] < 0 || cell[1] < 0 || cell[0] > width - 1 || cell[1] > height - 1) {
            return false;
        }
        else {
            return true;
        }
    }

    private _isCellNear(cell1: Cell, cell2: Cell) {
        return cell1[0] === cell2[0] && Math.abs(cell1[1] - cell2[1]) === 1
            || cell1[1] === cell2[1] && Math.abs(cell1[0] - cell2[0]) === 1
    }

    start() {
        console.log('555')
        let result = this.generateRandomBlocks(8, 8);
        console.log('666', result)

        let blockIndex = 0;
        for (let block of result) {
            let color = cc.color(Math.random() * 255, Math.random() * 255, Math.random() * 255, 100);
            for (let cell of block) {
                let node = cc.instantiate(this.prefabBox);
                node.x = 42 * cell[0] + 200;
                node.y = 42 * cell[1] + 200;
                node.color = color;
                node.getChildByName('label').getComponent(cc.Label).string = blockIndex + '';
                this.node.addChild(node);
            }
            ++blockIndex;
        }

        // 做一些检测
        let cells: { [key: string]: any } = {};
        blockIndex = 0;
        for (let block of result) {
            for (let cell of block) {
                let cellString = cell[0] + '-' + cell[1];
                if (cells[cellString]) {
                    console.error('Cell 重复', cellString, blockIndex, cells[cellString])
                }
                cells[cellString] = blockIndex;
            }
            ++blockIndex;
        }
    }

}
(正文完)
留言(0条)
发表新留言
您的大名:
必填
电子邮箱:
不公开,仅用于向你发送回复