Checking for neighbours more elegantly in Conway's Game of Life

Question

My method for counting neighbors in my soon-to-be Game of Life implementation is very repetitive and I was wondering if this could be done more elegantly:

static int countNeighbours(Board b, int x, int y) {
    int count = 0;
    if (b.getTile(x - 1, y - 1)) {
        ++count;
    }
    if (b.getTile(x, y - 1)) {
        ++count;
    }
    if (b.getTile(x + 1, y - 1)) {
        ++count;
    }
    if (b.getTile(x + 1, y)) {
        ++count;
    }
    if (b.getTile(x + 1, y + 1)) {
        ++count;
    }
    if (b.getTile(x, y + 1)) {
        ++count;
    }
    if (b.getTile(x - 1, y + 1)) {
        ++count;
    }
    if (b.getTile(x - 1, y)) {
        ++count;
    }
    return count;
}

Because officially the board should be infinite, I don't need out-of-bounds checks in this code - I assume the board is infinite here -, but my Board implementation secretly looks like this:

// TODO: make the board 'infinite'
public boolean getTile(int x, int y) {
    if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) return false;
    return tiles[y][x];
}

public void setTile(int x, int y, boolean val) {
    if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) return;
    tiles[y][x] = val;
}

(Just to save you the time it costs to type 'your code will cause an IndexOutOfBoundsException for the tile on (0,0)'. This question is on the implementation of static int countNeighbours(Board, int, int).)

I'm stuck with Java 6 by the way.

Answer 1

You're right, there's an alternate way to do this, but, first, some Java standards:

1. 1-liners should have braces. This is a code-style that is common to many langauges because it is more maintainable, and leads to fewer future bugs. Lines like:

   if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) return;
   

   should be:

   if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) {
       return;
   }
   

2. Don't use arithmetic when you can use a simpler operator. Back to:

   if (x < 0 || y < 0 || x > getWidth() - 1 || y > getHeight() -1) { ... }
   

   Which can be simplified to:

   if (x < 0 || y < 0 || x >= getWidth() || y >= getHeight()) { ...}
   

3. Use plain booleans when they make sense (again, back to...):

   if (x < 0 || y < 0 || x >= getWidth() || y >= getHeight()) { ...}
   

   which can be put in a function like (transformed to uses && instead):

   public boolean getTile(int x, int y) {
       return x >= 0 && y >= 0 && x < getWidth() && y < getHeight() && tile[y][x];
   }
   

   Note, how the standard boolean short-circuit evaluation ensures that the x and y are valid before the tile[y][x] is used.

OK, about that code duplication. A trick with these sorts of problems is to use an array of offsets. Consider your grid, which has 8 neighbours (in a relative y,x format):

-1,-1     -1,0    -1,+1

 0,-1     *us*     0,+1

+1,-1     +1,0    +1,+1

We can put these neighbour offsets in to an array:

private static final int[][] NEIGHBOURS = {
    {-1, -1}, {-1, 0}, {-1, +1},
    { 0, -1},          { 0, +1},
    {+1, -1}, {+1, 0}, {+1, +1}};

Then, your check method becomes:

