Advertisement

Conway's Game of Life

An Introduction to Cellular Automata

Introduction to Cellular Automata

A Cellular automaton is a discrete model that consists of a regular grid of cells wherein each cell is in a finite state. The inital state of the cellular automate is selected by assigning a state to each cell. The simulation then progresses in discreet time steps. The state of a cell at timestep t depends only on the state of nearby cells at timestep t-1 and a set of rules specific to the automate.

Cell Neighboorhoods

The cells which have an influence on the state of the automate are called neighborhood. There are two commonly used types of neighborhoods: The Moore Neighborhood and the Van Neumann Neighborhood. The Moore neighborhood contains all neighboring cells even if they share only a cornerpoint with a cell whilst the Van Neumann Neighborhood contains only cells that share an edge with a cell.

Van Neumann Neighborhood and Moore Neighborhood
Image: Left Moore Neighborhood of the cell C. Right: Van Neumann Neighborhood.

Boundary Conditions

Cellular automata often use a toroidal topology of the simulation domain. This means that opposing edges of the grid are connected. The rightmost column is the neighbor of the leftmost column and the topmost row is the neighbor of the bottommost row and vice versa. This allows the unrestricted transfer of state information across the boundaries.

Opposing Edges of the Simulation domain are Connected
Image: Different boundary conditions of the Game Of Life; Left: Opposing edges of the grid are connected to form a toroidal topology of the simulation domain; Right: Cells beyond the grid boundary are always treated as if they were dead.

Another type of boundary condition treats nonexisting cells as if they all had the same state. In the Game of Life this would mean that nonexisting cells are treated as if they were dead (as opposed to the second state "alive"). The advantage of this boundary condition in the Game of Life is that it prevents gliders from wrapping around the edges of the simulation domain. This will prevent the destruction of a glider gun by the gliders it produces (see text below below for details about what gliders are).

Conway's Game of Life

The Game of Life is a cellular automaton devised by the british mathematician John Horton Conway in 1970. It was popularised by Martin Gardner in his October 1970 column of "Mathematical Games" in the "Scientific American" magazine [6]. The article garnered more response than any other of his previous articles in the magazine, including Gardners famous article on Hexaflexagons. John Conway gave an interesting interview on the youtube channel Numberphile [1] where he provided insight on the origins of the Game of Life. If you are interested what the terraforming of Mars has to do with the game of life I highly recommend watching it.

External Content: Video courtesy of Youtube / Numberphile

Video: John Horton Conway in an interview with the youtube channel Numberphile .

Rules

In the Game of Life each grid cell can have either one of two states: dead or alive. The Game of Life is controlled by four simple rules which are applied to each grid cell in the simulation domain:

Rules of the Game of Life

There are different ways to treat cells at the edges of the grid. Often the opposing sides of the grid are connected thus creating a toroidal topology of the simulation domain. Alternatively the neighbors of the edge cells could be treated as if they were always in the "dead" state. This is helpful when constructing "Glider Guns" to avoid destruction of the gun by the gliders wrapping around the edges.

Pattern Examples

Patterns will appear in a typical run of the Game of Life. Some patterns are static, others are oscillating or are moving across the screen. Some Patterns may even produce other patterns. The following tables give an overview on commonly appearing patterns in the Game of Life.

Still Lifes
Block:
The Block is the most common still life. It consists of four cells forming a 2x2 block. The block is a so called eater. This means it can destroy other patterns without suffering lasting damage to itself.
Beehive:
The beehive is a still life consisting of 6 cells. It is the second most common still life.
Loaf:
The loaf is a 7 cell still life. It is the third most common still life.
Oscillators
Blinker:
The smallest and most common oscillator.
Toad:
The Toad is a period 2 oscillator. It is the second most common naturally occuring oscillator.
Beacon:
The third most common naturally occuring oscillator. It is composed of two diagonally touching blocks.
Spaceships
The Glider:
The glider is a pattern that is moving diagonally across the screen. It is the smallest, most common, and first-discovered spaceship.
Lightweight spaceship (LWSS):
This is an oscillating object that is moving orthogonally across the screen. It is the smallest orthogonally moving spaceship.
Weekender:
This is an orthogonal spaceship that is slightly larger than the previous patterns.
back      next

You might also like: