Conway’s Game of Life must be one of the most continuously re-implemented algorithms in the history of software development. In case you’ve not seen it, the Game of Life is played out with cellular automata, or cells that are switched on or off by a set of rules. The rule set is applied to the all cells in one step, creating a new state or generation repeatedly.
A cellular automata implementation shares much with other problems often solved with stepwise and parallelizable modelling – as say some approaches to quantum electrodynamics, fluid mechanics and other physical models – so I figured it was as good a motif as any to explore some new technologies, and maybe work up some kata along the way.
The first step was to build up a core library code that implements the Game of Life. For a first implementation we need a grid of cells on which to play out the game, and a rule set that transforms the grid from one state to another.
This immediately sounded like a good basis for relatively quick kata. There are a couple of useful principles involved: practically, it’s immediately amenable to unit testing as we explicitly define the state we expect from any transformation; and the outline of the algorithm – applying a rule set to a whole state to transform it into a new state – is a useful one to remember.
So, to outline the kata, we need:
- A 2d grid that reports whether a cell at x,y is on (alive); allows us to set on/off state at x,y; allows us to clear (all off) and reset (random on/off); and perhaps display a simple representation of the grid to stdout.
- A rule set that transforms a 2d grid and returns a new 2d grid with some rule set applied.
- Unit tests should express the rules in terms of expected start and end grid states.
The rules – well they’re written up in many places, but to summarise:
- Cells with fewer than 2 neighbours die.
- Cells with 2 neighbours that are alive, stay alive.
- Cells with 3 neighbours stay alive if alive, or come to life if dead.
- Cells with 4 or more neighbours die.
The last time I went through this kata my set of C# NUnit tests looked like this – but I’d say the idea is to start from scratch each time:
[TestFixture]
public class CoreTests
{
[Test]
[ExpectedException("System.ArgumentOutOfRangeException")]
public void StubGridDoesntTakeNegativeWidth()
{
var g = new StubLifeGrid(-1, 1);
}
[Test]
[ExpectedException("System.ArgumentOutOfRangeException")]
public void StubGridDoesntTakeNegativeHeight()
{
var g = new StubLifeGrid(1, -1);
}
[Test]
[ExpectedException("System.ArgumentOutOfRangeException")]
public void StubGridOutOfRangeWidthRequestFails()
{
var g = new StubLifeGrid(2, 2);
g.AliveAt(3, 1);
}
[Test]
[ExpectedException("System.ArgumentOutOfRangeException")]
public void StubGridOutOfRangeHeightRequestFails()
{
var g = new StubLifeGrid(2, 2);
g.AliveAt(1, 3);
}
[Test]
[ExpectedException("System.ArgumentOutOfRangeException")]
public void StubGridSetOutOfRangeWidthFails()
{
var g = new StubLifeGrid(2, 2);
g.Set(3, 1, true);
}
[Test]
[ExpectedException("System.ArgumentOutOfRangeException")]
public void StubGridSetOutOfRangeHeightFails()
{
var g = new StubLifeGrid(2, 2);
g.Set(1, 3, true);
}
[Test]
public void DiesWithNoNeighbours()
{
ILifeGrid g = new StubLifeGrid(3, 3);
// Starts alive
g.Set(1, 1, true);
var r = new BasicRuleSet();
g = r.Transform(g);
Assert.IsFalse(g.AliveAt(1, 1));
// Starts dead
g = new StubLifeGrid(3, 3);
g.Set(1, 1, false);
g = r.Transform(g);
Assert.IsFalse(g.AliveAt(1, 1));
}
[Test]
public void DiesWithOneNeighbour()
{
ILifeGrid g = new StubLifeGrid(3, 3);
// Starts alive
g.Set(1, 1, true);
g.Set(0, 0, true); // create all possible and test
var r = new BasicRuleSet(); // static, in fact?
g = r.Transform(g);
Assert.IsFalse(g.AliveAt(1, 1));
// Starts dead
g = new StubLifeGrid(3, 3);
g.Set(1, 1, false);
g.Set(0, 0, true);
g = r.Transform(g);
Assert.IsFalse(g.AliveAt(1, 1));
}
[Test]
public void StaysAliveWithTwoNeighbours()
{
ILifeGrid g = new StubLifeGrid(3, 3);
g.Set(1, 1, true);
g.Set(0, 0, true);
g.Set(0, 1, true);
g.Display();
var r = new BasicRuleSet(); // static, in fact?
g = r.Transform(g);
g.Display();
Assert.IsTrue(g.AliveAt(1, 1));
// starts dead, stays dead
g = new StubLifeGrid(3, 3);
g.Set(1, 1, false);
g.Set(0, 0, true);
g.Set(0, 1, true);
g.Display();
r = new BasicRuleSet(); // static, in fact?
g = r.Transform(g);
g.Display();
Assert.IsFalse(g.AliveAt(1, 1));
}
[Test]
public void BornWithThreeNeighbours()
{
ILifeGrid g = new StubLifeGrid(3, 3);
g.Set(1, 1, false);
g.Set(0, 0, true);
g.Set(0, 1, true);
g.Set(0, 2, true);
g.Display();
var r = new BasicRuleSet(); // static, in fact?
g = r.Transform(g);
g.Display();
Assert.IsTrue(g.AliveAt(1, 1));
}
[Test]
public void StaysAliveWithThreeNeighbours()
{
ILifeGrid g = new StubLifeGrid(3, 3);
g.Set(1, 1, true);
g.Set(0, 0, true);
g.Set(0, 1, true);
g.Set(0, 2, true);
var r = new BasicRuleSet(); // static, in fact?
g = r.Transform(g);
Assert.IsTrue(g.AliveAt(1, 1));
}
}
In this case, and like many of the examples, there’s a message handler pump that keeps the model going. Messages to the renderer are posted delayed by the desired frame rate. 