3
\$\begingroup\$

I've written a simple demo for Conway's Game Of Life for self-practice.

How can I improve the code, especially the processLife() method which traverses and updates the next state of every element in the matrix.

The complete code is down below;

For those whose eyes are tired of looking at code here: Gist Link

public class GameOfLifeDemo {

    private static final int    HEIGHT = 10;
    private static final long   PERIOD = 120*1;

    public static void main(String[] args) throws InterruptedException {
        boolean [][] matrix = new boolean[HEIGHT][HEIGHT];
//      generateRandom(matrix); // random values matrix
//      testGlider(matrix);     // test for Glider
        testTumbler(matrix);    // test for Tumbler

        while(true) {
            Thread.sleep(PERIOD);
            printMatrix(matrix);
            processLife(matrix);
            System.out.println("-----------------------------------------------------");
        }
    }

    private static void processLife(boolean[][] matrix) {
        boolean[][] tempMatrix = new boolean[matrix.length][matrix[0].length];
        copyMatrix(matrix, tempMatrix);

        // sweep the matrix
        for(int i = 0; i < HEIGHT; i++) {
            for(int j = 0; j < HEIGHT; j++) {
                // count alive neighboors
                int countAlive = 0;
                for(int k = i-1; k <= i+1; k++) {
                    for(int t = j-1; t <= j+1; t++) {
                        if((k == i && t == j) || (t < 0 || t >= HEIGHT) || (k < 0 || k >= HEIGHT) )
                            continue;
                        else {
                            if(matrix[k][t]) {
                                countAlive++;
                            }
                        }
                    }
                }

                handleRules(tempMatrix, i, j, countAlive);
            }
        }

        copyMatrix(tempMatrix, matrix);
    }

    // rules
    // if cell have neighboors smaller than 1, die of loneliness
    // if cell have neighboors greater than 4, die of overpopulation
    // if only cell have 3 or 4 neighboors, live
    private static void handleRules(boolean[][] matrix, int i, int j, int countAlive) {
        if(countAlive <= 1 || countAlive >= 4)
            matrix[i][j] = false;
        else if(countAlive == 3 || countAlive == 4)
            matrix[i][j] = true;
    }

    private static void copyMatrix(boolean[][] src, boolean[][] dst) {
        for(int i = 0; i < HEIGHT; i++)
            System.arraycopy(src[i], 0, dst[i], 0, HEIGHT);
    }

    private static void printMatrix(boolean[][] matrix) {
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j] == true) {
                    System.out.print('X');
                } else {
                    System.out.print(' ');
                }
            }
            System.out.println();
        }
    }

    private static void generateRandom(boolean[][] matrix) {
        for(int i = 0; i < HEIGHT; i++)
            for(int j = 0; j < HEIGHT; j++)
                matrix[i][j] = Math.random() < 0.5;
    }

    /*
     * Test Method for Generating a Glider
     *    
     *     X
     *      X
     *    XXX
     * 
     */
    private static void testGlider(boolean[][] matrix) {
        matrix[0][1] = true;

        matrix[1][2] = true;

        matrix[2][0] = true;
        matrix[2][1] = true;
        matrix[2][2] = true;
    }

    /*
     * Test Method for Generating a Tumbler
     *    
     *      XX XX
     *      XX XX
     *       X X
     *     X X X X
     *     X X X X
     *     XX   XX
     * 
     */
    private static void testTumbler(boolean[][] matrix) {
        matrix[0][2] = true;
        matrix[0][3] = true;
        matrix[0][5] = true;
        matrix[0][6] = true;

        matrix[1][2] = true;
        matrix[1][3] = true;
        matrix[1][5] = true;
        matrix[1][6] = true;

        matrix[2][3] = true;
        matrix[2][5] = true;

        matrix[3][1] = true;
        matrix[3][3] = true;
        matrix[3][5] = true;
        matrix[3][7] = true;

        matrix[4][1] = true;
        matrix[4][3] = true;
        matrix[4][5] = true;
        matrix[4][7] = true;

        matrix[5][1] = true;
        matrix[5][2] = true;
        matrix[5][6] = true;
        matrix[5][7] = true;
    }

}
\$\endgroup\$
  • \$\begingroup\$ If efficiency is what you're looking for, think about the ways how you could avoid copying the matrix, and instead do what all functional programming experts tell you not to do ie. manipulate the matrix directly. \$\endgroup\$ – Sami Laine Apr 2 '16 at 1:57
  • \$\begingroup\$ Because that if I update the next-state with an in-place modify, then the previous states of the unhandled cell neighboors will be corrupted. So, as far as I can see, it is impossible. \$\endgroup\$ – Levent Divilioglu Apr 2 '16 at 4:55
  • 1
    \$\begingroup\$ You can do this with O(n) extra space for an n by n matrix \$\endgroup\$ – Justin Apr 2 '16 at 7:12
  • \$\begingroup\$ Yes, that's how I handle the NxN matrix. So, you also confirm that there is no way to handle the next states without extra space, do I understand you right? \$\endgroup\$ – Levent Divilioglu Apr 2 '16 at 15:39
