Tutorial: Conway’s Game of Life in D3


See the final version here.

This is an example of Conway’s Game of Life, built in D3. According to Wikipedia:

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.[1]The “game” is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.

There are only 4 rules in the Game of Life:

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

    The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

    I’m sure there are multiple ways of implementing Conway’s Game of Life, but this is just one of them. We start by declaring a few variables:

    			var ccx = 120, // cell count x
    				ccy = 30, // cell count y
    				cw = 5, // cellWidth
    				ch = 5,  // cellHeight
    				del = 100, // delay
    				xs = d3.scale.linear().domain([0,ccx]).range([0,ccx * cw]),
    				ys = d3.scale.linear().domain([0,ccy]).range([0,ccy * ch]),
    				states = new Array()
    

    The states variable will be used to hold the states of each cell: true for on and false for off. Next up, we’re going to fill the states array with data:

    d3.range(ccx).forEach(function(x) {
    	states[x] = new Array()
    	d3.range(ccy).forEach(function(y) {
    		states[x][y] = Math.random() > .8 ? true : false
    	})
    })
    

    This is a good example of the use of d3.range([start], stop, [step]) function which returns a range of number. We’re using only the stop argument, so in our case the first use of the range() function will generate an array of 0 (which is the default start) to 120, and uses the default step of 1. As you can see we’re building a 2-dimensional array here, so that we can easily access each state, for example states[0][0] to access the first state. We randomly set the state to either true or false.

    I have created the toGrid() function so that the 2-dimensional array is turned into an array of Objects, so that D3 can easily bind all the values to an SVG element (binding to the 2-dimensional array directly should also be possible, which I leave as an exercise for you at the moment…):

    			function toGrid(states) {
    				var g = []
    				for (x = 0; x < ccx; x++) {
    					for (y = 0; y < ccy; y++) {
    						g.push({"x": x, "y": y, "state": states[x][y]})
    					}
    				}
    				return g
    			}
    

    Now we initialize the visualization:

    			var vis = d3.select("body")
    				.append("svg:svg")
    				.attr("class", "vis")
    				.attr("width", window.width)
    				.attr("height", window.height)
    

    After that we create the initial state of the grid:

    vis.selectAll("rect")
    	.data(function() { return toGrid(states) })
      .enter().append("svg:rect")
    	.attr("stroke", "none")
    	.attr("fill", function(d) { return d.state ? "green" : "white" })
    	.attr("x", function(d) { return xs(d.x) })
    	.attr("y", function(d) { return ys(d.y) })
    	.attr("width", cw)
    	.attr("height", ch)
    

    Note that the data that is bound to svg:rect elements is the result from the toGrid() function. Also, there are multiple ways to show the on and off state of a cell, for instance using the visibility property. I chose to use the fill property in this case. It is either colored green or white (which is the background color) based on the state. This is all that’s needed to create the initial grid. Now comes the fun part: creating the new generations:

    			function createNewGeneration() {
    				var nextGen = new Array()
    
    				for (x = 0; x < ccx; x++) {
    					nextGen[x] = new Array()
    					for (y = 0; y < ccy; y++) {
    						var ti = y - 1 < 0 ? ccy - 1 : y - 1 // top index
    						var ri = x + 1 == ccx ? 0 : x + 1 // right index
    						var bi = y + 1 == ccy ? 0 : y + 1 // bottom index
    						var li = x - 1 < 0 ? ccx - 1 : x - 1 // left index
    
    						var thisState = states[x][y]
    						var liveNeighbours = 0
    						liveNeighbours += states[li][ti] ? 1 : 0
    						liveNeighbours += states[x][ti] ? 1 : 0
    						liveNeighbours += states[ri][ti] ? 1 : 0
    						liveNeighbours += states[li][y] ? 1 : 0
    						liveNeighbours += states[ri][y] ? 1 : 0
    						liveNeighbours += states[li][bi] ? 1 : 0
    						liveNeighbours += states[x][bi] ? 1 : 0
    						liveNeighbours += states[ri][bi] ? 1 : 0
    
    						var newState = false
    
    						if (thisState) {
    							newState = liveNeighbours == 2 || liveNeighbours == 3 ? true : false
    						} else {
    							newState = liveNeighbours == 3 ? true : false
    						}
    
    						nextGen[x][y] = newState
    					}
    				}
    
    				return nextGen
    			}
    

    This function implements the Game of Life rules mentioned earlier. We’re building a new 2-dimensional array here that will eventually be used to replace the value of the states variable. We’re determining the top, right, bottom and left index to use for each cell. If one of the index numbers would fall out of the range (greater than the length, or smaller than 0), then the index of the opposite side is used. For example, if we are currently at cell(0,5) (which means x = 0 and y = 5), then to calculate li (left index) we end up with index -1. This of course does not exist, so we use ccx.length - 1 instead, which is 199. This way all the cells will have a top, right bottom and left to work with. Next the number of liveNeighbours is calculated by summing up the number of true states of 8 neighbour cells. Finally the new state for this cell is calculate by actually applying the Game of Life rules. The new state is stored in the temporary array, which is being returned as the result of the function.

    The last part we need to do is to create new generations repeatedly and animate the grid accordingly:

    			function animate() {
    				states = createNewGeneration()
    				d3.selectAll("rect")
    					.data(toGrid(states))
    				  .transition()
    					.attr("fill", function(d) { return d.state ? "green" : "white" })
    					.delay(del)
    					.duration(0)
    			}
    
    			setInterval("animate()", del)
    

    This is done by the setInterval() Javascript function. We call the animate function with a delay of 100 milliseconds (the value of the del variable). The animate function itself is pretty straightforward. The value of the states variable is replaced with a new generation. Then all the rect elements are selected and the new generation is bound to these rectangles (note that again the 2-dimensional array is converted with the toGrid() function. After that we define the transition() we want to apply, and all we do is modify the fill property of each cell. Setting the delay to the del value as well seems to be working quite well. I guess this helps the browser to have enough time to calculate the new generation. We explicitly set the duration to 0 to override the default.

    That’s all there’s to it. I thought it would be more complex to build the Game of Life in D3, but it appears to be fairly straightforward. This code of course does require some calculation power from your browser, so just play around with the delay or grid size to get an optimal setting that works for you. Also, you can play with various other attributes to create interesting effects, for instance, using this for creating the grid gives a nice blurry effect:

    			vis.selectAll("rect")
    				.data(function() { return toGrid(states) })
    			  .enter().append("svg:rect")
    				.attr("stroke", "none")
    				.attr("fill", function(d) { return d.state ? "green" : "white" })
    				.attr("fill-opacity", .3)
    				.attr("x", function(d) { return xs(d.x) })
    				.attr("y", function(d) { return ys(d.y) })
    				.attr("width", function() { return 2 * cw })
    				.attr("height", function() { return 2 * ch })
    

    Enjoy!

    7 Comments

  5. August 26, 2011 - 14:46 | Permalink

    setInterval for animation loops is very unstable. If the processing for some reason takes longer than the set interval, the page crashes. You should take a look at this requestAnimationFrame shim by Paul Irish: http://paulirish.com/2011/requestanimationframe-for-smart-animating/

    With that running the animation loop, the size of the svg can be a lot bigger with the only risk being that the game of life runs slower, rather than crashing.

    I’m very much a novice myself, just trying to spread some good advice :)

    • August 26, 2011 - 14:56 | Permalink

      Hi, I must say that I haven’t had any troubles myself. Does it crash in every browser? Anyway, I didn’t know about requestAnimationFrame, but it looks really interesting. I’ll give it a try! Thanks for sharing!

      • Mike Bostock
        September 2, 2011 - 05:09 | Permalink

        D3 uses requestAnimationFrame internally. For example, if you use d3.timer instead of setInterval, you’ll get requestAnimationFrame in browsers that support it.

  6. October 27, 2011 - 07:24 | Permalink

    For the fun of it, I took to tweaking this code a bit, reformatting it as a github gist for bl.ocks.org and adding an interactive element (clicking in the simulation to attempt toggle a cell and see the consequences, if any, propagate):

    http://bl.ocks.org/1318699

  7. Leave a Reply

    Your email address will not be published. Required fields are marked *

    *

    You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>