实现一个生命游戏

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

然后今天闲的蛋疼又用 Javascript 和canvas实现了一下，项目地址：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);