Java: Conway's Game of Life

Question

I have just finished implementing a version of Conway's Game of Life using Java.

Being only a college student, I am sure that my code is no where near perfect, and was wondering if you could look at my code. What can I improve on? Are there faster ways to implement certain areas of my code? Is there excess code that I can trim away? Is there a smarter way of implementing Conway's Game of Life?

EDIT:

In hopes of receiving more feedback, here is the theory behind my implementation:

For reference, here are the rules for Conway's game of life (taken from wikipedia):

1. Any live cell with fewer than two live neighbors dies, as if by underpopulation.
2. Any live cell with tow or three live neighbors live on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by overpopulation
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Overview:

1. A different outlook on Conway's Game of Life
2. Unspoken rules
3. Explanation of important methods (and data structures used)

A different outlook on Conway's Game of Life

Let us first imagine the Game of Life as a n x n grid (we will also assume that this grid has coordinates such that the bottom left hand corner is denoted as (0,0) and the top right hand corner is denoted as (n,n) where n is a positive integer). This 2-Dimensional grid represents a group of n*n number of cells. Each grid block can be thought of as a cell, which not only stores a Boolean value (dead or alive) to describe the cell’s status, but also details its location via its coordinates. In addition, the current state of all cells determines which cells will die, continue to live, or be born in the next generation in accordance to the rules found above.

In a different perspective, however, Conway’s game of life is very similar to the game minesweeper. We can think of an alive cell as a mine, and its neighbors storing the number of mines that are closest to it. In this way, we are able to easily use the rules above to determine the future generation (particularly which cells will die, and which cells will be born).

What about the cells that are currently alive you might ask? Well, we can easily represent these as an integer greater than 10, where the one’s place indicates how many alive neighbors the currently alive cell has, and the ten’s places indicates that the cell is alive.

Unspoken rules

One observation that occurred to me is that the game of life is only concerned about alive cells. Only cells that are alive can die, cells that continue to live have to already be living, and cells can only be born if they have neighbors that are alive. As a result, checking the entire grid (time complexity: O(n^2)) to determine the future generation of cells would be a complete waste. It would be a lot faster if I stored all the currently alive cells and checked each alive cell along with their neighbors to determine the next generation (which is exactly what I did).

Explanation of important methods (and data structures used)

birth(): iterates over a HashMap containing a key-value pair of all alive cells along with its neighbors. If the key-value pair follows the game of life’s rules above, the key (an integer value that represents the location of a cell) is then pushed onto a stack that contains the next generation of alive cells. After each iteration, the value of the grid is reset to 0, and the key-value pair is removed from the HashMap.

insertAlive(): pops the stack and inserts the alive cell into the grid. Inserting a live cell follows the structure of minesweeper (neighbors of a live cell will be incremented by 1 and the alive cell will be incremented by 10 to denote that it is alive). All of the neighbors and alive cells are then put into a HashMap so that birth() can run properly.

printBoard() (should be named boardToString()): uses a StringBuilder to format the grid into a string.

Note: Most comments have been taken out because they don't add much to the readability of the code.

CellularAutomaton.java

package first;
public abstract class CellularAutomaton{
    public abstract String lifeCycle();
    public abstract boolean rules(int num);
}

GameOfLife.java

package first; 
import java.util.Stack;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class GameOfLife extends CellularAutomaton {

    int board[][];
    int dim;
    Stack<Integer> stackCells;
    HashMap<Integer, Integer> hmapCells;

    public gameOfLife(int d, Stack<Integer> s){
        board = new int[d][d];
        dim = d;
        stackCells = s;
        hmapCells = new HashMap<>();
    }

    public boolean rules(int num){
        return num == 3 || num == 12 || num == 13;
    }

    private void birth() {
        Iterator<Map.Entry<Integer,Integer>> it=hmapCells.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry<Integer,Integer> pair = it.next();
            int key = pair.getKey();

            if(rules(pair.getValue())){
              stackCells.add(key);
            }

            board[key/dim][key%dim] = 0;
            it.remove();
        }
    }

    private void insertAlive() {
        while(!stackCells.isEmpty()) {
            int cell = stackCells.pop();

            int x = cell / dim;
            int y = cell % dim;
            int startX = (x <= 0) ? 0 : x - 1;
            int startY = (y <= 0) ? 0 : y - 1;
            int endX = (x >= dim - 1) ? x + 1 : x + 2;
            int endY = (y >= dim - 1) ? y + 1 : y + 2;
    
            for(int i = startX; i < endX; ++i) {
                for(int j = startY; j < endY; ++j) {
                    hmapCells.put(i * dim + j, ++board[i][j]);
                }
            }
            hmapCells.put(cell, board[x][y] += 9);
        }
    }

    private String printBoard() {
        StringBuilder s = new StringBuilder();
        
        for(int elements[] : board) {
            for(int element : elements) {
                if(element >= 10){
                    s.append("* ");
                }
                else {
                    s.append("  ");
                }
            }
            s.append("\n");
        }
        
        return s.toString();
    }

    public String lifeCycle() {
        birth();
        insertAlive();
        return printBoard();
    }
}

