3
\$\begingroup\$

Follow-up to: Game Of Life implemented with for-loops and a boolean-array

As proposed by palacsint I went on and rewrote my implementation of the Game Of Life and extracted everything into two classes:

  • PetriDish

    • The parent which holds the array of cells
    • Sets the array up and initializes each cell
    • Starts the evolution
  • Cell

    • Stores it's current value
    • Holds references to it's neighbors

The main cell array is still one-dimensional because I find it convenient to access all cells easily with a simple foreach loop. The outermost cells are a dead border and never change there state, mostly to ease handling of the array.

It works like this:

  • Initiate the PetriDish
  • Set the array
  • Add cells into the array
  • Initialize all cells
    • The cell fetches it's neighbors from the parent PetriDish, except if it is a border-cell, then it does nothing.
  • The PetriDish kicks off the evolution
    • The cell checks it's neighbors via two static methods, countAliveNeighbors and checkSurvival
    • It stores that value in a second variable
  • The PetriDish ends the evolution
    • The cell overrides it's old value with the new one from the above cycle

This has a few ugly quirks:

  • Handling of the border-cells feels a little bit odd, but while I think about it I could remove them completely
  • It's necessary to save the new value of the cell in another variable, there for makes the evolution a two-step process

Okay, enough talk, here's the code:

public class PetriDish {

    private Cell[] cells;
    private int width;
    private int height;
    private long generation;
    private long duration;

    public Cell[] getCells() {
        return cells;
    }

    public Cell getCell(int x, int y) {
        return cells[y * width + x];
    }

    public int getHeight() {
        return height;
    }

    public int getWidth() {
        return width;
    }

    public long getGeneration() {
        return generation;
    }

    public long getDuration() {
        return duration;
    }

    public PetriDish(int width, int height) {
        this.width = width;
        this.height = height;

        this.cells = new Cell[width * height];

        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                cells[y * width + x] = new Cell(this, x, y,
                        x == 0 || y == 0 || x == width - 1 || y == height - 1);
            }
        }

        for (Cell cell : cells) {
            cell.prepare();
        }
    }

    public void doEvolution() {
        long start = System.currentTimeMillis();

        for (Cell cell : cells) {
            cell.startEvolution();
        }
        for (Cell cell : cells) {
            cell.finishEvolution();
        }

        generation++;
        duration = System.currentTimeMillis() - start;
    }
}

public class Cell {

    private PetriDish parent;
    private int x;
    private int y;
    private boolean value;
    private boolean nextValue;
    private boolean isBorderCell;
    private List<Cell> neighbors;

    public boolean getValue() {
        return value;
    }

    public void setValue(boolean value) {
        if (!isBorderCell) {
            this.value = value;
        }
    }

    public Cell(PetriDish parent, int x, int y, boolean isBorderCell) {
        this.parent = parent;
        this.x = x;
        this.y = y;

        this.isBorderCell = isBorderCell;
        this.neighbors = new ArrayList<Cell>();
    }

    public void prepare() {
        if (!isBorderCell) {
            for (int neighborX = x - 1; neighborX <= x + 1; neighborX++) {
                for (int neighborY = y - 1; neighborY <= y + 1; neighborY++) {
                    if (neighborX != x || neighborY != y) {
                        neighbors.add(parent.getCell(neighborX, neighborY));
                    }
                }
            }
        }
    }

    public void startEvolution() {
        nextValue = checkSurvival(value, countAliveNeighbors(neighbors));
    }

    public void finishEvolution() {
        value = nextValue;
    }

    private static int countAliveNeighbors(Iterable<Cell> neighbors) {
        int neighborsAlive = 0;

        for (Cell neighbor : neighbors) {
            if (neighbor.value) {
                neighborsAlive++;
            }
        }

        return neighborsAlive;
    }

    private static boolean checkSurvival(boolean isAlive, int neighborsAlive) {
        switch (neighborsAlive) {
            case 0:
            case 1:
                return false;

            case 2:
                return isAlive;

            case 3:
                return true;

            default:
                return false;
        }
    }
}

The project can be found at GitHub and needs Slick for visualization and input.

