Click here to Skip to main content
Click here to Skip to main content

Tagged as

Solving Conway’s Game of Life using State Pattern

, 21 Apr 2011
Rate this:
Please Sign up or sign in to vote.
An article on how to solve Conway’s Game of Life using State Pattern

Introduction

The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. The "game" is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.

Rule

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 neighbors, which are the cells that are 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 caused by under-population.
  2. Any live cell with two or three live neighbors’ lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

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 occur 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 preceding one). The rules continue to be applied repeatedly to create further generations.

The State Pattern

image001.jpg

The State Pattern is useful when we have to deal with States and handle change in states. In our problem, this would be ideal to use. The class diagram for State Design is shown above. It has an abstract State class with multiple children concrete State classes. In our case, we will have two concrete Children States – Alive, Dead.

It has a context class which deals with the decision of evaluating and handling the States.

The Approach

Since the rule of the game depends on the number of neighbors around each cell in the universe, our logic will be based on indentifying neighbors for each cell and finding their states.

  1. Identify the classes:
    1. Universe – Two dimension universe with cells as its content
    2. Cell – The Context class of our State Pattern. The cell has a state – Alive or Dead. It also has properties - Row, Column – defining its position in the Universe.
    3. Abstract State – This is the abstract class for our State. It contains an abstract method GetType which returns the type for each State.
    4. Concrete States – Alive and Dead classes
  2. Identify neighbors for each cell in the Universe – Each cell can have a maximum of 8 neighbors. The number of neighbors is defined by the position of the Cell in the two dimension grid of the Universe.
  3. Change the State of each cell in the Universe depending on the states of its neighbors based on the game rules.

The Solution

We define an abstract class State:

public abstract class State
    {
        public abstract Type GetStateType();
    }

We define the two concrete states of the Game, Alive and Dead:

public class Alive : State
    {
        public override Type GetStateType()
        {
            return this.GetType();
        }
    }

    public class Dead : State
    {
        public override Type GetStateType()
        {
            return this.GetType();
        }
    }

Next, we define the context of our states. In our case, the context would be our Cell class. The Cell class has four properties:

  1. State – Representing cell state Alive or Dead
  2. Neighbors – Neighbors of the cell
  3. Row – The row position of the cell in the universe
  4. Col – The column position of the cell in the universe
public class Cell
    {
        private State _state;
        private List<cell> _neighbors;
 
        public Cell()
        {            
            _neighbors = new List<cell>();
        }
       
        /// <summary>
        /// Constructor
        /// </summary>
        public Cell(State state) 
        {
            _state = state;
            _neighbors = new List<cell>();
        }
 
        public State State
        {
            get
            {
                return _state;
            }
            set
            {
                _state = value;
            }
        }
        public int Row { get; set; }
        public int Col { get; set; }
 
        public List<cell> Neighbors 
        {
            get { return _neighbors; }
            set { _neighbors = value; }
        }            
    }

In the end, we define our Universe class where all the action takes place.

public class Universe
    {
        private int _dimRow, _dimCol;
        private List<cell> _cells;
    }

Define constructor for the universe class. It takes the dimension in row, col and the content cells as collection.

public Universe(int DimRow, int DimCol, List<cell> Cells)
        {
            _dimRow = DimRow;
            _dimCol = DimCol;
            _cells = new List<cell>();
            _cells = Cells;            
        }

Define property Cells which are the contents of the universe:

public List<cell> Cells
        {
            get
            {
                Regenerate();                
                return _cells;
            }
            set
            {                
                _cells = value;
            }
        }

Each individual cell has neighbors. The rules of the game are defined by the state of the neighbors for each cell. So we calculate the neighbors and their states for each cell. We calculate the neighbors for each cell by analyzing their position in the Universe. There are eight rules to check – Left, Right, Top, Bottom, Right Diagonal Up, Left Diagonal Up, Right Diagonal Down, Left Diagonal Down.

If the cell is in the 1st row and 1st column – it would not have any neighbor on its left or top. Similarly for a cell in the extreme right bottom of the universe, it would not have any neighbor on its right and bottom, and so on.