Simulation.java

package first;

import java.util.Stack;

public class Simulation {
    public static void main(String args[]) throws InterruptedException{
        int dim = 70;
        Stack<Integer> init = new Stack<>();

        //all vals pushed to init is of the form: xPos * dim + yPos
        init.push(351);
        init.push(352);
        init.push(421);
        init.push(422);

        init.push(245); 
        init.push(246); 
        init.push(315); 
        init.push(316); 
        
        init.push(361); 
        init.push(431); 
        init.push(501); 
        init.push(292); 
        init.push(572);
        init.push(223); 
        init.push(643);
        init.push(224); 
        init.push(644);
        init.push(435);
        init.push(296);
        init.push(576);
        init.push(367);
        init.push(437);
        init.push(507);
        init.push(438);

        init.push(231);
        init.push(301);
        init.push(371);
        init.push(232);
        init.push(302);
        init.push(372);
        init.push(163);
        init.push(443);
        init.push(165);
        init.push(445);
        init.push(95);
        init.push(515);

        GameOfLife gOL = new GameOfLife(dim, init);

        while(true) {
            System.out.print(gOL.lifeCycle());
            Thread.sleep(100);
            System.out.print("\033[H\033[2J");  
        }
    }
}

Answer 1

First of all, I think the algorithm is pretty smart which is, for my humble experience, not so common for a college student. So congrats if you came up with it by yourself! If you're looking for smart implementations I would recommend functional ones, e.g. in Haskell; see also Shortest game of life.

Now, beware of smartness. A good code should be easy to read, easy to understand. This is of course not always possible when dealing with complex algorithm but I believe that it should be a target.

jjjjjjjjjjjj said:
Note: most comments have been taken out because they don't add much to the readability of the code

The point of comments is to help people understand your code (generally speaking, focus on the "why" rather than on the "what"). Here, to help people understand you had to add a lot of text to your post. Ideally this isn't needed because the code is:

• self-documented,
• commented to clear complex/implicit stuff up.

For instance, here is a quick rewrite of your code in an attempt to make the code more expressive:

GameOfLife.java

/**
 * Computes the next state of the automaton by using Conway's original rules.
 */
public class GameOfLife extends CellularAutomaton {

    /**
     * Stores all cells in a two-dimensional matrix. The value stored is
     * the number of live neighbors of the cell, +10 if the cell is alive.
     */
    private int board[][];
    private int dim;
    /*
     * index(cell) = cellX * dim + cellY
     */
    private Stack<Integer> indexesOfCellsAliveAtNextGeneration;
    private HashMap<Integer, Integer> cellsMaybeAliveAtNextGeneration;

    public GameOfLife(int d, Stack<Integer> s){
        board = new int[d][d];
        dim = d;
        indexesOfCellsAliveAtNextGeneration = s;
        cellsMaybeAliveAtNextGeneration = new HashMap<>();
    }

    public String newGeneration() {
        populateWorldWithAliveCellsFromPreviousGeneration();
        computeCellsMaybeAliveAtNextGeneration();
        return boardAsString();
    }

    private void populateWorldWithAliveCellsFromPreviousGeneration() {
        for (Map.Entry<Integer, Integer> cell : cellsMaybeAliveAtNextGeneration.entrySet()) {
            int cellIndex = cell.getKey();
            int cellValue = cell.getValue();
            
            if(willBeAlive(cellValue)){
              indexesOfCellsAliveAtNextGeneration.add(cellIndex);
            }

            board[cellIndex/dim][cellIndex%dim] = 0;
        }
    }

    private static boolean willBeAlive(int cell){
        return (!isAlive(cell) && nbOfNeighbors(cell) == 3) 
            || (isAlive(cell) && (nbOfNeighbors(cell) == 2 || nbOfNeighbors(cell) == 3));
    }
    
    private static boolean isAlive(int cell) {
        return cell >= 10;
    }
    
    private static int nbOfNeighbors(int cell) {
        return cell % 10;
    }

