12,815,986 members (39,870 online)
alternative version

Stats

16.1K views
6 bookmarked
Posted 21 Apr 2011

Solving Conway’s Game of Life using State Pattern

, 21 Apr 2011 CPOL
 Rate this:
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

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 `State`s – `Alive`, `Dead`.

It has a `context `class which deals with the decision of evaluating and handling the `State`s.

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 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)
{
{
Row = item.Row,
Col = item.Col - 1,
State=GetCellState(item.Row,item.Col-1)
});
}

// neighbor in same row - Right
if (item.Col < _dimCol - 1)
{
{
Row = item.Row,
Col = item.Col + 1,
State = GetCellState(item.Row, item.Col +1)
});
}

// neighbors in same col - Above
if (item.Row > 0)
{
{
Row = item.Row - 1,
Col = item.Col,
State = GetCellState(item.Row-1, item.Col)
});
}

// neighbors in same col - Below
if (item.Row < _dimRow-1)
{
{
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)
{
{
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)
{
{
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 )
{
{
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)
{
{
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)
{
{
Row = item.Row,
Col = item.Col,
});
}
// Living Cells Live
else
{
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)
{
{
Row = item.Row,
Col = item.Col,
//CellState = State.Living
State = new Alive()
});
}
// dead cells continue to die
else
{
{
Row = item.Row,
Col = item.Col,
});
}```

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 -

Input
- X -
- X -
- X -
Output
- - -
X X X
- - -

Input
- X X X
X X X -
- - X -
Output
X - - X
X - - X
- X - -```

History

• 19th April, 2011: Initial version

Share

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

You may also be interested in...

 Pro Pro

 First Prev Next
 Test Case Error Tony Audi28-Dec-16 11:03 Tony Audi 28-Dec-16 11:03
 I tried this Edward Giles6-Nov-11 0:04 Edward Giles 6-Nov-11 0:04
 [My vote of 2] IGood21-Apr-11 10:36 IGood 21-Apr-11 10:36
 Re: [My vote of 2] anshudutta21-Apr-11 19:00 anshudutta 21-Apr-11 19:00
 Re: [My vote of 2] IGood22-Apr-11 13:01 IGood 22-Apr-11 13:01
 Re: [My vote of 2] Member 740216624-Apr-11 8:50 Member 7402166 24-Apr-11 8:50
 Re: [My vote of 2] Stephen Killingsworth Jr.19-Nov-13 9:15 Stephen Killingsworth Jr. 19-Nov-13 9:15
 Last Visit: 31-Dec-99 19:00     Last Update: 23-Mar-17 10:38 Refresh 1