4
\$\begingroup\$

Inspired by this post, I decided to try to implement my own Conway's Game of Life.

I started with a non-warping board:

/**
 * Represents a single generation of a Conway's Game of Life.
 *
 */
public class Generation {

    protected static final int[][] SURROUNDING_CELL_POSITIONS = { { -1, -1 },
            { 0, -1 }, { 1, -1 }, { -1, 0 }, { 1, 0 }, { -1, 1 }, { 0, 1 },
            { 1, 1 } };

    protected final Cell[][] board;
    protected final int width;
    protected final int length;

    public Generation(Cell[][] board) {
        this.board = copyOfBoard(board);
        width = board.length;
        length = board[0].length;
    }

    public Generation getNextGeneration() {
        Cell[][] result = new Cell[width][length];
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < length; j++) {
                int count = getSurroundingCellCount(i, j);
                result[i][j] = board[i][j].clone();
                if (result[i][j].isAlive()) {
                    if (count > Cell.ALIVE_TO_DEAD_OVER
                            || count < Cell.ALIVE_TO_DEAD_UNDER) {
                        result[i][j].dead();
                    }
                } else if (count == 3) {
                    result[i][j].alive();
                }
            }
        }
        return new Generation(result);
    }

    protected int getSurroundingCellCount(int i, int j) {
        int result = 0;
        for (int[] add : SURROUNDING_CELL_POSITIONS) {
            int iIndex = (i + add[0]);
            int jIndex = (j + add[1]);
            if (iIndex >= 0 && iIndex < width && jIndex >= 0 && jIndex < length
                    && board[iIndex][jIndex].isAlive()) {
                result++;
            }
        }
        return result;
    }

    public Generation skipToNthGeneration(int n) {
        Generation result = this;
        for (int i = 0; i < n; i++) {
            result = result.getNextGeneration();
        }
        return result;
    }

    public Cell[][] getBoard() {
        return copyOfBoard(board);
    }

    protected Cell[][] copyOfBoard(Cell[][] board) {
        int length = board.length;
        int subArrayLength = board[0].length;
        Cell[][] result = new Cell[length][subArrayLength];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < subArrayLength; j++) {
                result[i][j] = board[i][j] == null ? new Cell() : board[i][j].clone();
            }
        }
        return result;
    }

}

I immediately noticed that getNextGeneration() requires O(n) space. Is this necessary? I feel like it isn't, but I am unsure of how to do so.

Then I created the WarpingGeneration class, to implement a warping Conway's Game of Life:

public final class WarpingGeneration extends Generation {

    public WarpingGeneration(Cell[][] board) {
        super(board);
    }

    @Override
    public WarpingGeneration getNextGeneration() {
        return new WarpingGeneration(super.getNextGeneration().board);
    }

    @Override
    protected int getSurroundingCellCount(int i, int j) {
        int result = 0;
        for (int[] add : SURROUNDING_CELL_POSITIONS) {
            int iIndex = (i + add[0]) % width;
            int jIndex = (j + add[1]) % length;
            if (iIndex < 0) {
                iIndex += width;
            }
            if (jIndex < 0) {
                jIndex += length;
            }
            if (board[iIndex][jIndex].isAlive()) {
                result++;
            }
        }
        return result;
    }

}

Since it is very similar to the Generation class, I used inheritance to my advantage here.

And of course, nothing can be done without the Cell class:

public class Cell implements Cloneable {

    public static final int DEAD_TO_ALIVE = 3;
    public static final int ALIVE_TO_DEAD_OVER = 3;
    public static final int ALIVE_TO_DEAD_UNDER = 2;

    private boolean isAlive;

    public Cell() {
        dead();
    }

    public Cell(boolean isAlive) {
        setAlive(isAlive);
    }

    public boolean isAlive() {
        return this.isAlive;
    }

    public void setAlive(boolean isAlive) {
        this.isAlive = isAlive;
    }

    public void alive() {
        this.isAlive = true;
    }

    public void dead() {
        this.isAlive = false;
    }

    public void toggleLife() {
        this.isAlive = !this.isAlive;
    }

    @Override
    public Cell clone() {
        return new Cell(isAlive);
    }

}

Usage:

    public static void main(String[] args) {
        Cell[][] cells = new Cell[10][10];
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                cells[i][j] = new Cell(false);
            }
        }
        cells[0][1].alive();
        cells[1][2].alive();
        cells[2][2].alive();
        cells[2][1].alive();
        cells[2][0].alive();

        Generation g = new WarpingGeneration(cells);
        printGen(g);
        for (int i = 0; i < 100; i++) {
            g = g.getNextGeneration();
            printGen(g);
        }
    }

    private static void printGen(Generation g) {
        Cell[][] cellss = g.getBoard();
        for (Cell[] cells : cellss) {
            for (Cell cell : cells) {
                System.out.print((cell.isAlive() ? '*' : ' ') + " ");
            }
            System.out.println();
        }
    }

This will print 100 generations of the "Walker".

Concerns:

  1. Is it possible to reduce space complexity from O(n)? If so, how?
  2. Is there a faster way to do skipToNthGeneration()?
  3. And as usual, anything else?
