Writing Conway’s Game of Life in JavaScript using TDD Pt.1

In this 3-part entry, we write Conway’s Game of Life in JavaScript using Test Driven Development.

Conway’s Game of Life is a relatively simple cellular automaton. The game consists of a board of undefined size and cells, which can be either alive or dead. There are four simple rules, which determine the board state after every update:

• If a living cell has less than two living neighbors, it dies
• If a living cell has more than three living neighbors, it dies
• If a living cell has exactly two or three living neighbors, it lives
• If a dead cell has exactly three living neighbors, it comes back to life

So, with all that out of the way, let’s start coding!

First, we create a project with the following structure:

project structure

As a test runner, we use karma, with the following config:


module.exports = function(config) {
  config.set({
    basePath: '',
    frameworks: ['jasmine'],
    files: [
      'app/*.js',
      'test/*.js'
    ],
    reporters: ['progress'],
    port: 9876,
    colors: true,
    logLevel: config.LOG_INFO,
    autoWatch:false, 
    browsers: ['PhantomJS'],
    captureTimeout: 60000,
    singleRun: false
  });
};

This is a very standard config. We can start karma using “karma start” and run tests using the “karma run” command. For further information on installing and configuring the karma test runner, check out it’s official documentation here.

For writing our unit tests, we will use Jasmine, as configured above. You can install the karma-jasmine plugin like this.

Now, let’s finally write some code!…but where to start? A Conway’s game consists of cells which are located somewhere on a (in this case) 2-dimensional board. We probably want to have some way to add cells to a board, in order to initialize the game properly.

First, the test:


  describe('addCell', function() {
 
   it('adds a cell to a board', function() {
     var board = new Board();
     var cell = new Cell(1, 1, true);
 
     board.addCell(cell);
 
     expect(board.cells.x1y1).toEqual(cell);
   });
 
 });

What’s happening here is that we create a “describe” block in order to organize our tests for improved code readability and within it our first unit test. In this test, we first do some setup, creating a board, a cell and adding the cell to the board. After that, we assert that the cell has indeed been added to the board in a certain way.

As you can see, we already made a design decision here, expecting a “cells” object within the board, containing the cell saved with a formatted identifier created from the cells coordinates.

The next step is to run the failing test and to make it pass.

First, we introduce the concept of a Board and of a Cell:


var Board = function() {
  this.cells = {}; 
};
 
var Cell = function(x, y) {
  this.x = x;
  this.y = y;
};

The board just holds a collection object called “cells” and the cell is just a value object for its coordinates on the board.


Board.prototype = {
  addCell: function(cell){
    this.cells[getCellRepresentation(cell.x, cell.y)] = cell;
  }
}
 
function getCellRepresentation (x, y) {
 return "x" + x + "y" + y; 
}

Here, we implement the “addCell” method, which just adds the passed in Cell object to the collection of cells, using an identifier containing the x and y coordinates of the cell (e.g.: x1y1 for the cell at x=1 and y=1). We use this concept of a “map” rather than an Array, because it may be advantageous to be able to directly reference each cell at a later point.

As a next step, we might want to calculate a cell’s neighbors. To do that, we need to have a way to get a cell at specified coordinates. First, a new test case:


  describe('getCellAt', function() {
 
   it('returns the cell at the provided coordinates', function() {
     var board = new Board();
     var cell = new Cell(1, 1, true);
 
     board.addCell(cell);
 
     expect(board.getCellAt(1, 1)).toEqual(cell);
   });
  });

Now, as the setup for both our test cases is the same (creating a board with a cell added to it), we can refactor it to a “beforeEach” method, which will get called before each test case:


  var board, cell; 
 
  beforeEach(function() {
    board = new Board();
    cell = new Cell(1, 1, true);
    board.addCell(cell);
  });

Now we can remove the setup code from the two test cases, which just leaves the “expect” clauses.

After running the failing test, we implement the “getCellAt” method as follows:


Board.prototype = {
…
getCellAt: function(x, y) {
    return this.cells[getCellRepresentation(x, y)];  
  }
}

We did all the heavy lifting for this method within the “addCell” method, so that now we just have to return the value at the specified coordinates.

The next step on our journey to calculating the living neighbors of a cell is to iterate through the whole neighborhood of a cell (-1, 0, 1) and count the cells who are alive. This is a more complex problem, so we will take the zero, one, many approach of testing. First, a test case for the case of zero living cells:


  describe('getAliveNeighbors', function() {
   it('returns 0 if there are no other cells', function() {
    expect(board.getAliveNeighbors(cell)).toEqual(0);
   });
  });

We implement the simplest thing that will make the test pass:


  getAliveNeighbors: function(cell) {
    return 0;
  }

…and then write another test case:


 it('returns 1 if there is one alive cell next to the cell', function() {
  var neighborCell = new Cell(0, 1, true);
  board.addCell(neighborCell);
  expect(board.getAliveNeighbors(cell)).toEqual(1);
 });

In this test case, we add another cell to the board and expect our method to return 1. In order to do that, we need to extend the Cell by the concept of an internal state (to determine if a cell is alive or dead).

First, extend the Cell:


var Cell = function(x, y, alive) {
  this.x = x;
  this.y = y;
  this.alive = alive;
};
 
Cell.prototype = {
  isAlive : function() {
    return this.alive;
  }
};

