How to count a cell's neighbors in a cellular automaton with wraparound

Question

So I'm making a program that simulates Life-like cellular automata, but I'm having some trouble with the method used to count a cell's live neighbors. The problem is that I want to be able to change how the grid wraps around -- that is, whether it wraps around from left to right (i.e., cylindrical), from top to bottom and left to right (i.e., toroidal), or not at all (i.e., flat) -- and I can't figure out how to make my method account for that. Here's what I have so far:

public int getLiveNeighbors(int row, int col)
{
    int count = 0;

    // "topology" is an int that represents wraparound:
    // 0 = flat; 1 = cylindrical; 2 = toroidal
    int top = topology != 2 ? row - 1 : (row + ROWS - 1) % ROWS;
    int bottom = topology != 2 ? row + 1 : (row + 1) % ROWS;
    int left = topology != 0 ? (col + COLS - 1) % COLS : col - 1;
    int right = topology != 0 ? (col + 1) % COLS : col + 1;

    for (int r = top; r < bottom + 1; r++)
        for (int c = left; c < right + 1; c++)
            if (!(r == row && c == col) && getCell(r, c).equals(LIVE))
                count++;
}

The key, I think, is the if-statement in the for-loop -- there has to be some way to check whether r and c are within the bounds of the grid, while keeping in mind that the definition of "bounds" will vary depending on whether/how the grid wraps around. In the past I've gotten around this by having three different sets (one for each wraparound setting) of eight different if-statements to individually check each of the eight cells comprising the original cell's neighborhood; as you can imagine, it was not very pretty, but at least it worked.

I'm not so great at explaining my own code, so I hope that wasn't too confusing -- I'm feeling a little loopy myself (ha). If anyone has any questions, feel free to ask!

Answer 1

You probably already have a class like Board with a method like getCell(x, y) (at least a method of this kind is present in your code).

I'd just make this method lenient in a sense that it would accept negative x and y or x and y greater or equal to COLS and ROWS. Thus you could just iterate over col - 1 to col + 1 and row - 1 to row + 1 (minus col and row) and not care that these coordinates go "over the board". It's the task of the Board to do coordinate lookups correctly.

What makes your code harder is also that you handle different topologies in one place. It's quite hard to follow.

You could make it simpler by implementing different subclasses of Board like CylindricalBoard, ToroidalBoard and FlatBoard. Each of the subclasses would implement getCell differently, but in the context of the subclass it will be clearly understandable.

Answer 2

You're looking for the Strategy Pattern:

There are common situations when classes differ only in their behavior. For this cases is a good idea to isolate the algorithms in separate classes in order to have the ability to select different algorithms at runtime.

In this case you'd want something like this (abbreviated for clarity):

class Point {
    int x;
    int y;
}

interface WrapStrategy {
    Point moveUp(Point p);
    Point moveDown(Point p);
    Point moveLeft(Point p);
    Point moveRight(Point p);
}

class CylinderWrapping implements WrapStrategy {
    int height;
    int circumference;
    Point moveUp(Point p) {
        if (p.y <= 0)
            return null; // cannot move up
        return new Point(p.x, p.y - 1);
    }
    Point moveDown(Point p) {
        if (p.y >= height - 1)
            return null; // cannot move down
        return new Point(p.x, p.y + 1);
    }
    Point moveLeft(Point p) {
        if (p.x <= 0)
            return new Point(circumference - 1, p.y);
        return new Point(p.x - 1, p.y);
    }
    Point moveRight(Point p) {
        if (p.x >= circumference - 1)
            return new Point(0, p.y);
        return new Point(p.x + 1, p.y);
    }
}

Answer 3

Try this:

import java.awt.Point;

public class Neighbours {

    public static void main(String[] args) {
        Neighbours inst=new Neighbours();
        int r=3;//<ROWS
        int c=3;//<COLS
        for(int i :new int[]{0,1,2}){
            inst.type=i;
            System.out.format("There are %d neighbours of point (%d,%d), topography type %d\n", inst.countLiveNeighbours(r, c), c, r,i);
        }
    }

    int ROWS=4;
    int COLS=4;
    int type=0;//0=flat, 1=cylinder, 2=toroid

    /**
     * Is x,y a neighbour of r,c?
     * @return coordinates of neighbour or null
     */
    Point neighbour(int x, int y, int r, int c){
        if((x==c)&&(y==r))
            return null;
        switch (type){
/*this is wrong for the reasons explained below
        case 0: return ((x<COLS)&&(y<ROWS)) ? new Point (x,y) : null;
        case 1: return y<ROWS ? new Point(x%COLS,y) : null;
        case 2: return new Point(x%COLS,y%ROWS);
*/
 //replacement statements produce the correct behaviour
    case 0: return ((x<COLS)&&(x>-1)&&(y<ROWS)&&(y>-1)) ? new Point (x,y) : null;
    case 1: return ((y<ROWS)&&(y>-1)) ? new Point(Math.floorMod(x,COLS),y) : null;
    case 2: return new Point(Math.floorMod(x,COLS),Math.floorMod(y,ROWS));
        }
        return null;
    }

    int countLiveNeighbours(int r, int c){
        int result=0;
        for(int x=c-1; x<c+2; x++)
            for(int y=r-1; y<r+2; y++){
                Point p=neighbour(x,y,r,c);
                if(live(p)){
                    System.out.format("\tpoint (%d,%d)\n",(int)p.getX(),(int)p.getY());
                    result++;
                }
            }
        return result;
    }

    boolean live(Point p){
        boolean result=true;
        if(p==null)
            return false;
        //perform tests for liveness here and set result
        return result;
    }
}