\$\endgroup\$
4
\$\begingroup\$
  1. Getter-setter methods in PetriDish and Cell should be declared after the constructors. (Check Java Coding Conventions, 3.1.3 Class and Interface Declarations.) I prefer placing them at the end of the classes (after every other methods).

  2. I'd check the input values:

    import static com.google.common.base.Preconditions.*;
    ...
    
    public PetriDish(final int width, final int height) {
        checkArgument(width > 3, "width has to be at least 3");
        checkArgument(height > 3, "height has to be at least 3");
        ...
    }
    

    Of course a simple if and a throw new IllegalArgumentException also does it if you don't want to include guava-libraries.

  3. Passing this to another method/class in the constructor usually isn't a good idea:

    cells[y * width + x] = new Cell(this, x, y, x == 0 || y == 0 
        || x == width - 1 || y == height - 1);
    

    If the constructor later throws an exception the created Cell objects has a reference to an incompletely constructed PetriDish object. (Maybe Cell stores the reference in a static field, passes it to an event listener or a singleton class etc.) I'm not sure, but probably I'd create an init() method for this logic.

  4. Reading the following constructor call isn't the easiest task:

    new Cell(this, x, y, x == 0 || y == 0 || x == width - 1 || y == height - 1);
    

    I'd create a local variable for the last parameter:

    final boolean isBorderCell = x == 0 || y == 0 || x == width - 1 
        || y == height - 1;
    cells[y * width + x] = new Cell(this, x, y, isBorderCell);
    

    An isBorderCell method would be the best:

    private boolean isBorderCell(final int width, final int height, final int x, 
            final int y) {
        if (x == 0) {
            return true;
        }
        if (y == 0) {
            return true;
        }
        if (x == width - 1) {
            return true;
        }
        if (y == height - 1) {
            return true;
        }
        return false;
    }
    

    I think it's easier to read than a long boolean expression.

  5. I'd rename Cell.prepare() to init(). It's more common.

  6. The prepare method could be in the PetriDish class and could call a Cell.setNeighbors(). If you move it Cell doesn't have to have PetriDish field and constructor parameter at all.

  7. countAliveNeighbors should be non-static and should use the neighbors field directly:

    private int countAliveNeighbors() {
        ...
    }
    

    The same is true for the checkSurvival method. Actually, I'd rename it to calcNextState:

    private boolean calcNextState() {
        final int neighborsAlive = countAliveNeighbors();
        switch (neighborsAlive) {
            ...
        }
    }
    
  8. Use getters instead of direct field access in the countAliveNeighbors method:

    if (neighbor.getValue()) {
        neighborsAlive++;
    }
    

    (What's the deal with Java's public fields?)

  9. Instead of the boolean value flag I'd use an enum with ALIVE and DEAD values. It would be more meaningful (without true and false as magic "numbers").

  10. The isBorderCell flag in Cell does not smell good. Create a Cell interface:

    public interface Cell {
        void prepare();
        void startEvolution();
        void finishEvolution();
        boolean getValue();
        void setValue(final boolean value);
    }
    

    and rename the current Cell to NormalCell and create an empty BorderCell class:

    public class BorderCell implements Cell {
    
        @Override
        public void prepare() {
        }
    
        @Override
        public void startEvolution() {
        }
    
        @Override
        public void finishEvolution() {
        }
    
        @Override
        public boolean getValue() {
            return false;
        }
    
        @Override
        public void setValue(boolean value) {
            throw new UnsupportedOperationException();
        }
    }
    

    A factory method is useful in the PetriDish:

    private Cell createCell(int x, int y) {
        if (isBorderCell(width, height, x, y)) {
            return new BorderCell();
        } else  {
            return new NormalCell(this, x, y);
        }
    }
    

    After that remove the borderCell flag and its usages from the NormalCell class. (Check Replacing the Conditional Logic on Price Code with Polymorphism in Refactoring: Improving the Design of Existing Code by Martin Fowler)

  11. If you would like to get rid of the nextValue field in Cell try modifying the doEvolution method. It could return a new PetriDish with brand new Cells which contain the state of the next generation. It would help storing the full history (for example in a List<PetriDish>), but I think the current design with the nextValue field also fine (if you don't need the full history of course).

\$\endgroup\$
  • 1
    \$\begingroup\$ Very nice, thank you, very good recommendations. After some thinking I've decided to drop the border-cells completely and instead just check the values in prepare()/init(), the check of the neighbors is done in a foreach anyway, so it won't effect that part, but it will remove a lot of overhead. \$\endgroup\$ – Bobby Dec 17 '11 at 20:04

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.