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

Game of life: Code solution in C#

, 7 Mar 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
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.


Block pattern

Input A
Output A
329881/Square1.png
329881/Square1.png

Boat pattern
Input B
Output B
329881/Input_B.png
329881/Input_B.png

Blinker pattern
Input C
Output C
329881/Input_C.png329881/Output_C.png

Toad pattern

Input D
Output D
329881/Input_D.png329881/Outout_D.png


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:

329881/Generation_Overview.png

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.

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:

  1. Task for updating existing cells in Output Grid.
  2. Task for adding adding row or column in the Output Grid.

329881/Parallel_Task_1_-_Copy.png

329881/Parallel_Task_2.png

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.
    // 1. Task for changing all existing Cell Status        
    private Task EvaluateCellTask;
    // 2. Task for expanding output gird if respective rule satisfies
    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.
        // 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 Top left cell
Reachable cells from Top Side cell
Reachable cells from Center cell
329881/Reachable_Cell_1.png329881/Reachable_Cell_2.png329881/Reachable_Cell_3.png

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.

329881/Cell_Enum_Types.png


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)
   

References

History  

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

License

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

Share

About the Author

Kailash Shastri
Technical Lead Imfinity Pte Ltd
India India
Working as Technical lead in Imfinity Pte Ltd. Having experience in ASP.NET, C#, WCF, WebServices, SQL Server and other microsoft technologies.

Comments and Discussions

 
Questionimprovements Pinmemberfredatcodeproject17-Jun-14 1:17 
GeneralMy vote of 3 Pinmembermuhammed riyaaz3-Jul-13 21:10 
QuestionZombie apocalypse game Pinmemberjacksonfive23-Oct-12 6:47 
QuestionTo add my name... Pinmembersonisachin30-May-12 0:33 
GeneralMy vote of 5 PinmemberMehdiNaseri7-Mar-12 17:51 
QuestionFormatting PinmemberCollin Jasnoch17-Feb-12 10:39 

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 | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 7 Mar 2012
Article Copyright 2012 by Kailash Shastri
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid