12
\$\begingroup\$

I am a beginner to java and I've coded the Game of Life! For those not familiar, the game entails creating a grid of specified dimensions with each box in the grid being either dead or alive. The grid starts with a random dead or alive state for each box. New generations have new dead/alive boxes based on the following conditions: If there are 3 alive boxes neighbouring any dead box, it becomes alive. If there are less than 2 alive boxes neighbouring an alive box, that box dies. It also dies if there are more than 3 alive boxes around it.

The way I am approaching this is by making a boolean[][] array grid with true representing an alive box and false representing a dead one. The view class takes this boolean grid and turns it into a grid of boxes that are either coloured white or red (white = dead)(red = alive).

Game Class:

import java.util.Arrays;
import java.util.Random;

public class Game {
    private boolean[][] grid;
    private int genCount;
    private int width;
    private int height;

    public Game(int i, int j) {
        genCount = 0;
        if (i < 1 || j < 1) {
            throw new IllegalArgumentException("grid too small!");
        }
        if (i > 100 || j > 100) {
            throw new IllegalArgumentException("grid too big!");
        }
        width = i;
        height = j;
        grid = new boolean[j][i];
    }

    public int getWidth() {
        return width;
    }
    public int getHeight() {
        return height;
    }

    public boolean[][] getGrid() {
        return grid;
    }

    public void setGrid(boolean[][] grid) {
        this.grid = grid;
    }

    public int getGen() {
        return genCount;
    }

    public void setGen(int gen) {
        this.genCount = gen;
    }

    public void randomGrid(double probability) {
        Random r = new Random();
        for (int j = 0; j < height; j++) {
            for (int i = 0; i < width; i++) {
                grid[j][i] = Math.random() < probability;
            }
        }
    }

    public boolean[][] makeCopy() {
        // making a copy of the current grid, avoiding aliasing.
        boolean[][] nGrid = new boolean[height][width];
        for (int j = 0; j < height; j++) {
            for (int i = 0; i < width; i++) {
                nGrid[j][i] = grid[j][i];
            }
        }
        return nGrid;
    }

    public void newGen() {

        boolean[][] nGrid = makeCopy();

        for (int j = 0; j < height; j++) {
            for (int i = 0; i < width; i++) {
                if (grid[j][i] == false) {
                    // new life, due to having 3 neighbours!
                    if (getNeighbours(j, i) == 3) {
                        nGrid[j][i] = true;
                    }
                } else {
                    // isolation death!
                    if (getNeighbours(j, i) <= 1) {
                        nGrid[j][i] = false;
                    }
                    // overcrowing death!
                    if (getNeighbours(j, i) >= 4) {
                        nGrid[j][i] = false;
                    }
                }
            }
        }
        genCount++;
        grid = nGrid;
    }

    public int getNeighbours(int j, int i) {
        int count = 0;
        int jMax = grid[0].length - 1;
        int iMax = grid[1].length - 1;

        // checking up, down, right, left, allowing wrapping
        if ((j < jMax && grid[j + 1][i]) || (j == jMax && grid[0][i])) {
            count++;
        }
        if ((j > 0 && grid[j - 1][i]) || (j == 0 && grid[jMax][i])) {
            count++;
        }
        if ((i < iMax && grid[j][i + 1]) || (i == iMax & grid[j][0])) {
            count++;
        }
        if ((i > 0 && grid[j][i - 1]) || (i == 0 && grid[j][iMax])) {
            count++;
        }

        // checking diagonals, allowing wrapping
        if ((j < jMax && i < iMax && grid[j + 1][i + 1]) || (j == jMax && i < iMax && grid[0][i + 1])
                || (j < jMax && i == iMax && grid[j + 1][0]) || (j == jMax && i == iMax && grid[0][0])) {
            count++;
        }
        if ((j < jMax && i > 0 && grid[j + 1][i - 1]) || (j == jMax && i > 0 && grid[0][i - 1])
                || (j < jMax && i == 0 && grid[j + 1][iMax]) || (j == jMax && i == 0 && grid[0][iMax])) {
            count++;
        }
        if ((j > 0 && i < iMax && grid[j - 1][i + 1]) || (j == 0 && i < iMax && grid[jMax][i + 1])
                || (j > 0 && i == iMax && grid[j - 1][0]) || (j == 0 && i == iMax && grid[jMax][0])) {
            count++;
        }
        if ((j > 0 && i > 0 && grid[j - 1][i - 1]) || (j == 0 && i > 0 && grid[jMax][i - 1])
                || (j > 0 && i == 0 && grid[j - 1][iMax]) || (j == 0 && i == 0 && grid[jMax][iMax])) {
            count++;
        }
        return count;
    }

}

View Class:

import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class View extends JPanel {

    public void paint(Graphics g) {

        Game game = new Game(10, 10);
        game.randomGrid(0.2);
        game.newGen();
        boolean[][] grid = game.getGrid();

        g.setColor(Color.red);
        for (int j = 0; j < game.getHeight(); j++) {
            for (int i = 0; i < game.getWidth(); i++) {
                g.drawRect(100 + (50 * i), 100 + (50 * j), 50, 50);
                if (grid[j][i]) {
                    g.fillRect(100 + (50 * i), 100 + (50 * j), 50, 50);
                }
            }
        }

    }

    public static void main(String[] args) {
        JFrame frame = new JFrame();
        frame.getContentPane().add(new View());

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(1000, 1000);
        frame.setVisible(true);
    }
}
\$\endgroup\$
2

5 Answers 5

20
\$\begingroup\$

You are not assigning default values to the fields and you are splitting game logic and UI. That's a good start.

public Game(int i, int j) {

In a public function or constructor I expect clearly named parameters.

if (i > 100 || j > 100) {
    throw new IllegalArgumentException("grid too big!");
}

So a grid of 101 cells is too big if i = 1 and j = 101 but a field of 10 thousand cells is not too big if i = 100 and j = 100? I'd return specific errors for the width and height parameters.

width = i;

Generally we simply use this.width = width instead, so we don't have to come up with a different variable name.

public boolean[][] getGrid() {
    return grid;
}

Beware of exposing your state. The reference to the grid is copied, but the arrays are mutable! Either clone or expose the state in another way (e.g. using an enumerator or by referencing grid cells separately using coordinates).

public void setGen(int gen) {
    this.genCount = gen;
}

It's a bit weird that you can set the genCount during the game of life. Again, setGen and gen may not really be clear to the user. gen may also have any value apparently, allowing the object instance to have an invalid state. I'd rename genCount to generation, so away with gen altogether and remove this setter.

public void randomGrid(double probability) {

This is OK-ish, but I prefer to check if probabilities are between 0 and 1 inclusive (yeah, I know, Java is rather heavy on boilerplate code).

public boolean[][] makeCopy() {

This seems near identical to getGrid. But more importantly, if I make a copy of a game then I don't expect a grid in return. This method is in dire need to be made private anyway.

boolean[][] nGrid = new boolean[height][width];

Just newGrid is only 2 characters extra. Don't overly skim on characters (and possibly learn how to touch type).

for (int i = 0; i < width; i++) {
    nGrid[j][i] = grid[j][i];
}

Use System.arrayCopy() at least for the inner loop instead.

if (grid[j][i] == false) {

Ugh, here are the i and j again, but now j is the X-coordinate while it was the width before and i is the Y-coordinate.

Furthermore, what about two constants? DEAD = false and ALIVE = true? Using an enum is also possible (enum Cell { DEAD, ALIVE; }), so that false and true cannot even be used anymore.

if (getNeighbours(j, i) == 3) {

This I like, good method name, and a method that is sorely needed here.

genCount++;
grid = nGrid;

Lovely, side effects right at the end where they belong.


As for getNeighbours, let's simplify things a bit using modular arithmetic...

private static final boolean ALIVE = true;

private int getNeighbours(int x, int y) {
    int count = 0;

    // iterate over all neighbouring cells as a square
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            // skip cell itself
            if (dx == 0 && dy == 0) {
                continue;
            }

            // get coordinates for neighbour
            int nx = Math.floorMod(x + dx, width);
            int ny = Math.floorMod(y + dy, height);

            if (grid[nx][ny] == ALIVE) {
                count++;
            }
        }
    }

    return count;
}

Note that floorMod is the modulus operation while % is the remainder operation which will return -1 if the left operand is -1. That's not what you want, you want width - 1 or height - 1 instead.

Now I hope that looks a bit easier on the eye. You may want to rename dx to deltaX and nx to neighbouringX or something like that, but there is such a thing as overdoing it too. For local vars you may be a bit less strict (fields and parameters are more important for sure).

Note that I didn't know that the game of life uses wrapping, but that's another matter I guess. I'll not go on about the strategy design pattern, that might be a bit too deep.


I think your design would look better if you split your game of life into a Game and Grid class. That way the method naming would be much easier.


Finally, currently your game of life only operates when redrawing the window (or JFrame in Swing talk). That's of course not how it should be, it should be running on a timer and/or using buttons.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I'm glad you focused on the Game class. I focused on the GUI. I like both our answers. \$\endgroup\$ May 5, 2020 at 22:13
  • 4
    \$\begingroup\$ "So a grid of 101 cells is too big if i = 1 and j = 101 but a field of 10 thousand cells is not too big if i = 100 and j = 100? That cannot be right?" Can't it? If the UI only has space to show 100 cells horizontally, and 100 cells vertically, that sounds about right to me. \$\endgroup\$ May 6, 2020 at 9:27
  • 6
    \$\begingroup\$ @PaulD.Waite Sure thing, but then I would have an error message saying that it is too wide or too high rather than "too big". I'll adjust the wording accordingly. \$\endgroup\$ May 6, 2020 at 10:29
  • \$\begingroup\$ "(and possibly learn how to touch type)" What do you mean by this? I'm used to touch typing meaning being able to type without looking at the keyboard, but I'm not sure how that applies to the clarity of using easier to understand variable names. \$\endgroup\$
    – Davy M
    May 7, 2020 at 1:23
  • 2
    \$\begingroup\$ BTW, the whole makeCopy() method could simply be replaced with "return grid.clone()". \$\endgroup\$ May 7, 2020 at 4:28
11
\$\begingroup\$

I made some modifications to your View class and created this GUI.

Life GUI

I couldn't get the Game class to cycle through generations. Maybe I missed something. I didn't see where the Game class needed any changes.

Here are the changes I made to your View class.

  1. I started the GUI on the Event Dispatch Thread (EDT) by calling the SwingUtilities invokeLater method. This ensures that the Swing components are created and updated on the EDT.

  2. I put the painting code in the paintComponent method. I called super.paintComponent to maintain the Swing paint chain. I removed all code that wasn't painting code.

  3. I put @Override annotations on all of the methods I overrode. That way, the compiler will possibly tell me if there's a problem with my method calls.

  4. I scaled the JPanel to a more reasonable size. Some of us still have tiny monitors. I got rid of most of the magic numbers.

Here's the View class code.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class View extends JPanel implements Runnable {

    private static final long serialVersionUID = 1L;

    private boolean[][] grid;

    private int margin;
    private int squareWidth;

    private Game game;

    public View() {
        this.game = new Game(10, 10);
        this.game.randomGrid(0.2);
        this.grid = game.getGrid();

        this.margin = 50;
        this.squareWidth = 32;
        int width = squareWidth * 10 + margin + margin;
        this.setPreferredSize(new Dimension(width, width));
    }

    @Override
    public void run() {
        JFrame frame = new JFrame("Conway's Game of Life");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        frame.getContentPane().add(new View());
        frame.pack();
        frame.setLocationByPlatform(true);
        frame.setVisible(true);

        Thread thread = new Thread(new Timer(game, this));
        thread.start();
    }   

    public void setGrid(boolean[][] grid) {
        this.grid = grid;
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        int generation = game.getGen();
        String text = "Generation: " + generation;
        g.setColor(Color.BLACK);
        g.drawString(text, 10, 30);

        g.setColor(Color.red);
        for (int j = 0; j < grid.length; j++) {
            for (int i = 0; i < grid[j].length; i++) {
                int x = margin + (squareWidth * i);
                int y = margin + (squareWidth * j);
                g.drawRect(x, y, squareWidth, squareWidth);
                if (grid[j][i]) {
                    g.fillRect(x, y, squareWidth, squareWidth);
                }
            }
        }

    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(new View());
    }

} 

I created a new Timer class to update the GUI every 5 seconds. Since the GUI never changed, I put a System.out.println method in the timer loop to make sure it was running.

You can change the 5 second delay if you wish.

import javax.swing.SwingUtilities;

public class Timer implements Runnable {

    private volatile boolean running;

    private Game game;

    private View view;

    public Timer(Game game, View view) {
        this.game = game;
        this.view = view;
        this.running = true;
    }

    @Override
    public void run() {
        while (running) {
            sleep(5000L);
            game.newGen();
            updateView();
//          System.out.println("running");
        }
    }

    private void sleep(long duration) {
        try {
            Thread.sleep(duration);
        } catch (InterruptedException e) {
            // Deliberately left empty
        }
    }

    private void updateView() {
        SwingUtilities.invokeLater(new Runnable() {
            @Override
            public void run() {
                view.setGrid(game.getGrid());
                view.repaint();
            }
        });
    }

    public synchronized void setRunning(boolean running) {
        this.running = running;
    }

}
\$\endgroup\$
2
  • \$\begingroup\$ It only performs the game of life in the redraw (e.g. resize) in the original. Cool to see an answer that focuses on the GUI, mine focuses on the game engine. \$\endgroup\$ May 5, 2020 at 22:06
  • \$\begingroup\$ So by minimizing and reshowing repeatly, the game runs faster? \$\endgroup\$ May 6, 2020 at 20:23
8
\$\begingroup\$

I would recommend changing how your grid is represented in memory. Imagine you have a 10000x10000 grid and just 1 cell at coordinates (5,5) that's alive.

If you use an array to store that information, you have to create thousands upon thousands of data points pretty much all of which basically say nothing but “nothing to see here”. Dead cells are the default and therefore there's not really much we need to hold in memory about them.

So let's use a HashSet that only stores the alive cells. If the HashSet contains a given coordinate, the corresponding cell is alive. Otherwise the HashSet returns false, meaning it is dead. Now you can have a virtually infinite grid which, especially if mostly empty (as a Game of Life usually is), hardly needs any memory.

My Java is super rusty so consider the following something like pseudo code, but you get the idea:

public class Coordinate {
    public int x, y;

// Just to make it even clearer than I thought it was: 
// There is more work to do in this code snippet, like overriding equals() and hashCode(). 
// This code is just to demonstrate the concept, not an actual full implementation.

}

public class Grid {
    private HashSet grid;

    public void setAlive(Coordinate c) {
        grid.add(c);
    }

    public void setDead(Coordinate c) {
        grid.remove(c);
    }

    public boolean isAlive(Coordinate c){
        return grid.contains(c);
    }

    public int getNumberOfNeighbours(Coordinate c){
        ...
    }
}

Obviously you can now continue to encapsulate other grid-specific functions and make your Game class simpler and better readable.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ To fully realize the benefits of this approach, you should also modify newGen() to only iterate over the neighbors of cells in the previous generation's HashSet, so that its runtime will be proportional to the number of live cells regardless of how far apart they are. (A slight complication is that doing this naively may result in redundantly processing the same cell multiple times if it has several live neighbors. One way to avoid that is to have a first pass that just counts the neighbors of each cell and stores them in a HashMap, and a second pass that updates the state based on that.) \$\endgroup\$ May 6, 2020 at 11:21
  • \$\begingroup\$ I just created a chess game that uses the same approach. I like the idea that you use Coordinate, but to avoid confusion I'd call that Position instead (as a position has an x- and y-coordinate). Furthermore, HashSet is just an implementation of Set (and in this case you'd use Set<Position> of course. Beware that Set<Position> requires Position.equals and Position.hashCode to be implemented (!). The approach is valid, but it does take a bit more advanced programming. \$\endgroup\$ May 6, 2020 at 16:27
  • \$\begingroup\$ @MaartenBodewes Which is why I added that the code snippet should be considered pseudo code to get the idea across ;) And to me a position can also be “above” or “top” so I found coordinate slightly more fitting, but whatever, the main goal was to explain the concept, not to provide copy-and-pastable code. \$\endgroup\$
    – Graprar
    May 6, 2020 at 17:10
  • 1
    \$\begingroup\$ An entry in a hash set containing a coordinate object requires at an absolute minimum 32 bits (one reference) for the hash entry and 128 bits for the object (two words overhead and two 32 bit fields). In an array, the state can be represented as a single bit. A game of life where only one in 160 cells are active wouldn't be very interesting, so you're probably not optimising for a representative use case. \$\endgroup\$ May 7, 2020 at 16:05
  • \$\begingroup\$ @PeteKirkham Interesting. I wasn't quite sure how much memory the HashSet solution would actually take which is why I changed my wording from “strongly suggest” to “recommend” in a later edit. I didn't expect it to be this bad, especially since I had been introduced to this approach at university (for this usecase, the Game of Life). But if you have gliders flying off into space the grid can become quite expansive and still mostly empty and there's no need to dynamically extend the grid, right? (Plus one still gets the benefit of only having to iterate over actually existing cells.) \$\endgroup\$
    – Graprar
    May 7, 2020 at 19:59
3
\$\begingroup\$

I can't speak to the Java-related aspects of your solution, but you've got one problem that would be an issue in any language: you're performing far more dynamic allocation than necessary.

In your case, you know exactly how much space you need: two grids of width*height space each. Instead of allocating a new grid every generation, just allocate the space you need at game startup. With each generation, swap which one represents the current state, and which one represents the next state. You can do this by allocating grid as a three-dimensional array, or by allocating two grids and swapping references, or whatever other method you think is easiest.

\$\endgroup\$
3
  • \$\begingroup\$ You can get away with one grid width*height and two working arrays of size width; update one row at a time, write back to the grid one row behind the one you're calculating so you don't affect the calculation. \$\endgroup\$ May 7, 2020 at 16:25
  • 1
    \$\begingroup\$ Interesting optimization direction. But beware at implementation specifics here: as one cell update depends on all its neighbours previous state, updating one row requires retaining knowledge of previous state of three rows (the one being currently updated, and the two neighbouring rows). One would therefore need kind of a moving (potentially rolling) window. But, I guess, no need of a "working copy" of the row being currently being updated, that we would need then to copy back to the array: updates could be done in-place. \$\endgroup\$ May 7, 2020 at 19:29
  • \$\begingroup\$ @PeteKirkham, a rolling update like you describe saves even more space, but it comes at a cost: shared access to the grid is much harder. The grid representing the current generation is only in a consistent state between updates, rather than always being in a consistent state. \$\endgroup\$
    – Mark
    May 7, 2020 at 20:26
2
\$\begingroup\$

A few quick notes on newGen(). The main one is you're calling getNeighbours twice in the cell-was-alive case, meaning you're doing double the work to count them when the value can't change. So you should only call it once and save the result in a variable, and since you're going to need the count in all cases so you can do it once before the if:

    for (int j = 0; j < height; j++) {
        for (int i = 0; i < width; i++) {
            int neighbours = getNeighbours(j, i);

I'd then continue with the 'alive' case since it's the 'true' case, but that doesn't really matter. Sticking with what you had, this becomes

            if (grid[j][i] == false) {
                // new life, due to having 3 neighbours!
                if (neighbours == 3) {
                    nGrid[j][i] = true;
                }
            } else {
                // isolation death!
                if (neighbours <= 1) {
                    nGrid[j][i] = false;
                }
                // overcrowing death!
                if (neighbours >= 4) {
                    nGrid[j][i] = false;
                }
            }

But as it stands you're copying the grid and then setting or resetting it for changes whereas we do explicitly know whether each cell is dead or alive in the conditions. If we change this to:

            if (grid[j][i] == false) {
                // new life, due to having 3 neighbours!
                if (neighbours == 3) {
                    nGrid[j][i] = true;
                } else {
                    // still dead
                    nGrid[j][i] = false;
                }
            } else {
                // isolation death!
                if (neighbours <= 1) {
                    nGrid[j][i] = false;
                } else if (neighbours >= 4) {
                    // overcrowing death!
                    nGrid[j][i] = false;
                } else {
                    // still alive
                    nGrid[j][i] = true;
                }
            }

then we're always setting the cell in nGrid, meaning you no longer need to copy the old grid: you can just allocate an empty array instead.

    // in newGen(), replacing the call to makeCopy()
    boolean[][] nGrid = new boolean[height][width];

Or we could simplify this condition further:

            if (grid[j][i] == false) {
                // new life if 3 neighbours, else dead
                nGrid[j][i] = (neighbours == 3);
            } else {
                // still alive if 2 or 3 neighbours, else dead
                nGrid[j][i] = (neighbours == 2) || (neighbours == 3);
            }

or even flipping the logic slightly:

            // New cell is alive if it has three neighbours, regardless whether it was
            // dead or alive before, or if it was already alive and has two neighbours.
            nGrid[j][i] = (neighbours == 3) || (grid[j][i] && (neighbours == 2));

although I appreciate the previous way is a clearer statement of the rules.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.