As I mentioned previously, last week at the JSOxford Code Retreat we spent a lot of time (all the time) developing Conway's Game of Life in various ways. As the code retreat was focusing on different coding methods and perfecting code rather than producing something that works I never got a fully working version. So last night I sat down and got to it!

About

Conway's Game of Life is a 0-player turn based simulation of life. The "game" follows some simple rules to update its cells on a board, crudely imitation evolution and life.

Rules

The rules of the game are as follows:

Any live cell with fewer than two live neighbours dies, as if caused by under-population.

Any live cell with two or three live neighbours lives on to the next generation.

Any live cell with more than three live neighbours dies, as if by overcrowding.

Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Wikipedia - http://en.wikipedia.org/wiki/Conway's_Game_of_Life

Approach

As we learnt last week, there are two ways to go about storing the game data (the state of the cells). The simple, and possibly naïve, way is to store a 2 dimensional array containing the state of every cell on the game board. The other is to only store a collection of live cells with their X and Y locations.

2D array

Storing the cell data in a two dimensional array is pretty simple.


var gameBoard = [
	[true, false, false, true, false],
	[true, false, false, true, false],
	[true, false, false, true, false],
	[true, false, false, true, false],
	[true, false, false, true, false]
];

The key thing to remember when approaching it this way is that the game board array must be cloned first before updating the cells. This is because all cells must be updated simultaneously so looping over and updating cell-by-cell would cause incorrect updating as you go through.

While this is the simplest approach, and the way we attempted when writing it out on paper, it doesn't scale very well. As the game is supposed to be infinite in size the array could very easily get too large for memory and cause the game to crash. This can be avoided by limiting the array to bounding dimensions.

Collection of Live Cells

The more scalable approach involves only storing the positions of the live cells. As all rules are based around the presence of live cells, the next iteration of cells can be calculated from this list.


var gameBoard = [
	{ x: 3, y: 5},
	{ x: 8, y: 2},
	{ x: 13, y: 5},
	{ x: 5, y: 9},
	{ x: 9, y: 10}
];

This is the approach I used last night. I have struggled on effectively calculating new cells to be "born", having resulted in iterating over all cells, checking if they are dead and then counting their live neighbours. This obviously goes against the infinite game board idea so if anyone has some suggestions on how to improve it you can Tweet @Marcus_Noble_ or fork my gist.

Final Code


var cells = [];
var boardWidth = 20;
var boardHeight = 20;
var intervalID;

function init(){
	var cell = $('').addClass('cell');
	var row = $('').addClass('row');
	var board = $('#gameBoard');
	var currentRow, i, j, newCell;

	$('#gameBoard').empty().on('click', function(){
		clearInterval(intervalID);
		init();
	});
	cells = [];

	for(i=0;i= 2 && neighbourCount <= 3){
			nextIteration.push(cells[i]);
		}
	}
	for(i=1;i<=boardHeight;i++){
		for(j=1;j<=boardWidth;j++){
			deadCell = {x:j,y:i};
			if(!isAlive(deadCell) && countNeighbours(deadCell) === 3){
				nextIteration.push(deadCell);
			}
		}
	}
	cells = nextIteration;
	render();
}

function isAlive(cell){
	return (cells.filter(function(currentCell){
		return (currentCell.x === cell.x && currentCell.y === cell.y);
	}).length > 0);
}

function countNeighbours(cell){
	var x1 = cell.x-1,
		x2 = cell.x+1,
		y1 = cell.y-1,
		y2 = cell.y+1;

	var neighbours = cells.filter(function(possibleNeighbour){
		if(possibleNeighbour.x === cell.x && possibleNeighbour.y === cell.y){
			return false;
		}
		return (possibleNeighbour.x >= x1 && possibleNeighbour.x <= x2 && possibleNeighbour.y >= y1 && possibleNeighbour.y <= y2);
	});
	return neighbours.length;
}

init();

You can check out the final version or take a look at the gist.

As always, if you have any comments Tweet @Marcus_Noble_.

Updated 2014-07-22

With a little help from @danielthepope I have improved the code slightly to remove the fixed universe problem. Cells are now born based on live cells instead of iterating over the game board.


var cells = [];
var boardWidth = 20;
var boardHeight = 20;
var $board = $('#gameBoard');
var intervalID;

function init(){
	var cell = $('').addClass('cell');
	var row = $('').addClass('row');
	var currentRow, i, j, newCell;

	$('#gameBoard').empty().on('click', function(){
		clearInterval(intervalID);
		init();
	});
	cells = [];

	for(i=0;i= 2 && neighbourCount <= 3){
			nextIteration.push(cells[i]);
		}
		// For each cell that is alive, find its neighbours
		cellX = cells[i].x;
		cellY = cells[i].y;
		neighbours = [];
		neighbours.push({x:(cellX-1),y:(cellY-1)});
		neighbours.push({x:(cellX-1),y:cellY});
		neighbours.push({x:(cellX-1),y:(cellY+1)});
		neighbours.push({x:cellX,y:(cellY-1)});
		neighbours.push({x:cellX,y:(cellY+1)});
		neighbours.push({x:(cellX+1),y:(cellY-1)});
		neighbours.push({x:(cellX+1),y:cellY});
		neighbours.push({x:(cellX+1),y:(cellY+1)});
		for(j=0, neighbourLength=neighbours.length; j 0);
}

function countNeighbours(cell){
	var x1 = cell.x-1,
		x2 = cell.x+1,
		y1 = cell.y-1,
		y2 = cell.y+1;

	var neighbours = cells.filter(function(possibleNeighbour){
		if(possibleNeighbour.x === cell.x && possibleNeighbour.y === cell.y){
			return false;
		}
		return (possibleNeighbour.x >= x1 && possibleNeighbour.x <= x2 && possibleNeighbour.y >= y1 && possibleNeighbour.y <= y2);
	});
	return neighbours.length;
}

init();