I always got problems finding the right track with test driven development (TDD), going down the wrong track can get you stuck.
So here I document my experience with tdd-ing Conway’s Game of Life in Java.
The most important part of a game of life implementation since the rules are simple is the datastructure to store the living cells.
So using TDD we should start with it.
One feature of our cells should be that they are equal according to their coordinates:
@Test
public void positionsShouldBeEqualByValue() {
assertEquals(at(0, 1), at(0, 1));
}
The JDK features a class holding two coordinates: java.awt.Point, so we can use it here:
public class Board {
public static Point at(int x, int y) {
return new Point(x, y);
}
}
You could create your own Position or Cell class and implementing equals/hashCode accordingly but I want to keep things simple so we stick with Point.
A board should holding the living cells and we need to compare two boards according to their living cells:
@Test
public void boardShouldBeEqualByCells() {
assertEquals(new Board(at(0, 1)), new Board(at(0, 1)));
}
Since we are only interested in living cells (all other cells are considered dead) we store only the living cells inside the board:
public class Board {
private final Set<Point> alives;
public Board(Point... points) {
alives = new HashSet<Point>(Arrays.asList(points));
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Board board = (Board) o;
if (alives != null ? !alives.equals(board.alives) : board.alives != null) return false;
return true;
}
@Override
public int hashCode() {
return alives != null ? alives.hashCode() : 0;
}
}
If you take a look at the rules you see that you need to have a way to count the neighbours of a cell:
@Test
public void neighbourCountShouldBeZeroWithoutNeighbours() {
assertEquals(0, new Board(at(0, 1)).neighbours(at(0, 1)));
}
Easy:
public int neighbours(Point p) {
return 0;
}
Neighbours are either vertically adjacent:
@Test
public void neighbourCountShouldCountVerticalOnes() {
assertEquals(1, new Board(at(0, 0), at(0, 1)).neighbours(at(0, 1)));
}
public int neighbours(Point p) {
int count = 0;
for (int yDelta = -1; yDelta <= 1; yDelta++) {
if (alives.contains(at(p.x, p.y + yDelta))) {
count++;
}
}
return count;
}
Hmm now both neighbour tests break, oh we forgot to not count the cell itself:
First the test…
@Test
public void neighbourCountShouldNotCountItself() {
assertEquals(0, new Board(at(0, 0)).neighbours(at(0, 0)));
}
Then the fix:
public int neighbours(Point p) {
int count = 0;
for (int yDelta = -1; yDelta <= 1; yDelta++) {
if (!(yDelta == 0) && alives.contains(at(p.x, p.y + yDelta))) {
count++;
}
}
return count;
}
And the horizontal adjacent ones:
@Test
public void neighbourCountShouldCountHorizontalOnes() {
assertEquals(1, new Board(at(0, 1), at(1, 1)).neighbours(at(0, 1)));
}
public int neighbours(Point p) {
int count = 0;
for (int yDelta = -1; yDelta <= 1; yDelta++) {
for (int xDelta = -1; xDelta <= 1; xDelta++) {
if (!(xDelta == 0 && yDelta == 0) && alives.contains(at(p.x + xDelta, p.y + yDelta))) {
count++;
}
}
}
return count;
}
And the diagonal ones are also included in our implementation:
@Test
public void neighbourCountShouldCountDiagonalOnes() {
assertEquals(2, new Board(at(-1, 1), at(1, 0), at(0, 1)).neighbours(at(0, 1)));
}
So we set the stage for the rules. Rule 1: Cells with one neighbour should die:
@Test
public void cellWithOnlyOneNeighbourShouldDie() {
assertEquals(new Board(), new Board(at(0, 0), at(0, 1)).next());
}
A simple implementation looks like this:
public Board next() {
return new Board();
}
OK, on to Rule 2: A living cell with 2 neighbours should stay alive:
@Test
public void livingCellWithTwoNeighboursShouldStayAlive() {
assertEquals(new Board(at(0, 0)), new Board(at(-1, -1), at(0, 0), at(1, 1)).next());
}
Now we need to iterate over each living cell and count its neighbours:
public class Board {
public Board(Point... points) {
this(new HashSet<Point>(Arrays.asList(points)));
}
private Board(Set<Point> points) {
alives = points;
}
public Board next() {
Set<Point> aliveInNext = new HashSet<Point>();
for (Point cell : alives) {
if (neighbours(cell) == 2 {
aliveInNext.add(cell);
}
}
return new Board(aliveInNext);
}
}
In this step we added a convenience constructor to pass a set instead of some cells.
The last Rule: a cell with 3 neighbours should be born or stay alive (the pattern is called blinker, so we name the test after it):
@Test
public void blinker() {
assertEquals(new Board(at(-1, 1), at(0, 1), at(1, 1)), new Board(at(0, 0), at(0, 1), at(0, 2)).next());
}
For this we need to look at all the neighbours of the living cells:
public Board next() {
Set<Point> aliveInNext = new HashSet<Point>();
for (Point cell : alives) {
for (int yDelta = -1; yDelta <= 1; yDelta++) {
for (int xDelta = -1; xDelta <= 1; xDelta++) {
Point testingCell = at(cell.x + xDelta, cell.y + yDelta);
if (neighbours(testingCell) == 2 || neighbours(testingCell) == 3) {
aliveInNext.add(testingCell);
}
}
}
}
return new Board(aliveInNext);
}
Now our previous test breaks, why? Well the second rule says: a *living* cell with 2 neighbours should stay alive:
public Board next() {
Set<Point> aliveInNext = new HashSet<Point>();
for (Point cell : alives) {
for (int yDelta = -1; yDelta <= 1; yDelta++) {
for (int xDelta = -1; xDelta <= 1; xDelta++) {
Point testingCell = at(cell.x + xDelta, cell.y + yDelta);
if ((alives.contains(testingCell) && neighbours(testingCell) == 2) || neighbours(testingCell) == 3) {
aliveInNext.add(testingCell);
}
}
}
}
return new Board(aliveInNext);
}
Done!
Now we can refactor and make the code cleaner like removing the logic duplication for iterating over the neighbours, adding methods like toString for output or better failing test messages, etc.
Schneide Blog 