Simulation of Conway's Game of Life with periodic boundary conditions

Question

This is exercise 2.4.20. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

Implement a class that simulates Conway’s Game of Life.

One thing to note: I did not want my grid to have passive edges and so in my program I considered the grid to be an opened torus (for example in a 10-by-10 grid represented by an array: a[9+1][9+1] == a[0][0]). I also tried to make the name of the methods and variables as self-explanatory as possible.

Here is my program:

public class GameOfLife
{
    public static boolean[][] randomGridMaker(int n, double p)
    {
        // n is the number of grid cells in each row or column
        // p is the probability of a cell being alive
        boolean[][] grid = new boolean[n][n];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (Math.random() < p)
                {
                    grid[i][j] = true;
                }
            }
        }
        return grid;
    }
    public static boolean[][] gridEqualizer(boolean[][] a)
    {
        int n = a.length;
        boolean[][] b = new boolean[n][n];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                b[i][j] = a[i][j];
            }
        }
        return b;
    }
    public static int liveNeighborCounter(boolean[][] a, int i, int j)
    {
        int counter = 0;
        int n = a.length;
        if (a[(i-1)%n][(j-1)%n]) counter++;
        if (a[(i-1)%n][j%n]) counter++;
        if (a[(i-1)%n][(j+1)%n]) counter++;
        if (a[i%n][(j+1)%n]) counter++;
        if (a[(i+1)%n][(j+1)%n]) counter++;
        if (a[(i+1)%n][j%n]) counter++;
        if (a[(i+1)%n][(j-1)%n]) counter++;
        if (a[i%n][(j-1)%n]) counter++;
        return counter;
    }
    public static boolean[][] gridUpdater(boolean[][] a)
    {
        int n = a.length;
        boolean[][] b = new boolean[n][n];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                b[i][j] = a[i][j];
            }
        }
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < n; j++)
            {
                int liveNeighbors = liveNeighborCounter(a, i, j);
                if (!a[i][j] && liveNeighbors == 3) b[i][j] = true;
                if (a[i][j])
                {
                    if (liveNeighbors == 1) b[i][j] = false;
                    if (liveNeighbors > 3) b[i][j] = false;
                }
            }
        }
        return b;
    }
    public static void gridDrawer(boolean[][] a)
    {
        int n = a.length;
        StdDraw.setXscale(0,n);
        StdDraw.setYscale(0,n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (a[i][j]) StdDraw.filledSquare(i+0.5,j+0.5,0.47);
            }
        }
    }
    public static void main(String[] args)
    {
        int n = Integer.parseInt(args[0]);
        double p = Double.parseDouble(args[1]);
        StdDraw.setPenColor(StdDraw.BOOK_BLUE);
        StdDraw.enableDoubleBuffering();
        boolean[][] a = new boolean[n][n];
        boolean[][] b = new boolean[n][n];
        a = randomGridMaker(n, p);
        while (true)
        {
            StdDraw.clear();
            gridDrawer(a);
            StdDraw.show();
            StdDraw.pause(50);
            StdDraw.clear();
            b = gridUpdater(a);
            gridDrawer(b);
            StdDraw.show();
            StdDraw.pause(50);
            a = gridEqualizer(b);
        }
    }
}

StdDraw is a simple API written by the authors of the book. I checked my program and it works. Here are two different instances of it:

Instance 1: n = 20 and p = 0.1:

Instance 2: n = 100 and p = 0.5:

Is there any way that I can improve my program (especially its performance)?

Thanks for your attention.

Answer 1

Nice implementation, few suggestions:

Naming conventions

In Java methods should be verbs and classes should be nouns.

• method randomGridMaker can be renamed to makeRandomGrid (or similar)
• method liveNeighborCounter can be renamed to countAliveNeighbors
• method gridDrawer could be drawGrid, etc..

Java Naming Convetions

Input validation

The program needs two arguments to start, better to provide a message to the user:

if(args.length != 2) {
    System.out.println("Size and probability not provided");
    System.exit(1);
}

Encapsulation

The grid is passed around in almost every method. Would be better to have the grid as state of GameOfLife:

public class GameOfLife {
    
    private boolean[][] grid;
    private int n;
    private double p;
    
    public GameOfLife(int n, double p) {
        grid = new boolean[n][n];
        this.n=n;
        this.p=p;
    }
//...
}

This will also make GameOfLife easier to reuse.

Main loop

while (true)
    {
        StdDraw.clear(); 
        gridDrawer(a);
        StdDraw.show();
        StdDraw.pause(50);
        StdDraw.clear();
        b = gridUpdater(a);
        gridDrawer(b);
        StdDraw.show();
        StdDraw.pause(50);
        a = gridEqualizer(b);
    }

• The method gridDrawer already knows how to use the library StdDraw, so the the methods clear and show can be moved there

