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:
- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors’ lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by overcrowding.
- 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
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.
- Identify the classes:
Universe – Two dimension universe with cells as its content 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. Abstract State – This is the abstract class for our State. It contains an abstract method GetType which returns the type for each State. - Concrete States –
Alive and Dead classes
- 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. - 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:
State – Representing cell state Alive or Dead Neighbors – Neighbors of the cell Row – The row position of the cell in the universe 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>();
}
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)
{
if (item.Col > 0)
{
item.Neighbors.Add(new Cell()
{
Row = item.Row,
Col = item.Col - 1,
State=GetCellState(item.Row,item.Col-1)
});
}
if (item.Col < _dimCol - 1)
{
item.Neighbors.Add(new Cell()
{
Row = item.Row,
Col = item.Col + 1,
State = GetCellState(item.Row, item.Col +1)
});
}
if (item.Row > 0)
{
item.Neighbors.Add(new Cell()
{
Row = item.Row - 1,
Col = item.Col,
State = GetCellState(item.Row-1, item.Col)
});
}
if (item.Row < _dimRow-1)
{
item.Neighbors.Add(new Cell()
{
Row = item.Row +1,
Col = item.Col,
State = GetCellState(item.Row +1, item.Col)
});
}
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)
});
}
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)
});
}
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)
});
}
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:
- Calculate number of living neighbors:
int livingNeighbors = 0;
foreach (Cell cell in item.Neighbors)
{
if (cell.State.GetStateType()==typeof(Alive))
{
livingNeighbors += 1;
}
}
- If cells are living – decide if they are going to live or die:
if (item.State.GetStateType() == typeof(Alive))
{
if (livingNeighbors < 2 || livingNeighbors > 3)
{
_newCells.Add(new Cell()
{
Row = item.Row,
Col = item.Col,
State = new Dead()
});
}
else
_newCells.Add(new Cell()
{
Row = item.Row,
Col = item.Col,
State = new Alive()
});
}
- 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,
State = new Alive()
});
}
else
{
_newCells.Add(new Cell()
{
Row = item.Row,
Col = item.Col,
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