private void SetNeighbors()
        {
            foreach (Cell item in _cells)
            {                
                // neighbor in same row - Left
                if (item.Col > 0)
                {                    
                    item.Neighbors.Add(new Cell() 
                    { 
                        Row = item.Row, 
                        Col = item.Col - 1, 
                        State=GetCellState(item.Row,item.Col-1)
                    });
                }
 
                // neighbor in same row - Right    
                if (item.Col < _dimCol - 1)
                {
                    item.Neighbors.Add(new Cell()
                    {
                        Row = item.Row,
                        Col = item.Col + 1,
                        State = GetCellState(item.Row, item.Col +1)
                    });    
                }
                    
                // neighbors in same col - Above
                if (item.Row > 0)
                {                    
                    item.Neighbors.Add(new Cell() 
                    { 
                        Row = item.Row - 1, 
                        Col = item.Col,
                        State = GetCellState(item.Row-1, item.Col)
                    });                    
                }
 
                // neighbors in same col - Below
                if (item.Row < _dimRow-1)
                {                    
                    item.Neighbors.Add(new Cell() 
                    { 
                        Row = item.Row +1, 
                        Col = item.Col,
                        State = GetCellState(item.Row +1, item.Col)
                    });                    
                }
 
                // neighbor diagonal - Left Above
                if (item.Row>0 && item.Col>0)
                {
                    item.Neighbors.Add(new Cell()
                    {
                        Row = item.Row - 1,
                        Col = item.Col - 1,
                        State = GetCellState(item.Row-1, item.Col-1)
                    });
                }
 
                // neighbor diagonal - Right above
                if (item.Row>0 && item.Col<_dimCol-1)
                {
                    item.Neighbors.Add(new Cell()
                    {
                        Row = item.Row - 1,
                        Col = item.Col + 1,
                        State = GetCellState(item.Row-1, item.Col+1)
                    });  
                }
 
                // neighbor diagonal - Left Below
                if (item.Row<_dimRow-1 && item.Col>0 )
                {
                    item.Neighbors.Add(new Cell()
                    {
                        Row = item.Row + 1,
                        Col = item.Col - 1,
                        State = GetCellState(item.Row+1, item.Col-1)
                    });
                }
 
                // neighbor diagonal - Right Below
                if (item.Row<_dimRow-1 && item.Col<_dimCol-1)
                {
                    item.Neighbors.Add(new Cell()
                    {
                        Row = item.Row + 1,
                        Col = item.Col + 1,
                        State = GetCellState(item.Row+1, item.Col+1)
                    });
                }            
            }
        }

GetCellState method calculates the state of each cell in the Universe:

private State GetCellState(int row, int col)
        {            
            Cell cell = _cells.Find((c) => 
		{ return (c.Row == row && c.Col == col); });            
            return cell.State;
        }

Once the neighbors are set, it's time we apply the rule engine for the game in the Regenerate() method. So for each cell:

  1. Calculate number of living neighbors:
    int livingNeighbors = 0;
                    foreach (Cell cell in item.Neighbors)
                    {
                        if (cell.State.GetStateType()==typeof(Alive))
                        {
                            livingNeighbors += 1;
                        }
                    }
  2. If cells are living – decide if they are going to live or die:
    if (item.State.GetStateType() == typeof(Alive))
                    {
                        // Living Cells Die
                        if (livingNeighbors < 2 || livingNeighbors > 3)
                        {
                            _newCells.Add(new Cell()
                            {
                                Row = item.Row,
                                Col = item.Col,
                                //CellState = State.Dead
                                State = new Dead()
                            });
                        }
                        // Living Cells Live
                        else
                            _newCells.Add(new Cell()
                            {
                                Row = item.Row,
                                Col = item.Col,
                                //CellState = State.Living
                                State = new Alive()
                            });
                    }
  3. Similarly if cells are dead – they come alive if the number of living neighbors =3.
    if (livingNeighbors == 3)
                        {
                            _newCells.Add(new Cell()
                            {
                                Row = item.Row,
                                Col = item.Col,
                                //CellState = State.Living
                                State = new Alive()
                            });
                        }
                        // dead cells continue to die
                        else
                        {                        
                            _newCells.Add(new Cell()
                            {
                                Row = item.Row,
                                Col = item.Col,
                                //CellState = State.Dead
                                State = new Dead()
                            });
                        }

Testing

Please refer to the Test harness Project for NUnitTesting. I have four test cases as explained below. For each test case, I have defined a Universe with input cells and then I have defined the expected Universe class after regeneration. I then compare the actual regeneration and expected regeneration.

X – Represents an Alive state
__ - Represents a Dead State

1.	Block Pattern
Input
X X
X X 
Output
X X
X X

2.	Bloat Pattern
Input 
X X -
X - X
- X -
Output 
X X -
X - X
- X -

3.	Blinker Pattern
Input
- X -
- X -
- X - 
Output 
- - -
X X X
- - -

4.       Toad Pattern
Input
- X X X
X X X -
- - X -
Output
X - - X
X - - X
- X - -

History

  • 19th April, 2011: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

anshudutta
Software Developer (Senior)
Australia Australia
I am a Senior Software Developer / Technical Consultant in a leading software company.

Comments and Discussions

 
GeneralI tried this PinmemberEdward Giles5-Nov-11 23:04 
General[My vote of 2] PinmemberIGood21-Apr-11 9:36 
GeneralRe: [My vote of 2] Pinmemberanshudutta21-Apr-11 18:00 
GeneralRe: [My vote of 2] PinmemberIGood22-Apr-11 12:01 
GeneralRe: [My vote of 2] PinmemberMember 740216624-Apr-11 7:50 
GeneralRe: [My vote of 2] PinmemberStephen Killingsworth Jr.19-Nov-13 8:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140827.1 | Last Updated 21 Apr 2011
Article Copyright 2011 by anshudutta
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid