Game of Life: TDD style in Java

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.

4 thoughts on “Game of Life: TDD style in Java

  1. Pingback: Thoughts about TDD « Schneide Blog

  2. Using java.awt.Point here violates package principles. The class Board contains business logic, the class java.awt.Point is from the java.awt package and therefore the UI. It would be more convenient if the package that contains Board has zero dependencies on anything related to the UI, so that we could easily verify that our business logic does not wrongly depend on the UI. So we should use a Point class of our own here.

    Apart from that, I really enjoyed reading this article and got inspired. I happen to be developing a Game of Life engine for fun just now, and was seeking inspiration about how to test it. You’ve inspired me, thank you!

    • Hi Christian, thank you for your comment. You are right with your observation that we should use a specific “Point” or “Coordinate” class. The usage of java.awt.Point is a shortcut that saves time only in the short run.

      Good find.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s