Cellular automaton mini framework and Conway’s Game of Life implementation

In this article I am going to create mini cellular automaton framework and then implement Conway’s game of life with it.  I will try to put attention to proper coding techniques, API design,  OOP and code documentation so its not only about cellular automaton but also about my thought process when I design new application.

Lets get started. First of all what is cellular automaton? Let’s look at wikipedia:

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays.

A cellular automaton consists of a regular grid of cells, each in one of a finite number of states, such as on and off (in contrast to a coupled map lattice). The grid can be in any finite number of dimensions. For each cell, a set of cells called its neighborhood is defined relative to the specified cell. An initial state (time t=0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously, though exceptions are known, such as the stochastic cellular automaton and asynchronous cellular automaton.

In other words it is a grid of cells and each cell changes its state during time iteration according to certain rules.

I want API to be as simple as possible and my goal is that it should work like this for any automaton at the end of the day:

World<Boolean> world = // create world implementation

for (int i = 0; i < 1000; i++) {
            Thread.sleep(100);
            world.nextState();
}

I don’t know if World is the best name for grid of cells abstraction but decided to use it anyway.

So the main classes will be  World and Cell .  Lets create them. Because I promised mini framework in the title I’m looking for a flexible solution and will create interfaces first which later can be implemented according to our needs.


public interface Cell<T> {
    
    T getValue();
    
    void revaluateCell();

    void commitRevaluation();
    
}

public interface World<T> {

    public void nextState();
    
    public void addPattern(Pattern pattern, Coordinates coordinates);
    
    public Cell<T> getCell(Coordinates coordinates);

}

World of course has method nextState() which is used for iterating through states and also provide additional methods for cell retrieval based on its coordinates and addition of new pattern. Cell can return its value with getValue() method. Also it is capable of reevaluating itself and then commit new reevaluated value. The reason for such design is that I want each cell to be “smart” and handle its own value independently. The 2 step process of reevaluation and commit is required because in most cases cell reevaluates itself depending on other cells in the world. That means that cell cannot commit its value before all cells reevaluate theirs first otherwise cell’s states would be inconsistent.  Lets see how such cell’s  implementation looks like:

public class SimpleCell<T> implements Cell<T> {

    private T value;

    private T revaluatedValue;

    private CellularAutomatonRule<T> rule;

    private Coordinates cellCoordinates;

    private World<T> world;

    public SimpleCell(T value, CellularAutomatonRule<T> rule,
            Coordinates cellCoordinates, World<T> world) {
        super();
        this.value = value;
        this.rule = rule;
        this.cellCoordinates = cellCoordinates;
        this.world = world;
    }

    @Override
    public T getValue() {
        return value;
    }

    @Override
    public void revaluateCell() {
        revaluatedValue = rule.calculateNewValue(value, world, cellCoordinates);
    }

    @Override
    public void commitRevaluation() {
        value = revaluatedValue;
        revaluatedValue = null;
    }

}

public interface CellularAutomatonRule<T> {
    T calculateNewValue(T currentValue, World<T> grid, Coordinates coordinates);
}
public interface Coordinates {
    int[] getCoordinates();
}

This SimpleCell implementation should be enough for most of the simple use cases. Here we have added two new abstractions – Coordinates and CellularAutomatonRule. Coordinates tells us where the Cell is in the world. Even though most often cellular automatons are in 2D grid world we want the design which allows any dimension and any type of Cell.  CellularAutomatonRule implementations defines rules how cell changes its value from one step to the next. In perfect world and perfect framework this should be the only class that has to be implemented when creating a new custom automaton.

Because each class should be responsible for only one thing lets add last abstraction – WorldGui.

public interface WorldGui<T> {
    public void showWorld(World<T> world);
}

It has only one method called showWorld() which must be invoked after each iteration to display World in a new state for the user. Today I will implement very simple text GUI just to show Conway’s game of life but because we code to abstraction it is very easy to replace it with other types of more interesting GUIs for example Swing.

So with current design our framework is used like this: user implements CellularAutomatonRule which defines what his automaton is doing and how each Cell changes its values. Then he constructs World which contains Cells of certain value type. Ideally all required World and Cell implementations are already provided by framework and can be simply reused. Then he simply iterate and invoke World.nextState() and WorldGui.showWorld() methods. And that is it.

OK lets implement interfaces we have left. Here is implementation of simple 2D coordinates which is really simple and self explanatory:

public class XYCoordinates implements Coordinates {

    private int x;
    private int y;

    public XYCoordinates(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

    @Override
    public int[] getCoordinates() {
        return new int[] { x, y };
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

}

Now World implementation for 2d grid world. As you can see here we have 2 classes SimpleTwoDimensionalGrid which is abstract class and SimpleBooleanGridWorld which extends SimpleTwoDimensionalGrid. The reason for this is to encapsulate all logic for 2d worlds in abstract class and reuse it later with various types of cells. In this example we create 2d world with cells with boolean values.

public abstract class SimpleTwoDimensionalGrid<T> implements World<T> {

    private Cell<T>[][] worldGrid = null;
    
    private int height;

    private int lenght;
    
    private CellularAutomatonRule<T> rule;

    @SuppressWarnings("unchecked")
    public SimpleTwoDimensionalGrid(int height, int length, CellularAutomatonRule<T> rule) {
        super();
        this.height = height;
        this.lenght = length;
        this.rule = rule;
        this.worldGrid = new Cell[height][lenght];
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < lenght; x++) {
                worldGrid[y][x] = createNewCell(new XYCoordinates(x, y), rule);
            }
        }
    }

    @Override
    public void nextState() {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < lenght; j++) {
                worldGrid[i][j].revaluateCell();
            }
        }
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < lenght; j++) {
                worldGrid[i][j].commitRevaluation();
            }
        }
    }

    @Override
    public Cell<T> getCell(Coordinates coordinates) {
        XYCoordinates gridCoordinates = (XYCoordinates) coordinates;
        return worldGrid[gridCoordinates.getY()][gridCoordinates.getX()];
    }
    
    @Override
    public void addPattern(Pattern pattern, Coordinates coordinates) {
        @SuppressWarnings("unchecked")
        T[][] patternValues = ((GridPattern<T>)pattern).get();
        XYCoordinates gridCoordinates = ((XYCoordinates)coordinates);
        for (int y = gridCoordinates.getY(); y < getHeight() && y < gridCoordinates.getY() + patternValues.length; y++) {
            for (int x = gridCoordinates.getX(); x < getLenght() && x < gridCoordinates.getX() + patternValues[0].length; x++) {
                worldGrid[y][x] = new SimpleCell<T>(patternValues[y - gridCoordinates.getY()][x - gridCoordinates.getX()], rule, new XYCoordinates(x, y), this);
            }
        }
    }

    public int getHeight() {
        return height;
    }

    public int getLenght() {
        return lenght;
    }
    
    protected abstract Cell<T> createNewCell(XYCoordinates coordinates, CellularAutomatonRule<T> rule);
}