static int countNeighbours(Board b, int x, int y) {
    int cnt = 0;
    for (int[] offset : NEIGHBOURS) {
        if (b.getTile(x + offset[1], y + offset[0]) {
           cnt++;
        }
    }
    return cnt;
 }

Answer 2

First of all, if the purpose of the getTile method is checking if a position is alive or not, call it isAlive. It makes the code a lot easier to understand that way.

It will help to encapsulate the possible directions in an enum:

enum Direction {
    NORTHWEST(-1, -1),
    NORTH(0, -1),
    NORTHEAST(1, -1),
    EAST(1, 0),
    SOUTHEAST(1, 1),
    SOUTH(0, 1),
    SOUTHWEST(-1, 1),
    WEST(-1, 0),
    ;

    final int dx;
    final int dy;

    Direction(int dx, int dy) {
        this.dx = dx;
        this.dy = dy;
    }
}

With the help of this enum, countNeighbours can be simplified in a more intuitive way:

static int countNeighbours(Board b, int x, int y) {
    int count = 0;
    for (Direction direction : Direction.values()) {
        if (b.isAlive(x + direction.dx, y + direction.dy)) {
            ++count;
        }
    }
    return count;
}

This could still be better: countNeighbours knows too much internal details about the Direction class (that it has dx and dy fields). We can have a more general solution by abstracting the details of positions, for example:

class Position {
    final int x;
    final int y;

    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    Position getNeighbourAt(Direction direction) {
        return new Position(x + direction.dx, y + direction.dy);
    }
}

Now countNeighbours can become:

static int countNeighbours(Board b, Position position) {
    int count = 0;
    for (Direction direction : Direction.values()) {
        if (b.isAlive(position.getNeighbourAt(direction))) {
            ++count;
        }
    }
    return count;
}

The good thing about this is that the logic of countNeighbours is now so generalized and abstract that the shape of the board doesn't matter anymore: it could be implemented as a globe, or a 3D grid, this logic will still work. The internal implementation of Direction and Position are fully hidden from countNeighbours, it doesn't need to know. This gives you the freedom to implement those differently without changing countNeighbours again.

Answer 3

Your Code

If you have so many if checks, it would be better to sort them in some way. For example, first all the x - 1 ifs, then the x ifs, then the x + 1 ifs:

static int countNeighbours(Board b, int x, int y) {
    int count = 0;
    if (b.getTile(x - 1, y - 1)) {
        ++count;
    }
    if (b.getTile(x - 1, y)) {
        ++count;
    }
    if (b.getTile(x - 1, y + 1)) {
        ++count;
    }
    if (b.getTile(x, y - 1)) {
        ++count;
    }
    if (b.getTile(x, y + 1)) {
        ++count;
    }
    if (b.getTile(x + 1, y - 1)) {
        ++count;
    }
    if (b.getTile(x + 1, y)) {
        ++count;
    }
    if (b.getTile(x + 1, y + 1)) {
        ++count;
    }
    return count;
}

This way, it's easier to see what you are checking, and also easier to see if you made some mistake.

Cleaner Code

You can always use two for loops instead:

int count = -1; // not counting ourselfs.
for (int xx = x - 1; xx <= x + 1; xx++) {
    for (int yy = y - 1; yy <= y + 1; yy++) {
        if (b.getTile(xx, yy))) {
            count++;
        }
    }
}
return count;

An alternative to starting at -1 would be to check if this is the current square:

if ((xx != x || yy != y) && b.getTile(xx, yy))) {
    count++;
}

You could also take a completely different approach:

1. if x and y are at the border, return 3
2. initial neighbor count: 8
3. Check if x is at the border, if so, subtract 3
4. Check if y is at the border, if so, subtract 3
5. return initial neighbor count

This would definitely perform better.

Although I'm unsure why you even need this method for the game of life?

And if your board would be infinite, the method would just always return 8 anyways.

Answer 4

Make your board slightly bigger so it gets a single tile unused border. Never examine cells on the border. This way you can omit the tests as you never land out of bounds. This makes the code a bit shorter and faster.

Consider placing your data in an 1D array. All it needs for it is a simple coordinate transformation like

boolean isAlive(int x, int y) {
    return data[HEIGHT * x + y];
}

On a modern CPU it's good for speed as multiplication is faster than memory indirection. It also makes other operations simpler, e.g., clearing or copying data.

Answer 5

Create a Point class instead of having pairs int x, int y everywhere. It is cleaner and more OO.

You do have to deal with the boundary conditions. There are basically two approches:

1. Make the board bigger than it should so that you have an invisible "buffer" border where the elements are always non-active. You can then simplify getTile since it you break down when it fetches an out of bound element, which is an element in the "buffer" border. You would have to modify your main loop so would it never tries to set the values in the "buffer" border.

2. The method you are currently using where you have to make sure you do not try to fetch a neighbor which is out of bounds (getTile).

There are already two posted answers that rightly suggest that you can make your code cleaner by using enum instead of a series of ifs. I want to propose a different solution. It is not necessarily better, but you should explore all possible solutions.

You can precompute the neighbors of the edge points, but compute the neighbors of the inner points. You would not want to store the precomputed neighbors of all inner points on a huge board since it would take too much memory.

public Collection<Point> getNeighbors(Point point) {
    Collection<Point> neighbors = edgePointsNeighbors.get(point);
    if (neighbors != null) { // point is on the edge
       return neighbors;
    } else { // point is an inner point
       return point.compute8Neighbors();
    }
}

