前几天在LeetCode上面遇到这么一个题目:Game of Life,给定一个初始pattern,求其下一个状态。

然后今天闲的蛋疼又用Javascriptcanvas实现了一下,项目地址:https://github.com/netcan/gameOfLife,最后搞到博客上了,具体可看左栏。

操作方法:

  • 鼠标右键暂停
  • 鼠标中键清除所有细胞
  • 鼠标左键添加细胞,最好在暂停状态下添加。

生命游戏规则很简单,在一个棋盘上面格子有细胞,细胞只有2种状态:生(1)或死(0)。每个细胞周围最多有8个空位,有以下4条规则:

  • “人口过少”:任何活细胞如果活邻居少于2个,则死掉。
  • “正常”:任何活细胞如果活邻居为2个或3个,则继续活。
  • “人口过多”:任何活细胞如果活邻居大于3个,则死掉。
  • “繁殖”:任何死细胞如果活邻居正好是3个,则活过来。

这里我随机生成一个初始棋盘,然后运行一遍生命游戏,将其绘制出来,以此循环。考虑到节省空间,我把下一个状态存到棋盘的第二比特位上面,然后右移得到下一个状态。

最终代码如下:


var ctx = document.getElementById('canvas').getContext("2d");
var bw = 800, bh = 600; // 画布宽、高
var d = 15; // 格子大小

function randomColor() {
    return "#"+(Math.round((1<<24)*Math.random())).toString(16);
}

function initBoard() {
    // 初始化格子
    for(var x = 0; x<=bw; x+=d) {
        ctx.moveTo(x, 0);
        ctx.lineTo(x, bh);
    }
    for(var y = 0; y<=bh; y+=d) {
        ctx.moveTo(0, y);
        ctx.lineTo(bw, y);
    }
}

function drawBoard(board, m, n) {
    // 绘制格子
    for(var i=0; i < m; ++i) {
        for(var j = 0; j < n; ++j) {
            ctx.fillStyle = randomColor();
            if(board[i][j] & 0x1)
                ctx.fillRect(i*d, j*d, d, d);
            else
                ctx.clearRect(i*d, j*d, d, d);
        }
    }
    ctx.stroke();
}

function getNeighbors(board, x, y, m, n) {
    var cnt = 0;
    for(var i=x-1; i<=x+1; ++i)
        for(var j=y-1; j<=y+1; ++j)
            if(i>=0 && j>=0 && i<m && j<n) {
                if((i != x || j != y)) cnt += board[i][j] & 0x1;
            }
    return cnt;
}

function gameOfLife(board, m, n) {
    for (var i = 0; i < m; ++i)
        for (var j = 0; j < n; ++j) {
            var nebs = getNeighbors(board, i, j, m, n);
            // console.log("("+i+", "+j + "): " + nebs);
            if(nebs == 2) board[i][j] |= (board[i][j] & 0x1) << 1; // 保持不变
            else if(nebs == 3) board[i][j] |= 0x2; // 增生
            else board[i][j] &= 0x1; // 死亡
        }

    for (var i = 0; i < m; ++i)
        for (var j = 0; j < n; ++j)
            board[i][j] >>= 1;
}


function run() {
    // 初始化数组
    if(typeof this.init == 'undefined') {
        board = [];
        m = parseInt(bw/d);
        n = parseInt(bh/d);
        for(var i = 0; i < m; ++i) {
            board[i] = [];
            for(var j = 0; j < n; ++j)
                board[i][j] = Math.round(Math.random());
                // board[i][j] = 0;
        }
        initBoard();
        this.init = true;
    }

    gameOfLife(board, m, n);
    drawBoard(board, m, n);
}

setInterval("run()", 400);