public class SimpleBooleanGridWorld extends SimpleTwoDimensionalGrid<Boolean> {
    public SimpleBooleanGridWorld(int height, int length, CellularAutomatonRule<Boolean> rule) {
        super(height, length, rule);
    }

    @Override
    protected Cell<Boolean> createNewCell(XYCoordinates coordinates, CellularAutomatonRule<Boolean> rule) {
        return new SimpleCell<Boolean>(false, rule, coordinates, this);
    }
}

public interface Pattern {
    Object get();
}
public abstract class GridPattern<T> implements Pattern {
    public abstract T[][] get();
}
public class ToadPattern extends GridPattern<Boolean> {
    @Override
    public Boolean[][] get() {
        return new Boolean[][] {{false, true, true, true}, {true, true, true, false}};
    }
}

Code is pretty much self explanatory.  In constructor we create a new 2 dimensional array and fill it by invoking createNewCell() method for each position.  SimpleBooleanGridWorld returns SimpleCell with Boolean type value.  And in nextState() method we simply iterate through each cell two times – first to reevaluate and then commit new value.  Also World has the method to add some custom patterns to it so I have added some sample Pattern interface implementations.

For GUI I am a bit lazy and will create very simple text GUI with simple System.out.println().  It is printing grid world and then it is printing empty lines. If everything is correct this creates textual animation.

public class TextBooleanGridWorldGui implements WorldGui<Boolean> {

    @Override
    public void showWorld(World<Boolean> world) {
        SimpleBooleanGridWorld booleanGridWorld = (SimpleBooleanGridWorld)world;
        for (int y = 0; y < booleanGridWorld.getHeight(); y++) {
            for (int x = 0; x < booleanGridWorld.getLenght(); x++) {
                System.out.print(booleanGridWorld.getCell(new XYCoordinates(x, y)).getValue() ? "@" : "-");
            }
            System.out.println();
        }
        for (int y = 0; y < booleanGridWorld.getHeight(); y++) { // print empty lines to separate different states (if its large enough it will create animation for changing states)
            System.out.println();
        }
    }

}

