21
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The method should be a method of the board class, not a static method accepting a board. \$\endgroup\$ – Ingo Bürk Sep 7 '14 at 8:31
  • \$\begingroup\$ Of course! I thought it was ugly but didn't know how to improve it. Thank you! @IngoBürk \$\endgroup\$ – 11684 Sep 7 '14 at 8:53
  • 1
    \$\begingroup\$ Related, but focused more on performance than on elegance: codereview.stackexchange.com/questions/42718/… \$\endgroup\$ – Ilmari Karonen Sep 7 '14 at 10:12
18
\$\begingroup\$

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;
 }
\$\endgroup\$
  • 7
    \$\begingroup\$ I'd suggest that b.getTile be renamed b.hasNeighbourAt (or something similar) for readability. The name getTile makes the method appear to return something called a Tile. \$\endgroup\$ – user25884 Sep 7 '14 at 1:20
  • 1
    \$\begingroup\$ @Tony - getTile returns a value based on whether there is life there, not whether it has a neighbour at somewhere. A name like isLifeAt(x,y) may be better, but certainly not hasNeighbourAt. \$\endgroup\$ – rolfl Sep 8 '14 at 11:17
  • \$\begingroup\$ Right, I was thinking of passing the neighbors' offsets, not their coordinates. (No -u- in "neighbor" for me! I'm American.) It's a simple problem, so you probably don't want to overengineer it. Still, it'd be nice to think in terms of tiles. \$\endgroup\$ – user25884 Sep 8 '14 at 15:23
  • \$\begingroup\$ Turns out I never accepted this answer. Anyway, thanks, it was very helpful. \$\endgroup\$ – 11684 Jan 28 '18 at 23:03
13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I like your enum, but I have a feeling that the Position class will cause a lot of performance overhead as the original code only uses primitives for the position. \$\endgroup\$ – Simon Forsberg Sep 7 '14 at 12:11
  • 5
    \$\begingroup\$ The title of the OP did ask for a "more elegant" solution. I don't think the performance overhead is really significant. I've used this pattern in a programming contest with performance constraints, and it didn't seem to cause problems. To have such clarity and flexibility in the overall design, I think it's worth doing this way. If it really turns out to hurt performance, only then we should start to optimize, at the expense of breaking up good encapsulation. \$\endgroup\$ – janos Sep 7 '14 at 12:26
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ No, count living neighbours. Sorry, I should have stated that. getTile(int, int) returns a boolean, indicating if that cell is alive. \$\endgroup\$ – 11684 Sep 6 '14 at 22:23
  • 1
    \$\begingroup\$ Ok, counting living cells makes more sense^^ I overlooked that your tiles field just stores a boolean for the alive state. In that case I would name the method countLivingNeighbours, which makes it clearer what the method actually does. \$\endgroup\$ – tim Sep 6 '14 at 22:34
  • \$\begingroup\$ int count = -1; with your double for-loop approach sounds like a bad idea. If the current tile is false, you should start at zero. \$\endgroup\$ – Simon Forsberg Sep 7 '14 at 12:09
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is what Donald Knuth was talking about when he mentioned premature optimization. \$\endgroup\$ – Ingo Bürk Sep 7 '14 at 8:30
  • 1
    \$\begingroup\$ @IngoBürk This would be a premature optimization if it didn't simplify the code. But it really does! \$\endgroup\$ – maaartinus Sep 7 '14 at 10:03
  • 1
    \$\begingroup\$ @IngoBürk I wrote about shortness and also "It also makes other operations simpler". I partly agree with you concerning unused cells, but the it all can be encapsulated in a few lines. And it's an ancient trick, used nearly everywhere and worth learning. \$\endgroup\$ – maaartinus Sep 7 '14 at 10:31
  • 1
    \$\begingroup\$ I'm fine with using an array as the implementation. Whatever floats one's boat. I only argued that performance as the reasoning is not a good argument because it's micro optimization on something that hasn't even been investigated yet to see if performance is even a problem. \$\endgroup\$ – Ingo Bürk Sep 7 '14 at 11:08
  • 1
    \$\begingroup\$ @IngoBürk It really isn't. This way is MUCH easier to work with. In fact, anyone coming from a C background is probably so used to doing this that the translation helper method shown in this answer is completely unneeded. \$\endgroup\$ – krowe Sep 8 '14 at 0:29
4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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).

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You forgot to mention anything about how the OP can get a Bool^9 out of their current way of doing things... Besides, while they can lead to impressive gains in performance, my problem with highly specific optimisations like these is that they make it a hassle to extend or generalise the algorithm later - e.g. to support larger neighbourhoods or additional states - and they make the code harder to understand for future readers (including/primarily your future self). The OP asked for more elegant code, not necessarily more fast/cryptic code. :P Still maybe useful for someone's exact scenario. \$\endgroup\$ – underscore_d Dec 2 '18 at 23:03
  • \$\begingroup\$ I think a lookup table is not just faster, but also quite a bit shorter and more elegant. The code can be extended easily to larger neighbourhoods, and all that really needs to change is the encoding of the transition function. If you further want to abstract it to cells of different colours, etc., this too can be encoded easily. \$\endgroup\$ – Mayer Goldberg Mar 7 at 22:17
  • \$\begingroup\$ It may be that I just hadn't thought enough about LUTs at the time. ;) I have been working on an implementation of Life with some extra features and might end up wanting to try LUTs on it. It's not currently clear to me where the boundary lies where it becomes useful, i.e. where trading more expressive code for transition functions becomes beneficial. But obviously that's probably more of a personal thing, and I'm not a mathematician by trade after all. :) I have in a past life done QuadLife on a 4 MHz Z80, so I'm not stranger to slightly more exotic LUTs, though it would be sorcery to me now! \$\endgroup\$ – underscore_d Mar 11 at 14:11
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I like the idea, but it doesn't fit in with my current algorithm, because I construct a new board for every 'frame', instead of changing the same board. This would make instantiating a new board a very heavy operation. \$\endgroup\$ – 11684 Sep 8 '14 at 10:58
  • \$\begingroup\$ For performance you could use byte instead of int (bool should also take 1 byte). \$\endgroup\$ – Gentian Kasa Oct 16 '15 at 10:38
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.