Prologue

Game of Life is basically a cellular automation model created by British mathematician John Horton Conway back in the 70s.

This is basically a computer game, more precisely a zero-player computer game.

But how the game works if there are no players to play?

The answer to this question is simple – It has an initial state and a set of well-defined rules and with no further input its state transition is determined by the initial state and the set of rules.

In Game of Life, we have a Two Dimensional (2D) grid of cells and each of the cells have a definite state. Say either ON or OFF or more clearly a cell in Game of Life can be ALIVE or DEAD. Let’s take a look at the below images.

As you can see there are black cells and white cells. Black cells have state ALIVE and white cells have state DEAD. In the initial state, there are 80 cells ALIVE and 320 cells DEAD. Consider the 25th state or generation. There are 48 cells ALIVE and 352 cells DEAD. And at the 100th generation, there are only 8 cells ALIVE and we can say they achieved stability.

I know the above set of images doesn’t help us understand what is happening. So consider another grid of size 128 * 128 and State transition from 81 till 100. Slide through each of the images.

This slideshow requires JavaScript.

As you can see from the slide, a certain number of patterns expands or reduce in adjacent generations, some patterns oscillate between generations, some patterns move upward or downward or diagonal and some patterns stay as such till the end.

Rules

The rules are very simple and based on a number of criteria’s.

  • There should not be overpopulation
  • Initial state should be chaotic and outcomes should be unpredictable
  • Self-replication should be possible

In a state transition from M to N

  • A cell can go from ALIVE state to DEAD state
  • A cell can go from DEAD state to ALIVE state
  • A cell can stay in ALIVE or DEAD state

This transitions of the cell state are defined by the number of neighbor cells which are ALIVE.

How do we calculate neighbor count?

Simple, take a cell in the grid, it will have a maximum of eight nearest neighbor cells and count which all cells are alive.

Once we are done with the neighbor counting, it is time to apply the rules to do the transitions.

I think it would be nice if we consider it as an algorithm and I am a bit tired of using unordered lists. Let’s have a look.

neighborCount <- getNeighborCount(prevGrid, x, y)
if prevGrid[x,y].isAlive()
begin
    if neighborCount < 2
    begin
        newGrid[x,y].setState(DEAD)
    else if neighborCount > 3
        newGrid[x,y].setState(DEAD)
    else if negihborCount == 3 or neighborCount == 2
        # No Transitions
        newGrid[x,y].setState(ALIVE)
    end
else
    if neighborCount == 3
    begin
        newGrid[x,y].setState(ALIVE)
    end
end

This algorithm is the backbone of the Game of Life and it is simply a set of rules and it is given below.

  1. If there is overpopulation or underpopulation the living cell dies.
  2. If there is exactly three living neighbors, the dead cell become alive

Now go through the above algorithm again, you will understand it a bit clearer if it wasn’t during the first time.

Getting bored? Take a look at the below Wikipedia page to understand the commonly occurring patterns and background details.

https://en.wikipedia.org/wiki/Conway’s_Game_of_Life

So what is next?

Above given explanation is a bit more theoretical and so I have included the generator methods in this article. For implementing this I have used the Java programming language. Along with this for drawing and graphics related operations, I used one of the popular visual arts programmings library or precisely a language written in Java programming language called Processing. It is simple and easy to code language and if you know Java things are easy. Please take a look at the below link to get details about Processing language.

https://processing.org/

Thank you for reading this article. If you like to see the generator class methods you can have a look here.

package main;
import java.util.Random;
/**
* Algorithms for Game of Life is implemented here.
* @version 1.0
* @author Seyed Sahil
*/
public final class Generator {
/**
* @return Creates a 2D grid of cells and make a part of the cells alive.
* If the grid width is W and grid height is H, then the number of cells
* which are alive in the initial state will be calculated using equation ((W * H) / D).
* W = 10, H = 10 and D = 10, then the number of cells which are alive will be 10.
*/
public static Cell[][] getInitialState() {
Cell[][] grid = new Cell[Constants.BOARD_WIDTH][Constants.BOARD_HEIGHT];
for (int i = 0; i < Constants.BOARD_WIDTH; i++) {
for (int j = 0; j < Constants.BOARD_HEIGHT; j++) {
grid[i][j] = new Cell(Constants.STATE_DEAD);
}
}
Random numberGenerator = new Random();
int counter = Constants.BOARD_WIDTH * Constants.BOARD_HEIGHT / Constants.DIVISOR;
while (counter > 0) {
int i = numberGenerator.nextInt(Constants.BOARD_WIDTH);
int j = numberGenerator.nextInt(Constants.BOARD_HEIGHT);
if (grid[i][j].getState() != Constants.STATE_ALIVE) {
grid[i][j].setState(Constants.STATE_ALIVE);
counter--;
}
}
return grid;
}
/**
* Produce the next generation 2D grid by using the 2D grid from the previous generation.
* Using the previous generation grid it calculates the number of neighbors for each cell.
* Then using the neighbor count it build the new 2D grid. Rules of Game of Life are applied
* by this method using neighbor count.
* @see #copyGeneration(Cell[][])
* @see #getNeighborCount(Cell[][], int, int)
* @param previousGrid
* @return New 2D grid created for the next generation.
*/
public static Cell[][] getNextGeneration(final Cell[][] previousGrid) {
Cell[][] newGrid = Generator.copyGeneration(previousGrid);
for (int i = 0; i < Constants.BOARD_WIDTH; i++) {
for (int j = 0; j < Constants.BOARD_HEIGHT; j++) {
int neighborCount = Generator.getNeighborCount(previousGrid, i, j);
if (previousGrid[i][j].getState() == Constants.STATE_ALIVE) {
if (neighborCount < 2) {
newGrid[i][j].setState(Constants.STATE_DEAD);
} else if (neighborCount > 3) {
newGrid[i][j].setState(Constants.STATE_DEAD);
}
} else {
if (neighborCount == 3) {
newGrid[i][j].setState(Constants.STATE_ALIVE);
}
}
}
}
return newGrid;
}
/**
* Make a copy of existing 2D grid of cells.
*
* @param grid
* @return The new copy.
*/
private static Cell[][] copyGeneration(final Cell[][] grid) {
Cell[][] copyGrid = new Cell[Constants.BOARD_WIDTH][Constants.BOARD_HEIGHT];
for (int i = 0; i < Constants.BOARD_WIDTH; i++) {
for (int j = 0; j < Constants.BOARD_HEIGHT; j++) {
copyGrid[i][j] = new Cell(grid[i][j].getState());
}
}
return copyGrid;
}
/**
* Calculate number of alive neighbor cells for a cell in the {@code grid} identified by
* {@code i} and {@code j}. Neighbor count will never be negative.
* @param grid
* @param i
* @param j
* @return The number of neighbors of the current cell.
*/
private static int getNeighborCount(Cell[][] grid, int i, int j) {
int neighborCount = 0;
for (int ii = i - 1; ii <= i + 1; ii++) {
for (int jj = j - 1; jj <= j + 1; jj++) {
try {
Cell usableCell = grid[ii][jj];
if (usableCell.getState() == Constants.STATE_ALIVE) {
neighborCount++;
}
} catch (ArrayIndexOutOfBoundsException ex) {
// No need to process this exception.
}
}
}
if (grid[i][j].getState() == Constants.STATE_ALIVE) {
neighborCount--;
}
return neighborCount;
}
}
view raw Generator.java hosted with ❤ by GitHub

If you have any suggestion ā€“ let it be anything related to my writing or the content or doubts, leave it as a comment here šŸ™‚

Thanks

Seyed Sahil

 

Advertisement