And last interface to implement before running our example is of course CellularAutomatonRule:

public class ConwaysGameOfLifeRule implements CellularAutomatonRule<Boolean> {
    
    private static Cell<Boolean> EMPTY_CELL = new SimpleCell<Boolean>(false, null, null, null);

    @Override
    public Boolean calculateNewValue(Boolean currentValue, World<Boolean> world, Coordinates coordinates) {
        XYCoordinates gridCoordinates = (XYCoordinates)coordinates;
        SimpleTwoDimensionalGrid<Boolean> gridWorld = (SimpleBooleanGridWorld)world;
        int sum = (getUpperNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0) + (getLowerNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0)
                + (getLeftNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0) + (getRightNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0)
                + (getUpperLeftNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0) + (getUpperRightNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0)
                + (getLowerLeftNeigbhor(gridWorld, gridCoordinates).getValue() ? 1 : 0) + (getLowerRightNeigbhor(gridWorld, gridCoordinates).getValue() ? 1 : 0);
        return currentValue ? sum == 2 || sum == 3 : sum == 3;
    }
    
    private Cell<Boolean> getUpperNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX();
        int neighborY = coordinates.getY() - 1;
        return (neighborY >= 0) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getLowerNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX();
        int neighborY = coordinates.getY() + 1;
        return (neighborY < world.getHeight()) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getLeftNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() - 1;
        int neighborY = coordinates.getY();
        return (neighborX >= 0) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getRightNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() + 1;
        int neighborY = coordinates.getY();
        return (neighborX < world.getLenght()) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getUpperLeftNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() - 1;
        int neighborY = coordinates.getY() - 1;
        return (neighborX >= 0 && neighborY >= 0) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getUpperRightNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() + 1;
        int neighborY = coordinates.getY() - 1;
        return (neighborX < world.getLenght() && neighborY >= 0) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getLowerLeftNeigbhor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() - 1;
        int neighborY = coordinates.getY() + 1;
        return (neighborX >= 0 && neighborY < world.getHeight()) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getLowerRightNeigbhor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() + 1;
        int neighborY = coordinates.getY() + 1;
        return (neighborX < world.getLenght() && neighborY < world.getHeight()) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

}

Implementation of ConwaysGameOfLifeRule provides some getters to retrieve cell’s neighbors. In calculateNewValue() method it returns new value of the cell according to the Conway’s game of life rules which are following:
1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

And that’s it. Lets create main method and see Conway’s game of life in action:

public class Main {
    
    public static void main(String[] args) throws IOException, InterruptedException {
        WorldGui<Boolean> gui = new TextBooleanGridWorldGui();
        World<Boolean> world = new SimpleBooleanGridWorld(30, 100, new ConwaysGameOfLifeRule());
 world.addPattern(new ToadPattern(), new XYCoordinates(15, 15));
        gui.showWorld(world);
        for (int i = 0; i < 1000; i++) {
            Thread.sleep(100);
            world.nextState();
            gui.showWorld(world);
        }
    }

}

Pretty much as I wanted. If you run it from your eclipse you might see your toad pattern  similar to this (if you have not implemented your own GUIclass) :

toad

You can read more about game of life and its other patterns in wikipedia.

So what if you want one dimensional or 3d automaton. Well you will need implement all classes e.g create 3dCoordinates, 3D World, 3DGui etc. Same goes for different values of the cell. It can be as simple as boolean or as complex as you want when creating value class. And the good news is after you do this, its easy just to change rule class and experiment with different cellular automatons. However in most cases 2d grid automatons should be enough 🙂

So this article was not only about cellular automaton but also about OOP and my thought process when designing new application. I hope you liked it and learned something from it. I welcome any criticism, remarks, ways to improve, suggestions, bugfixes etc. If you implement different kinds of cellular automatons on top of it let me know! All code can be downloaded from Github!

You might wonder how cellular automatons can be used in practice. It is useful for doing various kinds of simulations. For example traffic simulation or electronic circuits simulation or some particles movement simulation etc. You could even try to play with cellular automatons and try to create some music!

In the next article I will try to implement something more interesting with automaton – simplified stock market simulation. Cheers!

Advertisements