Introduction
Let us start with an introduction to
the GAME OF LIFE problem. As per wiki “The Game of Life, also known simply as
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.
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:
Any live cell with fewer than two live neighbours dies,
as if by loneliness.
Any live cell with more than three live neighbours
dies, as if by overcrowding.
Any live cell with two or three live neighbours lives,
unchanged, to the next generation.
Any dead cell with exactly three live neighbours comes
to life.
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.
Problem
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.
Block pattern
Input A | Output A |
|
|
Boat pattern
Input B | Output B |
|
|
Blinker pattern
Input C | Output C |
 |  |
Toad pattern
Input D | Output D |
 |  |
It is important to note that in Output D, the two new rows have been due to Rule #4 i.e. Any dead cell with exactly three live neighbours comes
to life. Thus, the next state will include two new auto grown rows.
Background
This looks interesting and it seems that implementing the logic in a structured language will not be very difficult. However, there are a couple of catch here.
- The other catch is the need of implementation in Object oriented fashion
which is a bit tricky. It means design should conform to object
oriented principles.
- The first generation is created by applying the above
rules simultaneously to every cell in the seed. I think we may need some sort of Threading implementation here to provide simultaneous updates on all cells.
To be able to implement such solution in object oriented manner is quite a challenging task. However, we will come up with a design which obeys object oriented principles.
Handling Grid Generations
The first idea which comes into my mind is to keep separate Grid in initial generation and next Generation. In the beginning, we will have two grids say Input Grid and Output Grid. Input Grid is the initial state of game off life to start with. Output grid will contain the next generation of Input Grid. We need to apply rules for each cell in Input Grid and get the Cell's next generation in Output Grid. In case, where Row or Column growth is required then these will be added to Output Grid.
Please note that the state of Input grid will not be updated to get the next generation, so there is no run-time consideration of cell state changes. In other words, consider Input Grid as grid with freezed cells and Output Grid will change until all cells in Input Grid is evaluated. Please see figure below:
Once a generation is complete, we will do a swapping of Output Grid to Input Grid and the process will continue.
Considerations for two dimensional matrix
We need to implement a two dimensional matrix having every cell containing one of two boolean values; live or dead. This two dimensional structure should be able to grow in either side e.g. new row could be added to top as well as bottom and new column can be added before first column and last column. It gives a sense of a list as we need not refer a cell from its index but need to enumerate from first item till the last element.
From the above discussion, it is clear that we are moving into the utilizing list collection classes in C#. We have a custom class for cell having a boolean property as Isalive. This will make the implementation more extensible.
Further, to hold a list of cell a custom object called Row which contains a list of cells. Therefore, our grid will contain a list of such rows, which in turn contains a list of Columns.
Let us have a look at how will our Grid look like:
public class Grid
{
public List<Row> GridObj { set; get; }
}
Each row is represented as follows:
public class Row
{
public List<Cell> Cells { get; set; }
} Finally each Cell will look like this:
public class Cell
{
public Boolean IsAlive { get; set; }
} Also, if any other behavior is required to be added at the cell level then it cal be easily done in the Cell class.
Considerations for simultaneous update to all cells
This is very important point on simultaneously updating all cells in the Game of Life Grid. At first sight this seems trivial. Let us analyze the below questions before moving on:
How can we update all cells at the same time?
Is there any update to a cell dependent on other cells updates?
Answer to the Question 1 is rather simple. Here it does not require CPU to execute cell update operation at the same time, but it requires that all tasks are done in parallel in different threads as cell's next generation is not dependent upon next generation of other cells. Here we need to implement threading to apply simultaneous update to all cells.
The answer to the second question is a bit tricky. As discussed in the last sentence, Cell's next generation is not dependent upon next generation of other cells. This is true, we always need to read Input Grid (which is freezed) and stuff the result to Output Grid cell. So Output Grid cell state is independent of other cell state in Output Grid. However, in some situations the OutputGrid can grow; a new row or column can be added to Output Grid. This will cause issues in parallel operations. How? Think about a situation where a Thread1 is updating the first row of grid. However, other thread Thread2 has added a new row in output grid before Thread1 has completed the operation. Now, when Thread1 will now update cell in the first row, the result will be incorrect as the first row (before Thread2 had executed) has now become second row, but the changes have been applied to the first row. Thus, there will be two kind of tasks required to be done on Output Grid:
- Task for updating existing cells in Output Grid.
- Task for adding adding row or column in the Output Grid.
I will explain about these task in detail when discussing about code.
Using the code
Here
is the list of classes used to implement Game of Life:
Game:
This is the primary class of solution which
will be used as main interface for the game.
User of this class needs to provide number of rows and column at the
initial level.
public Game(int rows, int columns)
{
if (rows <= 0 || columns <= 0) throw new ArgumentOutOfRangeException("Row
and Column size must be greater than zero");
_inputGrid = new Grid(rows, columns);
_outputGrid = new Grid(rows, columns);
} Optionally, user can set maximum number of
generations of the Game of life.
objLifeGame.MaxGenerations = maxGenerations;
Further, user needs to set some cells inside
the grid to live by calling TogglegridCell method.
Game objLifeGame = new Game(3, 3);
objLifeGame.ToggleGridCell(0, 1);
objLifeGame.ToggleGridCell(1, 1); It also consist two Tasks
which are executed in parallel to update grid simultaneously. Notice that we are using two task which are executed in parallel.
private Task EvaluateCellTask;
private Task EvaluateGridGrowthTask;
Grid:
This class is a dynamic two dimensional data structure which holds matrix of cells.
It consists of generic list of rows which in turn contains list of cells.
Row:
This class is a generic list of cells. User can add a cell at the end of cell list or
insert a cell at specified index.
Cells:
This class holds the actual representation of cell data in a Boolean property IsAlive
which is true for live and false for dead cells.
Coordinates: This is a struct to hold x and y co-ordinates of the grid.
public struct CoOrdinates
{
public int X;
public int Y;
public CoOrdinates(int x, int y)
{
X = x;
Y = y;
}
}
Rule:
This class separates the algorithm of transitioning grid to the next
generation. It exposes ChangeCellsState and ChangeGridState methods to apply
changes on grid. It has following static methods.
public static void ChangeCellsState(Grid inputGrid, Grid outputGrid, CoOrdinates coOrdinates)
private static int CountAliveNeighbours(Grid grid, CoOrdinates coOrdinates)
private static int IsAliveNeighbour(Grid grid, CoOrdinates baseCoOrdinates, CoOrdinates offSetCoOrdinates)
private static Boolean IsAliveInNextState(Cell cell, int liveNeighbourCount)
public static void ChangeGridState(Grid inputGrid, Grid outputGrid)
private static void CheckColumnGrowth(Grid inputGrid, Grid outputGrid, int colId)
private static void CheckRowGrowth(Grid inputGrid, Grid outputGrid, int rowId)
ReachableCell:
This is a specialized class to make traversal of adjacent cells from a
specified cell easier. It keeps reachable adjacent cell locations for unique
cell types on any size of grid. Cell types are distinct cell locations which
share similar adjacent cells.
public static Dictionary<CellTypeEnum, List<CoOrdinates>> ReachableCellDictionary;
Every cell in the grid will have a unique set of reachable cells adjacent to it. For example, Top left corner cell having index (0,0) can have three reachable adjacent cells (0,1), (1,0) and (1,1). Similarly, any top side cell having index (0,1) can have reachable 5 adjacent cells (0,2), (1,2), (1,1), (1,0) and (0,0). Few samples below:
Reachable cells from Top left cell | Reachable cells from Top Side cell | Reachable cells from Center cell |
 |  |  |
Based on the location of Coordinates of cell, it can be broadly divided into below categories.
public enum CellTypeEnum
{
TopLeftCorner,
TopRightCorner,
BottomLeftCorner,
BottomRightCorner,
TopSide,
BottomSide,
LeftSide,
RightSide,
Center,
OuterTopSide,
OuterRightSide,
OuterBottomSide,
OuterLeftSide,
None
}
The below figure shows all cell types available in 4x4 Grid. Cell type for any other grid can be used in similar manner.
GridHelper:
This is a static helper class to perform operations like displaying the grid
and Copy source grid to destination.
public static void Display(Grid grid)
public static void Copy(Grid sourceGrid, Grid targetGrid)
private static void MatchSchema(Grid sourceGrid, Grid targetGrid)
private static void AssignCellValues(Grid sourceGrid, Grid targetGrid)
References
History
This is the first version of the article. Reader comments are welcome.
