What is the Java game of life?

396    Asked by LucasJackson in Java , Asked on Oct 13, 2022

 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):


Any live cell with fewer than two live neighbors dies, as if by underpopulation.

Any live cell with two or three live neighbors live on to the next generation.

Any live cell with more than three live neighbors dies, as if by overpopulation

Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Overview:


A different outlook on Conway's Game of Life

Unspoken rules

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 stackCells;
    HashMap hmapCells;
    public gameOfLife(int d, Stack 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> it=hmapCells.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry 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>                for(int j = startY; j < endY>                    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;
}
Simulation.java
package first;
import java.util.Stack;
public class Simulation {
    public static void main(String args[]) throws InterruptedException{
        int dim = 70;
        Stack 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("33[H33[2J");  
        }
    }
}


Answered by Michael Robinson

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:

Java game of life
/**
 * 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 indexesOfCellsAliveAtNextGeneration;
    private HashMap cellsMaybeAliveAtNextGeneration;
    public GameOfLife(int d, Stack 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 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 ;
    }
    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 xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed>

I mostly renamed some variables/methods and introduced some utility methods. The code is a bit longer and 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.



Your Answer