Cellular automata I : Conway's Game of Life

Cellular automata vary a fair bit in definition, depending on how broad one wants to make it, but overall, for a rather broad definition, a cellular automaton is some kind of discrete topological space (generally a manifold equipped with a tesselation), where each cell of the tesselation has a state out of a possible number of defined states, and those states will evolve according to some set of rules related to the states of its neighbours.

To simplify things somewhat, let's consider the simplest case, caled Life-like automatons. Life-life automatons are characterized by the following :

The space is a two-dimensional grid, either on the plane, or, for actual implementations, a rectangle or torus, with a square tesselation.
There are only two states, refered to as live and dead states.
Each cell's evolution is only influenced by the Moore neighbourhood.
The change of state of a cell only depends on the number of live cells surrounding it.

The neighbours on the plane are generally the simplest ones : either the four squares neighbouring the cell vertically and horizontally (the von Neumann neighbourhood), or the eight closest cells (the Moore neighbourhood).

Conway's game of life

Conway's game of life is the most famous of cellular automaton. It was made to study self-replicating systems, being loosely based on biological life. The rules for it are fairly simple. There are two states : a cell is either "alive" or "dead' (represented later on by a black or white cell), and the neighbourhoods are Moore neighbourhoods. Every tick, each cell evolves according to those rules.

If a cell is alive and it has less than two alive neighbours, it dies of underpopulation.
If a cell is alive and it has more than three neighbours, it dies of overpopulation.
If a cell is alive and has two or three neighbours, it will remain alive.
If a cell is dead and has exactly three neighbours, it will become alive through reproduction.

Those rules were designed to have complex behaviour without becoming chaotic, as most cellular automata with random rules will either settle in a single state or produce seemingly random patterns.

Implementing it is fairly straightforward, although we'll need to use a temporary grid since the sum of neighbours is done with the states of the previous tick. If we consider the grid to be an array with the alive state represented by 1 and the dead state by 0,

Javascript

function updateGrid()
{
	var tmpGrid = [];
	for(var i = 0; i < gridSize; i++)
	{
		var sum = sumNeighbours(i, 1);
		if(grid[i] == 1)
		{
			tmpGrid[i] = (sum < 2 || sum > 3)?0:1;
		}
		else
		{
			tmpGrid[i] = (sum == 3)?1:0;
		}
	}
	for(var i = 0; i < t; i++)
	{
		grid[i] = tmpGrid[i];
	}
}

The computation of the total number of neighbourhoods is not terribly more complex, but as we will use a finite grid, it will require some checks. This is not the best possible implementation, as a lot of those checks are unnecessary (we only need to check for the edges for a very limited number of cells), but it is easier to read than doing different loops for the inside and border of the grid.

First, here's a way to do it for a rectangular grid, just going through every neighbour that is actually on the grid :

Javascript

function sumNeighbours(i, v)
{
	var sum = 0;
	var xi = i % w;
	var yi = Math.floor(i / w);
	for(var x = xi-1; x <= xi+1; x++)
	{
		for(var y = yi - 1; y<= yi + 1; y++)
		{
			if(!(x == xi && y == yi)
				&& x >= 0 && x < w 
				&& y >= 0 && y < h
				&& grid[x + y * w] == v)
			{
				sum++;
			}
		}
	}
	return sum;
}

And here is one for a toroidal grid, where every cell outside of the grid is changed to a cell on the other side :

Javascript

function sumNeighboursTorus(i, v)
{
	var sum = 0;
	var xi = i % w;
	var yi = Math.floor(i / w);
	
	for(var x = xi-1; x <= xi+1; x++)
	{
		for(var y = yi - 1; y<= yi + 1; y++)
		{
			x2 = x;
			y2 = y;
			if(x2 < 0)		{x2 = w - 1;}
			else if(x2 == w)	{x2 = 0;}
			if(y2 < 0)		{y2 = h - 1;}
			else if(y2 == h)	{y2 = 0;}
			
			if(!(x2 == xi && y2 == yi) && grid[x2 + y2 * w] == v)
			{
				sum++;
			}
		}
	}
	return sum;
}

As the case where edges lead to nothing tend to give odd border behaviours, we'll use the torus case here.

With the addition of a few functions to display and update that grid, we can now display a finite game of life. A few interesting basic examples of it are three categories : the still lifes, oscillators and spaceships.

The still lifes are patterns that will remain static as long as they are isolated from other patterns, that is, separated by at least one empty cell. There's a handful of simple still lifes, such as the block, beehive, loaf, boat and tub. Here we can see them side by side, from left to right :

Oscillators are patterns which evolve somewhat but will go back to the same pattern every $n$ tick, with $n$ the frequency of the oscillator. Simple oscillators are the blinker, the toad, the beacon, the clock, all of period 2.

More complex oscillators with longer periods include the pulsar (of period 3), and the pentadecathlon (of period 15).

Spaceships repeat their patterns with some frequency, much like oscillators, but also get translated during the process. As every cell can only affect its direct neighbours, this limit the speed of such a translation to one cell per tick at its maximum.

The most famous spaceship (and pattern of the game of life in general) is the glider

More complex structures

Conway's game of life is Turing complete,

Reflectors

Guns

Guns are structure that will output spaceships.

Puffer trains

Rakes

Logical gates

Last updated : 2023-04-22 15:10:49

Tags : computation-theory , javascript