1
\$\begingroup\$

Everything is static. You could be using Object Oriented Programming, but you are simply using static functions and variables in the main function. Better would be to have a GameOfLife class which you instantiate (preferably to the initial state of the board). Something like this:

class GameOfLife {
    private boolean[][] board;

    public GameOfLife(boolean[][] board) {
        this.board = copyOfBoard(board);
    }
}

And then that class could have a advanceGeneration() function and similar things.


Don't use boolean[][] for this. It's less clear what you are doing here. Instead, use an enum:

public enum CellType {
    DEAD, ALIVE
}

Granted, the boolean[][] initializes to entirely false, whereas this CellType[][] doesn't, but I feel like the readability is worth it. At the very least, define some constants:

public static final boolean ALIVE = true;
public static final boolean DEAD = false;

private static final long PERIOD = 120*1;

I have no idea what this is by the name. What's the *1 for anyway? What is this the period of? Or is this referring to the punctuation mark?

while(true) {
    Thread.sleep(PERIOD);
    printMatrix(matrix);
    processLife(matrix);
    System.out.println("-----------------------------------------------------");
}

Oh you are using it as a delay between states of the board. In that case, it should be named something better. However, you are working too hard here. You could just use Java's built in Timer class:

Timer timer = new Timer();
timer.scheduleAtFixedRate(new TimerTask() {
    // Code goes here
}, 0, TIME_BETWEEN_FRAMES);

That uses java.util.Timer, but if you want to go for a Swing timer (aka you want to use a GUI), then you could do this:

// This is a javax.swing.timer
// this::functionToCall is really just any ActionListener, but I personally like lambda functions
Timer timer = new Timer(TIME_BETWEEN_FRAMES, this::functionToCall);

// You could do:
// Timer timer = new Timer(TIME_BETWEEN_FRAMES, (e) -> {
//     // Code goes here
// });
timer.start();

private static void handleRules(boolean[][] matrix, int i, int j, int countAlive) {
    if(countAlive <= 1 || countAlive >= 4)
        matrix[i][j] = false;
    else if(countAlive == 3 || countAlive == 4)
        matrix[i][j] = true;
}

This modifies the result. You almost always want your functions to act like mathematical functions rather than procedures. Additionally, Wikipedia lists the CGoL rules as follows:

  • Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any live cell with more than three live neighbours dies, as if by over-population.
  • Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Rewrite this like so:

private static boolean computeValueForNeighbours(boolean currentValue, int countAlive) {
    if (currentValue) {
        if (countAlive < 2) return false;
        if (countAlive == 2 || countAlive == 3) return true;
        if (countAlive > 3) return false;
    }
    if (countAlive == 3) return true;
    return false;
}

Note that this may also have different behaviour than your function.

    if(countAlive <= 1 || countAlive >= 4)
        matrix[i][j] = false;
    else if(countAlive == 3 || countAlive == 4)

That last countAlive == 4 will never be true, since it would have matched the previous if statement if it was.


private static void processLife(boolean[][] matrix) {
    boolean[][] tempMatrix = new boolean[matrix.length][matrix[0].length];
    copyMatrix(matrix, tempMatrix);

You copy the matrix to a temporary matrix and back every time. This is very inefficient. Although we tend to like immutability, I would avoid it in this case. There are two things bad here:

  1. You don't need to make a copy there and back. Just do something like

    boolean[][] oldState = copyOf(matrix);
    // Now store the new state into the `matrix`, using the oldState to obtain the information you need
    
  2. You don't need to copy the entire matrix. For an n x n matrix, copying takes O(n^2) extra space. You can get by with O(n) space, or copying only a single row. The idea is to modify the matrix in place, using a single-dimensional array to hold the old values of the row you are working on. Then, you simply use that array when you get the old values for computing the new line. You will need another variable as well. Something like this (doesn't completely work and I don't recommend this code style; this is just to get the idea out there):

    boolean[] row = new boolean[matrix[0].length];
    
    for (int y = 0; y < matrix.length; y++) {
        boolean previousX = false;
        for (int x = 0; x < matrix[y].length; x++) {
            int countAlive = 0;
    
            if (previousX) countAlive++;
            if (row[x]) countAlive++;
            if (row[x + 1]) countAlive++;
            if (row[x - 1]) countAlive++;
            if (matrix[y][x + 1]) countAlive++;
            if (matrix[y + 1][x - 1]) countAlive++;
            if (matrix[y + 1][x]) countAlive++;
            if (matrix[y + 1][x + 1]) countAlive++;
    
            previousX = row[x];
            row[x] = matrix[y][x];
            matrix[y][x] = computeValueForNeighbours(matrix[y][x], countAlive);
        }
    }
    

    That looks very awkward because row stores part of one row and part of the next row. The if statements do go by the top, middle, and bottom row of the nearby cells. Please improve the readability of this when you actually code it.

\$\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.