May 7 2011

John Conway's Game of Life part 1 of N

Category: MobileJoel Ivory Johnson @ 14:59

The Game of Life is a refinement of an idea from John von Newman in the 1940's. The refinement was done by John Conway and appeared in Scientific America in October 1970. I'll skip over the details of why such a program is of interest. But the program produces some interesting patterns.

The typical version of the game is composed of a grid of cells where some number of cells are initially marked as having life. The grid of cells is evaluated and cells get marked as alive or dead based on a small set of rules based on it's neighbors. Two cells are neighbors with each other if they touch diagonally or side-by-side.

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The above algorithm enough and the program is easy to implement. The challenge is more in creating a decent user interface for the program. I decided to make this program myself. The first step in making the program was to implement the algorithm. I wanted to make sure the algorithm worked so I created a simple XNA program that would allow me to see the algorithm work. It's non-interactive so you can only see the program run but not impact the outcome.

Theres a small amount of data that needs to be tracked for each cell. I need to know if a cell is alive and whether or not it should be alive during the next cycle. The cell will also need to interact with other cells in the community. Some time in the future I plan to allow the cells to express something about the parent from which it came. Though I won't be doing that for this first version.

public class Cell
{
     public CellCommunity  Community   { get; set; }
     public bool           IsAlive     { get; set; }
     public bool           WillSurvive { get; set; }
     public Gene           GeneList { get; set; }
}

The community of cells themselves will be saved in a two dimensional array. The cell community class has two methods that will do the work of calculating whether or not a cell should be alive the next cycle and another for applying the results of those calculations.

public void EvaluateNewGeneration()
{
    ++GenerationCount;

    for (var cx = 0; cx < CellGrid.GetUpperBound(0); ++cx)
    {
        for (var cy = 0; cy < CellGrid.GetUpperBound(1); ++cy)
        {
            var neighborsneighborList = GetNeighborList(cx, cy);
            var len = neighborsneighborList.Length;

            if ((IsAlive(cx, cy)))
            {
                if ((neighborsneighborList.Length > MAX_NEIGHBOR_COUNT) || (neighborsneighborList.Length < MIN_NEIGHBOR_COUNT))
                    KillCell(cx, cy);
                else
                    KeepCellAlive(cx, cy);
            }
            else
            {
                if ((neighborsneighborList.Length ==3))
                {
                    KeepCellAlive(cx, cy);
                }
            }
        }
    }
}

public void ApplySurvival()
{
    for (var cx = 0; cx < CellGrid.GetUpperBound(0); ++cx)
    {
        for (var cy = 0; cy < CellGrid.GetUpperBound(1); ++cy)
        {
            var cell = CellGrid[cx, cy];
            if (cell != null)
            {
                cell.IsAlive = cell.WillSurvive;
            }
        }
    }
}

I decided to make the UI in XNA. I have an idea on how to visualize a cell changing state and I can more easily implement it using a 3D API. Since the "world" of the Game of Life is in a grid I'm going to represent the state of a cell with a square that is either black (if the cell is not alive) or some other color (if the cell is alive). I'm drawing the squares by rendering vertices instead of writing sprites. This give me greater liberty in changing the color or shape of a cell. The following will draw one of the squares.

const int _squareWidth = 5;
const int _squareHeight = 5;
private const int _offsetX = -_squareWidth*30;
private const int _offsetY = -_squareHeight*18;

void DrawSquare(int x, int y, Color c)
{
    _vertices[0].Color = c;
    _vertices[1].Color = c;
    _vertices[2].Color = c;
    _vertices[3].Color = c;

    _vertices[0].Position.X = _offsetX + _squareWidth * x + _squareWidth;
    _vertices[0].Position.Y = _offsetY + _squareHeight * y;

    _vertices[1].Position.X = _offsetX + _squareWidth*x;
    _vertices[1].Position.Y = _offsetY + _squareHeight*y;

    _vertices[2].Position.X = _offsetX + _squareWidth * x + _squareWidth;
    _vertices[2].Position.Y = _offsetY + _squareHeight * y + _squareHeight;

    _vertices[3].Position.X = _offsetX + _squareWidth * x;
    _vertices[3].Position.Y = _offsetY + _squareHeight * y +_squareHeight;

    graphics.GraphicsDevice.DrawUserPrimitives(PrimitiveType.TriangleStrip, _vertices, 0, _vertices.Length-2);     
}

With the ability to draw the square completed it's easy to iterate through the collection of cells and render them to the screen according to whether or not they are alive.

protected override void Draw(GameTime gameTime)
{
    GraphicsDevice.Clear(Color.CornflowerBlue);

    var effect = new BasicEffect(GraphicsDevice);
    effect.World = _world;
    effect.Projection = _projection;
    effect.View = _view;
    effect.VertexColorEnabled = true;
    effect.TextureEnabled = false;
    effect.LightingEnabled = false;

    foreach(var effectPass in effect.CurrentTechnique.Passes)
    {
        effectPass.Apply();
        for (int cx = 0; cx < 60;++cx )
        {
            for(int cy=0;cy<36;++cy)
            {
                Color c = _community.IsAlive(cx, cy) ? Color.Red : Color.Black;
                DrawSquare(cx,cy,c);
            }
        }                    
    }
    base.Draw(gameTime);
}

I manually populated the grid and let it run. I'm happy to say it seems to be working. Now onto designing and making the user interface.

Screen Shot

Tags: ,