where edgePointsNeighbors is a precomputed Map<Point, Collection<Point>>. The class Point should be immutable, with hashCode and equals correctly implemented if it is used as a map key.

Finally, I just want to make a more or less related comment to the effect that you could implement periodic boundary conditions instead. One could somewhat argue that periodic boundary conditions are closer to an infinite board than hard boundaries. In the method above, you would just have to change the precomputed neighbors of edgePointsNeighbors. All points on the edge would now also have 8 neighbors, but those neighbors would cross over. For example, Point(0, 0)'s neighbors would include Point(0, 1), Point(n - 1, n - 1), Point(0, n - 1), etc.

Answer 6

The answer by rolfl is great, I will just add that what you have here is a nice use-case for enums. If you define an enum like:

public enum Direction {
   N(-1,0),
   E(1,0),
   S(1,0),
   W(-1,0),
   NE(-1,1),
   SE(1,1),
   SW(1,-1),
   NW(-1,-1);

   public final int dx;
   public final int dy;

   Direction(int dx, int dy) {
       this.dx = dx;
       this.dy = dy;
   }
}

then you can do:

for (Direction dir : Direction.values()) {
    if (b.getTile(x + dir.dx, y + dir.dy) {
           cnt++;
    }
}

If checking for neighbors is all you need, this will not be a drastic improvement. However, it has the potential of making a lot of API a bit nicer; you could introduce methods with signatures more like like:

public boolean isNeighborAlive(int x, int y, Direction which);

Or you could make it more general by introducing a type Vector2D which could be very similar to Direction enum; it would have public static final fields holding instances pointing north, south, etc:

public final class Vector2D {
    public static final Vector2D N = new Vector2D(-1,0);
    // etc.

}

Then you could have api with methods like:

public boolean isNeighborAlive(Vector2D point, Vector2D offset);

which would produce a loop like:

for (Vector2D offset : Vector2D.directions()) {
    cnt += b.isNeighborAlive(current, offset)? 1 : 0;
}

(you could also have a method that adds two vectors and this could be cleaner, but would also produce a lot more garbage).

Answer 7

The transition function for the game of life is a function from Bool^9 -> Bool. This is a finite and very small function to compute. If you pre-compute it, then you don't need to count anything: Just loop through the board, and replace each cell with the value of the function at that point.

If you like this idea, you may enjoy pre-computing Bool^16 -> Bool^4, which is larger, but still small enough to keep in RAM, and then you can go through the board 4 times as fast, filling in a 2x2 matrix of cells at each iteration.

Answer 8

You can also count neighbors by having your cells contain their number of neighbors all the time. When a cell becomes "alive" it updates all surrounding cells by one and when one "dies" it decrements all surrounding cells.

Doing this requires basically the same code, but depending on whether you're getting number of values or making changes more frequently it may be faster since changes only happen when a tile actually changes and then only happens at that one 3x3 spot around it.

Answer 9

Personally, if I wouldn't want to refactor the code too much (because the project is too small or whatever the case may be), I'd go with:

static int countNeighbours(Board b, int x, int y) {
    return (b.getTile(x - 1, y - 1))   ? 1 : 0
           + (b.getTile(x, y - 1))     ? 1 : 0
           + (b.getTile(x + 1, y - 1)) ? 1 : 0
           + (b.getTile(x + 1, y))     ? 1 : 0
           + (b.getTile(x + 1, y + 1)) ? 1 : 0
           + (b.getTile(x, y + 1))     ? 1 : 0
           + (b.getTile(x - 1, y + 1)) ? 1 : 0
           + (b.getTile(x - 1, y))     ? 1 : 0;
}

and also rename getTile into something like isAlive. The end result should become something like:

static int countNeighbours(Board b, int x, int y) {
    return (b.isAlive(x - 1, y - 1))   ? 1 : 0
           + (b.isAlive(x, y - 1))     ? 1 : 0
           + (b.isAlive(x + 1, y - 1)) ? 1 : 0
           + (b.isAlive(x + 1, y))     ? 1 : 0
           + (b.isAlive(x + 1, y + 1)) ? 1 : 0
           + (b.isAlive(x, y + 1))     ? 1 : 0
           + (b.isAlive(x - 1, y + 1)) ? 1 : 0
           + (b.isAlive(x - 1, y))     ? 1 : 0;
}

Otherwise, I'd go with @Janos' or @rolfl's version.