• There is no need of gridEqualizer if a new grid is already created in gridUpdater

• The two calls to pause(50) can now become pause(100)

The result would be:

GameOfLife gol = new GameOfLife(n,p);
gol.initRandom();
while (true){
    drawGrid(gol.getGrid());
    StdDraw.pause(100);
    gol.update(); // this is gridUpdater
}

Notice that:

• GameOfLife doesn't know how to draw itself, therefore is independent of the library StdDraw
• Only GameOfLife can modify the grid

Performance

There are no big issues about performances, just few suggestions.

There are many operations in liveNeighborCounter:

public static int liveNeighborCounter(boolean[][] a, int i, int j)
    {
        int counter = 0;
        int n = a.length;
        if (a[(i-1)%n][(j-1)%n]) counter++;
        if (a[(i-1)%n][j%n]) counter++;
        if (a[(i-1)%n][(j+1)%n]) counter++;
        if (a[i%n][(j+1)%n]) counter++;
        if (a[(i+1)%n][(j+1)%n]) counter++;
        if (a[(i+1)%n][j%n]) counter++;
        if (a[(i+1)%n][(j-1)%n]) counter++;
        if (a[i%n][(j-1)%n]) counter++;
        return counter;
    }

I noticed that there is no need to use % so often, but only when the index oveflows. It can be simplified like this:

private int countAliveNeighbors(int i, int j) {
    int counter = 0;
    for(int x=i-1 ; x<=i+1; x++) {
        for(int y=j-1; y<=j+1; y++) {
            // Skip given position
            if(x==i && y==j)
                continue;
            if(isAlive(castIndex(x),castIndex(y))) {
                counter++;
            }
        }
    }
    return counter;
}

private boolean isAlive(int i, int j) {
    return grid[i][j];
}

private int castIndex(int i) {
    if(i>=n) return 0;
    return i<0 ? n-1 : i;
}

Regarding memory, I noticed that there are some initializations that can be avoided like:

boolean[][] a = new boolean[n][n];
a = randomGridMaker(n, p);

The initialization is already done in the method randomGridMaker, so you can directly have:

boolean[][] a = randomGridMaker(n, p);

Same for other parts in the code. I will just paste here the code refactored.

Refactored code

public class GameOfLife {
    
    private boolean[][] grid;
    private int n;
    private double p;
    
    public GameOfLife(int n, double p) {
        grid = new boolean[n][n];
        this.n=n;
        this.p=p;
    }
    
    public void initRandom() {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (Math.random() < p)
                {
                    grid[i][j] = true;
                }
            }
        }
    }
    
    private boolean isAlive(int i, int j) {
        return grid[i][j];
    }
    
    private int castIndex(int i) {
        if(i>=n) return 0;
        return i<0 ? n-1 : i;
    }
    
    private int countAliveNeighbors(int i, int j) {
        int counter = 0;
        for(int x=i-1 ; x<=i+1; x++) {
            for(int y=j-1; y<=j+1; y++) {
                // Skip given position
                if(x==i && y==j)
                    continue;
                if(isAlive(castIndex(x),castIndex(y))) {
                    counter++;
                }
            }
        }
        return counter;
    }
    
    private boolean[][] cloneGrid(){
        boolean[][] b = new boolean[n][n];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                b[i][j] = grid[i][j];
            }
        }
        return b;
    }
    
    public void update() {
        boolean[][] b = cloneGrid();
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < n; j++)
            {
                int liveNeighbors = countAliveNeighbors(i,j);
                if(isAlive(i,j)) {
                    if (liveNeighbors == 1 || liveNeighbors > 3) { 
                        b[i][j] = false;
                    }
                } else if (liveNeighbors == 3){
                    b[i][j] = true;
                }
            }
        }
        grid=b;
    }
    
    public boolean[][] getGrid(){
        return grid;
    }
    
    public static void drawGrid(boolean[][] a)
    {
        int n = a.length;
        StdDraw.clear();
        StdDraw.setXscale(0,n);
        StdDraw.setYscale(0,n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (a[i][j]) StdDraw.filledSquare(i+0.5,j+0.5,0.47);
            }
        }
        StdDraw.show();
    }
    public static void main(String[] args)
    {
        if(args.length != 2) {
            System.out.println("Size and probability not provided");
            System.exit(1);
        }
        int n = Integer.parseInt(args[0]);
        double p = Double.parseDouble(args[1]);
        StdDraw.setPenColor(StdDraw.BOOK_BLUE);
        StdDraw.enableDoubleBuffering();
        GameOfLife gol = new GameOfLife(n,p);
        gol.initRandom();
        while (true)
        {
            drawGrid(gol.getGrid());
            StdDraw.pause(100);
            gol.update();
        }
    }
}