6
\$\begingroup\$

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:

enter image description here

Instance 2: n = 100 and p = 0.5:

enter image description here

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

Thanks for your attention.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This had been my favorite programming exercise for a long time. I have 2 suggestions: 1) make a Glider Gun. The Gosper gun is ok but there are more interesting ones out there. 2) read about the construction of a Turing Machine in the Game of Life (it's theoretical, I'd not try actually doing it, but the concept is really interesting) \$\endgroup\$
    – Z4-tier
    Sep 1 '20 at 4:15
  • \$\begingroup\$ @Z4-tier Thank you very much. I certainly try to make other constructions with it. :) \$\endgroup\$ Sep 1 '20 at 8:35
3
\$\begingroup\$

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();
        }
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Thank you very much for your time. :) \$\endgroup\$ Sep 1 '20 at 8:35
  • \$\begingroup\$ I try to assimilate all the above information gradually. \$\endgroup\$ Sep 1 '20 at 8:43
  • \$\begingroup\$ @KhashayarBaghizadeh I'm glad I could help ;) Please consider to accept the answer when you are satisfied. \$\endgroup\$
    – Marc
    Sep 1 '20 at 15:23
  • \$\begingroup\$ Of course :) I'm just waiting for a few more hours to see if there could be other suggestions. \$\endgroup\$ Sep 1 '20 at 15:31

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.