12,823,984 members (46,290 online)
alternative version

#### Stats

61K views
23 bookmarked
Posted 17 Feb 2012

# Game of life: Code solution in C#

, 7 Mar 2012 CPOL
 Rate this:
An Object Oriented solution to Conway's Game of life problem in C#

## 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:

1. Any live cell with fewer than two live neighbours 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 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.

##### 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.

1. 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.
2. 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
{
// List of Rows in Grid
public List<Row> GridObj { set; get; }

// other code ...

}
```

Each row is represented as follows:

```public class Row
{
//List of Cells
public List<Cell> Cells { get; set; }

// other code ...

}
```

Finally each Cell will look like this:

```    public class Cell
{
//A Cell can be alive or dead based on this property - true = alive and false = dead
public Boolean IsAlive { get; set; }

// other code ...

}  ```
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.

1. Task for updating existing cells in Output Grid.

## 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.
```// 1. Task for changing all existing Cell Status
// 2. Task for expanding output gird if respective rule satisfies
```
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.
```    // Dictionary to hold list of reachable cells co-ordinates for specified cell type
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 Center cell

Based on the location of Coordinates of cell, it can be broadly divided into below categories.
```   /// <summary>
/// Cell types are unique types of cell in grid of any size
/// Every cell type has distinct reachable djacent cells which can be traversed
/// </summary>
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.

```/// <summary>
/// Display the grid
/// </summary>
public static void Display(Grid grid)
/// <summary>
/// Deep copy Copy Source grid to target grid
/// </summary>
/// <param name="sourceGrid"></param>
/// <param name="targetGrid"></param>
public static void Copy(Grid sourceGrid, Grid targetGrid)
/// <summary>
/// Set target grid schema similar to source grid schema
/// </summary>
/// <param name="sourceGrid"></param>
/// <param name="targetGrid"></param>
private static void MatchSchema(Grid sourceGrid, Grid targetGrid)
/// <summary>
/// Assign Source grid cell values to target grid
/// </summary>
/// <param name="sourceGrid"></param>
/// <param name="targetGrid"></param>
private static void AssignCellValues(Grid sourceGrid, Grid targetGrid)
```

## History

This is the first version of the article. Reader comments are welcome.

## Share

 Technical Lead 3 Pillar Global India
Working as Technical lead in 3 Pillar Global. Having experience in ASP.NET, C#, Web API, WebServices, SQL Server and other Microsoft technologies.

## You may also be interested in...

 Pro Pro

 First Prev Next
 Windows Form Member 1208625625-Oct-15 14:23 Member 12086256 25-Oct-15 14:23
 improvements fredatcodeproject17-Jun-14 1:17 fredatcodeproject 17-Jun-14 1:17
 My vote of 3 muhammed riyaaz3-Jul-13 21:10 muhammed riyaaz 3-Jul-13 21:10
 Zombie apocalypse game jacksonfive23-Oct-12 6:47 jacksonfive 23-Oct-12 6:47
 To add my name... sonisachin30-May-12 0:33 sonisachin 30-May-12 0:33
 My vote of 5 MehdiNaseri7-Mar-12 17:51 MehdiNaseri 7-Mar-12 17:51
 Formatting Collin Jasnoch17-Feb-12 10:39 Collin Jasnoch 17-Feb-12 10:39
 Last Visit: 31-Dec-99 19:00     Last Update: 27-Mar-17 16:11 Refresh 1