    private void computeCellsMaybeAliveAtNextGeneration() {
        cellsMaybeAliveAtNextGeneration.clear();

        while(!indexesOfCellsAliveAtNextGeneration.isEmpty()) {
            int cellIndex = indexesOfCellsAliveAtNextGeneration.pop();

            int cellX = cellIndex / dim;
            int cellY = cellIndex % dim;
            int topLeftNeighbourX = (cellX <= 0) ? 0 : cellX - 1;
            int topLeftNeighbourY = (cellY <= 0) ? 0 : cellY - 1;
            int bottomRightNeighbourX = (cellX >= dim - 1) ? cellX + 1 : cellX + 2;
            int bottomRightNeighbourY = (cellY >= dim - 1) ? cellY + 1 : cellY + 2;

            // Iterate through every cell's neighbor to increate their neighbor number

            for(int i = topLeftNeighbourX; i < bottomRightNeighbourX; ++i) {
                for(int j = topLeftNeighbourY; j < bottomRightNeighbourY; ++j) {
                    boolean isNeighbor = i != cellX || j != cellY;
                    if (isNeighbor) {
                        int neighborIndex = i * dim + j;
                        cellsMaybeAliveAtNextGeneration.put(neighborIndex, incrementedNumberOfNeighbors(i, j));
                    }
                }
            }
            cellsMaybeAliveAtNextGeneration.put(cellIndex, makeAlive(cellX, cellY));
        }
    }
    
    private int incrementedNumberOfNeighbors(int x, int y) {
        return ++board[x][y];
    }
    
    private int makeAlive(int x, int y) {
        return board[x][y] += 10;
    }

    private String boardAsString() {
        StringBuilder s = new StringBuilder();

        for(int[] cells : board) {
            for(int cell : cells) {
                if(isAlive(cell)){
                    s.append("* ");
                }
                else {
                    s.append("  ");
                }
            }
            s.append("\n");
        }

        return s.toString().trim();
    }
}

I mostly renamed some variables/methods and introduced some utility methods. The code is a bit longer ands feels more verbose but is IMHO also easier to understand. It is still very procedural (which is not bad per se, especially for such a simple program) but you may want to try to add more expressiveness by introducing new classes such as Board or Cell. You'll find such OO implementations on GitHub.

Your code may also run into memory issues with large boards. Indeed, your board[][] variable stores all the cells, even dead ones. With a 10000 x 10000 board containing only ~5/6 cells you'll waste a lot of memory. A solution is to use a sparse array (basically, a set containing only alive cells).

As a side note, a few years ago I also tried to model a highly-configurable GoL in a "pure" OO way; my code is on GitHub if you want to check it out. The method computing the next generation of the world is ImmutableGeneration::nextGeneration; given a set of alive cells, it basically: 1) compute all neighbors cells then 2) keep only those that will be alive. Rules indicating whether a cell will be alive or dead are implemented in Rule.java.

---

EDIT: personal opinion on conciseness versus verbosity when it comes to naming to answer a comment

First of all, I believe that there are no right answers: it's all about tradeoffs and personal preferences. Naming is hard and you'll find plenty of articles on the subject.

There are only two hard things in Computer Science: cache invalidation and naming things
— Phil Karlton

My take is that conciveness is pleasant but can lead to ambiguities. And ambiguity, especially hidden one, is a threat. The first example that comes to my mind is mistakenly mixing units:

// Everything looks good...
double pathLength = distanceFromGoal + distanceToTarget;

// ... but adding units makes easy to spot bugs
double pathLengthInKilometers = distanceFromGoalInMeters + distanceToTargetInMillimeters;

That being said, long names do make the code harder to read. They can be reduced by taking two things into account:

• the context (e.g. name of the enclosing method / class / package),
• the scope (a local variable in a 3-line method may be fine with a short name whereas a function used multiple times across the whole codebase may need a longer one).

That's also what is advised by Google's naming conventions.

As a last note, as you suggested very long names may be seen as code smells. Usually, the issue is a lack of cohesion (the class/method does too much different things — once again, no clear metrics on this, it's up to developer's feeling). For instance, in the code I proposed we may think of populateWorldWithAliveCellsFromPreviousGeneration as a method holding responsibilities: 1) computing the cells that will be alive at the next generation and 2) populating the world. We could thus split it in two: populateWorldWith(aliveCellsFromPreviousGeneration()).

In the same way we could gather the attributes which name ends with "atNextGeneration" under a new Generation class:

public class GameOfLife extends CellularAutomaton {

    private Generation lastGeneration;

    public String newGeneration() {
        this.lastGeneration = lastGeneration.nextGeneration();
        return this.lastGeneration.toString();
    }
}

public class Generation {

    public Generation nextGeneration() {
        return new Generation(aliveAtNextGeneration(this.aliveCells));
    }

    ...

}

But splitting the logic into too much classes will also increase the architecture complexity and make harder to understand the flow.

As a conclusion I would advise you to keep in mind that any piece of code is susceptible to be modified by developers having no previous knowledge on the project and who must understand what the code does and why it does it so that they can maintain it or reuse parts without introducing regressions. There's no silverbullet: only tradeoffs, and what matters when you make a choice is that:

• you can identify the tradeoff,
• you understand the pros and cons of each alternative and choose one of them knowingly.

(but don't push too much pressure on you: KISS and remember that code can be refactored thereafter)

Answer 2

I just have one small recommendation regarding readability. When you have a method called printBoard, you would normally expect it to print out the board. A better name for that method would be boardToString.