\$\endgroup\$
  • \$\begingroup\$ This is a not-too-simple algorithm which seems to be pretty optimised from the point of view of using low-memory-consuming features. On the other hand, the exact efficiency of the whole approach is not too clear (writing the main ideas about how each part is expected to deal with each task might perhaps be helpful? Starting to analyse this code right away without knowing what is going on at all is not too appealing)... \$\endgroup\$ – varocarbas Nov 23 '15 at 12:18
  • \$\begingroup\$ ... in any case,: skipToNthGeneration() does seem unnecessarily inefficient. Why iterating from 0 to n every time? Why not defining the starting indices in getNextGeneration() on account of this n value? This also brings the exact motivation behind the current implementation of the loops in getNextGeneration(); it does seem improvable. Although as said, sharing the basic ideas about what you are trying to accomplish in each part would be definitively very helpful to motivate some people (at least, me :)) to take a deeper look at the code. \$\endgroup\$ – varocarbas Nov 23 '15 at 12:24
  • \$\begingroup\$ Side note: I don't quite understand why some people memorise algorithms as there is only way to accomplish the given goal (you don't see the algorithm you posted as one of the multiple possible answers to a given problem, but as an absolute truth; something which is there to be copied/pasted and, eventually, slightly updated). The worst part is that a big proportion of these assumed-to-be-ideal ways are quite non-optimal (to not mention that copy-pasters are quite bad at facing real problems). Well... at least, I didn't spend my time understanding the problem and writing an answer :) \$\endgroup\$ – varocarbas Nov 24 '15 at 9:11
2
\$\begingroup\$

Design

Extension is the wrong tool for this job. You should be using the Strategy pattern to provide an adjacent life detector. Clients can provide any detector, and your base Generator code is protected.

The getNextGeneration method is noise. Clients can already do that by calling skipToNthGeneration(1).

You've got a fancy mutable cell class that basically holds a boolean. Use an enum with ALIVE and DEAD and save yourself a ton of object creation to no good end.

You can make Generation an immutable class. I don't see any reason not to.

Naming

I think width and height are more clear than width and length.

x and y are better variables for a coordinate space than i and j.

Concerns

  1. You can play with a sparse matrix implementation. That might help for relatively sparse games, but it's going to add a decent amount of complexity to a toy problem. I think it's premature optimization unless you know something you aren't saying.

  2. There are definitely performance optimizations out there. Do a search on codereview. Many will have you recreate the Cell class to track, for instance, the adjacent cells. Maybe start here? Optimize Conway's Game of Life As always, you need to find the correct line between ease-of-comprehension and performance. Trust Knuth: premature optimizations are the root of all evil.

  3. If I were to redesign this as-is, it would look more like the code below. I left out the creation of a new Generation object from scratch because I ran out of review time. :-) A builder might be appropriate, or a constructor taking a boolean[][].

Generation:

/**
 * Represents a single generation of a Conway's Game of Life.
 *
 */
public final class Generation {

    private static final int ALIVE_TO_DEAD_OVER = 3;
    private static final int ALIVE_TO_DEAD_UNDER = 2;

    private enum CellState {
        ALIVE, DEAD
    }

    private final CellState[][] board;
    private final LifeDetector lifeDetector = null;
    private final int height;
    private final int width;

    private Generation(final CellState[][] board) {
        this.board = board;
        this.width = board.length;
        this.height = board[0].length;
    }

    public Generation advanceGenerations(final int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Must advance a non-negative number of generations! Got " + n);
        }

        Generation result = this;
        for (int i = 0; i < n; i++) {
            result = result.getNextGeneration();
        }
        return result;
    }

    public boolean isCellAlive(final int x, final int y) {
        return this.board[x][y] == CellState.ALIVE;
    }

    public int getWidth() {
        return this.width;
    }

    public int getHeight() {
        return this.height;
    }

    private Generation getNextGeneration() {
        final CellState[][] nextGeneration = new CellState[this.width][this.height];

        for (int x = 0; x < this.width; x++) {
            for (int y = 0; y < this.height; y++) {
                nextGeneration[x][y] = this.nextCellState(x, y);
            }
        }
        return new Generation(nextGeneration);
    }

    private CellState nextCellState(final int x, final int y) {
        final int adjacentLife = this.lifeDetector.countAdjacentLife(this, x, y);

        if (this.isCellAlive(x, y)
                && ((adjacentLife < ALIVE_TO_DEAD_UNDER) || (adjacentLife > ALIVE_TO_DEAD_OVER))) {
            return CellState.DEAD;
        }

        if (adjacentLife == 3) {
            return CellState.ALIVE;
        }

        return this.board[x][y];
    }
}

LifeDetector:

public interface LifeDetector {

    int countAdjacentLife(final Generation generation, final int x, final int y);
}

NonWarpingDetector:

public final class NonWarpingDetector implements LifeDetector {

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

    @Override
    public int countAdjacentLife(final Generation generation, final int x, final int y) {

        int adjacentLife = 0;
        for (final int[] add : SURROUNDING_CELL_POSITIONS) {
            final int xIndex = (x + add[0]);
            final int yIndex = (y + add[1]);
            if ((xIndex >= 0) && (xIndex < generation.getWidth())
                    && (yIndex >= 0) && (yIndex < generation.getHeight())
                    && generation.isCellAlive(x, y)) {
                adjacentLife++;
            }
        }
        return adjacentLife;

    }

}

WarpingDetector:

public final class WarpingDetector implements LifeDetector {

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

    @Override
    public int countAdjacentLife(final Generation generation, final int x, final int y) {
        int adjacentLife = 0;
        for (final int[] add : SURROUNDING_CELL_POSITIONS) {
            int xIndex = (x + add[0]) % generation.getWidth();
            int yIndex = (y + add[1]) % generation.getHeight();
            if (xIndex < 0) {
                xIndex += generation.getWidth();
            }
            if (yIndex < 0) {
                yIndex += generation.getHeight();
            }
            if (generation.isCellAlive(x, y)) {
                adjacentLife++;
            }
        }
        return adjacentLife;
    }
}
\$\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.