then, generalize the method to make the test pass:


  getAliveNeighbors: function(cell) {
    var x = cell.x;
    var y = cell.y;
    var aliveCells = 0;
 
    for (var i = -1; i < 2; i++) {
      for(var j = -1; j < 2; j++) {
        if(i === 0 && i == j) {
          continue;
        }
        var currentCell = this.getCellAt(x + i, y + j);
 
        if(currentCell && currentCell.isAlive()) {
          aliveCells++;
        }
      }
    }
 
    return aliveCells;
  }

The implementation is actually pretty simple, first we iterate through the whole neighborhood of the center cell (all cells directly next to it, with x and y values of -1, 0 and 1 added to the center cell’s x and y). We also want to ignore the center cell (x+0, y+0). Finally, we count the living cells and return that number.

This makes the test pass. We are pretty confident that this implementation is solid, but we only covered the “zero” and “one” test cases, so we will add another “many” test case just to be sure:


    it('returns 8 if there are 8 neighbors available', function() {
      board.addCell(new Cell(0, 1, true));
      board.addCell(new Cell(0, 2, true));
      board.addCell(new Cell(0, 0, true));
      board.addCell(new Cell(2, 1, true));
      board.addCell(new Cell(1, 0, true));
      board.addCell(new Cell(2, 2, true));
      board.addCell(new Cell(1, 2, true));
      board.addCell(new Cell(2, 0, true));
 
      expect(board.getAliveNeighbors(cell)).toEqual(8);
    });

…and an inverse, because we really want to be sure this works for all possible cases:


    it('returns 1 if there are 7 dead cells next available', function() {
      board.addCell(new Cell(0, 1, true));
      board.addCell(new Cell(0, 2, false));
      board.addCell(new Cell(0, 0, false));
      board.addCell(new Cell(2, 1, false));
      board.addCell(new Cell(1, 0, false));
      board.addCell(new Cell(2, 2, false));
      board.addCell(new Cell(1, 2, false));
      board.addCell(new Cell(2, 0, false));
 
      expect(board.getAliveNeighbors(cell)).toEqual(1);
    });

As expected, both tests pass and we are now able to successfully calculate a cell’s living neighbors, which is a core part of calculating the next state of the whole board.

This concludes part 1 of this series. In the next part, we will look at implementing the four rules mentioned above, in order to consequently be able to calculate new board states.

Full source code of this example so far:

Tests: (spec.js)


describe('Conways Game of Life', function() {
 
  var board, cell; 
 
  beforeEach(function() {
    board = new Board();
    cell = new Cell(1, 1, true);
    board.addCell(cell);
  });
 
  describe('addCell', function() {
   it('adds a cell to a board', function() {
     expect(board.cells.x1y1).toEqual(cell);
    });
  });
 
  describe('getCellAt', function() {
 
   it('returns the cell at the provided coordinates', function() {
      expect(board.getCellAt(1, 1)).toEqual(cell);
    });
  });
 
  describe('getAliveNeighbors', function() {
 
    it('returns 0 if there are no other cells', function() {
      expect(board.getAliveNeighbors(cell)).toEqual(0);
    });
 
    it('returns 1 if there is one alive cell next to the cell', function() {
      var neighborCell = new Cell(0, 1, true);
      board.addCell(neighborCell);
 
      expect(board.getAliveNeighbors(cell)).toEqual(1);
    });
 
    it('returns 8 if there are 8 neighbors available', function() {
      board.addCell(new Cell(0, 1, true));
      board.addCell(new Cell(0, 2, true));
      board.addCell(new Cell(0, 0, true));
      board.addCell(new Cell(2, 1, true));
      board.addCell(new Cell(1, 0, true));
      board.addCell(new Cell(2, 2, true));
      board.addCell(new Cell(1, 2, true));
      board.addCell(new Cell(2, 0, true));
 
      expect(board.getAliveNeighbors(cell)).toEqual(8);
    });
 
    it('returns 1 if there are 7 dead cells next available', function() {
      board.addCell(new Cell(0, 1, true));
      board.addCell(new Cell(0, 2, false));
      board.addCell(new Cell(0, 0, false));
      board.addCell(new Cell(2, 1, false));
      board.addCell(new Cell(1, 0, false));
      board.addCell(new Cell(2, 2, false));
      board.addCell(new Cell(1, 2, false));
      board.addCell(new Cell(2, 0, false));
 
      expect(board.getAliveNeighbors(cell)).toEqual(1);
    });
  });
});

Implementation (conway.js):


var Cell = function(x, y, alive) {
  this.x = x;
  this.y = y;
  this.alive = alive;
};
 
Cell.prototype = {
  isAlive : function() {
    return this.alive;
   }
};
 
var Board = function() {
  this.cells = {}; 
};
 
Board.prototype = {
  addCell: function(cell){
    this.cells[getCellRepresentation(cell.x, cell.y)] = cell;
  },
  getCellAt: function(x, y) {
    return this.cells[getCellRepresentation(x, y)];  
  },
  getAliveNeighbors: function(cell) {
    var x = cell.x;
    var y = cell.y;
    var aliveCells = 0;
 
    for (var i = -1; i < 2; i++) {
      for(var j = -1; j < 2; j++) {
        if(i === 0 && i == j) {
          continue;
        }
        var currentCell = this.getCellAt(x + i, y + j);

        if(currentCell && currentCell.isAlive()) {
          aliveCells++;
        }
      }
    }

    return aliveCells;
  }
};

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=""> <s> <strike> <strong>