Conway's Game of Life - A Rule Framework and Implementation

• Download source code - 43 KB
• Download executable - 13 KB

Introduction

The Game of Life is not your typical computer game. It is a 'cellular automaton', and was invented by Cambridge mathematician John Conway. The "game" is actually a zero-player game, meaning that its evolution is determined by its initial state, needing no input from human players. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.

This game became widely known when it was mentioned in an article published by Scientific American in 1970. It consists of a collection of cells which, based on a few mathematical rules, can live, die or multiply. Depending on the initial conditions, the cells form various patterns throughout the course of the game. For an introduction, you can watch the video fragment from Stephen Hawkings The Meaning of Life. 

Background

John Conway extended the work of John von Neumann who had created a machine that operated on a board that could create copies of itself. The rules that Neumann's machine operated under were much more complicated than the rules in Conway's Game of Life.

The game of life became very famous soon after its creation. Many become fascinated by the fact that the very simple rules that the cells operate under could create order out of chaos and that so complicated patterns could evolve. When home computers become popular soon after the game was published, a lot of implementations become available and the game becomes a popular screen server.

Conway's game of life is however not only fascinating to look at but is of theoretic interest for mathematics physics, philosophy, economy and many other scientific fields. E.g. it is one of the most famous examples of cellular automata which has become a popular topic to study in computability theory. See Wikipedia for a more in depth article about Conway's game of life.

The Problem of 'Game of life' 

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbors dies, as if by loneliness.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
4. Any dead cell with exactly three live neighbors comes to life.
   -- Extended rule (not part of original definition) to show pluggable rule engines
5. Any dead cell with age > 3 dies (additional rule). Every generation creates an age for the cells

The initial pattern constitutes the 'seed' of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed — births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick. (In other words, each generation is a pure function of the one before.) The rules continue to be applied repeatedly to create further generations.

The inputs below represent the cells in the universe as X or - . X is a alive cell. - is a dead cell or no cell . The below inputs provide the provide pattern or initial cells in the universe . The output is the state of the system in the next tick (one run of the application of all the rules), represented in the same format.

Here are a few illustrations from http://www.conwaylife.com/wiki/Conway's_Game_of_Life.

Block(still life)	Blinker(oscillator)	Glider(spaceship)	Pulsar(period 3 oscillator)

Illustration of Rules

A cell C is represented by a 1 when alive or 0 when dead, in an m-by-m square array of cells. We calculate N - the sum of live cells in C's eight-location neighbourhood, then cell C is alive or dead in the next generation based on the following table:

From here http://rosettacode.org/wiki/Conway's_Game_of_Life.

Assume cells beyond the boundary are always dead.

The "game" is actually a zero-player game, meaning that its evolution is determined by its initial state, needing no input from human players. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.

Although you should test your implementation on more complex examples such as the glider in a larger universe, show the action of the blinker (three adjoining cells in a row all alive), over three generations, in a 3 by 3 grid.

This is a set of guidelines on the web about how to make the game.

This article (and code) partially follows the above guidelines and also focuses on why and how should we create generic rule processing interfaces and/or pipelines.

The last of the 5 rules mentioned above can be seen in execution in code also.

Along with the framework, there is an implementation in WPF to demonstrate the algorithm from an end-user UI perspective. Here is how it looks:

Using the Code

Now a little deep dive into the code...

The rule engine is common and depends on ITransition which looks like:

namespace gameOfLife.Framework
{
    public interface ITransition
    {
        void Apply(ITransitive cellContainer);
    }

    public interface ITransitive
    {
        void ApplyTransitions(params ITransition[] transitions);
 
        IList<Cell> Cells { get; set; }
    }  
} 

Based on this, the set of rules are implemented and chained to the order of implementation. Here is the rule 1 of the chain.

using gameOfLife.Framework;
 
namespace gameOfLife.Transition
{
    public class Loneliness : ITransition
    {
        public void Apply(ITransitive cellContainer)
        {
            //cellContainer.Cells = cellContainer.Cells.Where
            //((cell) => CanBeAlive(cellContainer.Cells, cell)).ToList();
 
            foreach (var cell in cellContainer.Cells)
            {
                if (!CanBeAlive(cellContainer.Cells, cell))
                {
                    cell.Kill();
                }
            }
        }
 
        private bool CanBeAlive(IList<Cell> otherCells, Cell cell)
        {
            return cell.NeighbouringLocations.Match(otherCells).Count > 1;
        }
    }    
}

As the board the PatternOfCells class:    

    public class PatternOfCells : ITransitive
    {
        private IList<Cell> cells = new List<Cell>();
 
        // threadsafe initialization
        private static ITransitive instance = new PatternOfCells();
 
        private PatternOfCells()
        {
        }
 
        public static ITransitive Instance
        {
            get
            {
                // do not need double lock here
                return instance;
            }
        }
 
        public void ApplyTransitions(params ITransition[] transitions)
        {
            foreach (ITransition transition in transitions)
            {
                transition.Apply(this);
            }
 
            ClearDeadCells();
        }
}

Points of Interest

The framework is useful for applications trying to implement solutions using Conway's Game of Life.

There is a custom rule also implemented. This needs to be chained to the set of execution. By default, it is not connected (in consistence to the classic Game of Life rules). The additional rule is a step beyond to make the game more interesting. You can attach the rule here:

private void InitializeTransitionIndexes()
{
      ...
      else
      {
         knownTransitions = new List<string>() 
            { "Loneliness", "OverCrowding", "NextGeneration", "Spawn", "Die" };  // "Die" has
                                                                           // to be appended
       }
}

History

• 16^th April, 2013: Initial version