Coding For Fun: Conway’s Life

Windows Phone From Scratch #45

I was feeling a bit restless yesterday, so I decided to see if I couldn’t get a first approximation of Conway’s Life cellular automaton up and running on Windows Phone.  I gave myself 1 hour to do it.  It came out okay, and today I submitted it to App Hub (I’ll let you know if it gets published) as a free app.

The premise of Conway’s “game” is to create a world in a grid. You seed the grid either at particular locations, or as I did, randomly.  You then proceed in generations.

Each generation you look at the existing cells which are deemed to be alive (red) or dead (black).  Alive cells that have fewer than 2 neighbors die of loneliness and are dead in the next generation.   Similarly, alive cells with 4 or more of the possible 8 neighbors, die of overcrowding.  Live cells with 2 or 3 neighbors live on to the next generation. Finally, dead cells with exactly three neighbors come to life in the next generation.

What makes Conway’s Life exceedingly interesting is that patterns emerge in the seeming random chaos (and for those of us who miss our PDP-8, it is endless fun to watch the red lights flash on and off!). 

To build this, I began by creating a grid of 30 rows and 15 columns, and experimenting with placing rectangles into each cell.  What quickly became clear was that if I did this stupidly, I would use a tremendous amount of resources and bring the phone to its knees. 

A few performance enhancements along the way:

1. Each generation: wipe out all the previous generation’s rectangles; otherwise they just pile up on one another, wasting memory

2. No need to draw the black (dead) cells, the background takes care of that

3. Be careful not to keep creating brushes; one brush can be shared among all the rectangles.

I opted to have two 2-dimensional arrays, which I named world1 and world2.  World1 at any given moment had the current world, world2 had the emerging world. 

const int ROWS = 32;
const int COLS = 17;
private bool[,]world1 = new bool[ ROWS, COLS ];
private bool[,]world2 = new bool[ ROWS, COLS ];
private long generation = 0;

The first step was to initialize the world. An empty world stays empty  I tinkered for a bit on how to randomly scatter live cells, and what density of live cells to use. I ended up deciding that a density of 1/3 live to 2/3 dead cells, randomly scattered, seemed to work pretty well,

 private void InitWorld( )
 {
    Random rand = new Random( );
    for ( int i = 0; i < ROWS; i++ )
    {
       for ( int j = 0; j < COLS; j++ )
       {
          if ( rand.Next( ) % 3 == 0 )
             world2[ i, j ] = true;
          else
             world2[ i, j ] = false;
       }
    }
 }

I needed a timer, and much preferred a timer that would work on the UI thread so that I didn’t have to marshal across threads.   Again the question was how fast the clock should run (how much time should there be, between generations).  While I intend to make this user-adjustable in some future version, for now I set it to ten milliseconds,

 private DispatcherTimer timer = 
          new DispatcherTimer( );

 private void SetTimer( )
 {
    timer.Interval = new TimeSpan( 0, 0, 0, 0, 10 );
    timer.Tick += new EventHandler( timer_Tick );
    timer.Start( );
 }

Each tick of the timer is a generation.  I begin each new generation by copying the current world (world2) to the “previous world” (world1) and then calling SetNewWorld to compute the next generation and then DrawNewWorld() to draw it.  I also increment my generation counter,

private void timer_Tick( 
     object sender, EventArgs e )
{
   world1 = world2;
   SetNewWorld( );
   DrawNewWorld( );
   generation++;
}

SetNewWorld looks at all eight neighbors to determine how many of them are alive, and then implements the rule about who lives into the next generation,

 private void SetNewWorld( )
 {
    for ( int i = 0; i < ROWS; i++ )
    {
       for ( int j = 0; j < COLS; j++ )
       {
          int totalAlive = 0;
          if ( Alive( i - 1, j ) ) // above
             totalAlive++;
          if ( Alive( i, j - 1 ) )  // left
             totalAlive++;
          if ( Alive( i, j + 1 ) ) // right
             totalAlive++;
          if ( Alive( i + 1, j ) ) // below
             totalAlive++;
          if ( Alive( i - 1, j - 1 ) ) // above left
             totalAlive++;
          if ( Alive( i - 1, j + 1 ) ) // above right
             totalAlive++;
          if ( Alive( i + 1, j - 1 ) ) // below left
             totalAlive++;
          if ( Alive( i + 1, j + 1 ) ) // below right
             totalAlive++;

          if ( totalAlive < 2 || 
             totalAlive > 3 || 
             ( totalAlive == 2 && 
                  world1[ i, j ] == false ) )
             world2[ i, j ] = false;
          else
             world2[ i, j ] = true;
       }
    }
 }

This method depends on a helper method, Alive, which checks to make sure the cell is “in bounds” and then returns the current status of that cell,

 private bool Alive( int i, int j )
 {
    if ( i < 0 || 
         j < 0 || 
         i > ROWS - 1 || 
         j > COLS - 1 )
       return false;
    return world1[ i, j ];
 }

Finally, DrawNewWorld updates the generation in the title and then clears the content panel of all existing rectangles. We then iterate through each cell populating the alive ones with new rectangles and adding the rectangles to the grid,

 private void DrawNewWorld( )
 {
    ApplicationTitle.Text = "Life " + generation.ToString( );

    ContentPanel.Children.Clear( );

    var filler = new SolidColorBrush( Colors.Red );

    for ( int i = 0; i < ROWS; i++ )
    {
       for ( int j = 0; j < COLS; j++ )
       {
          if ( world2[ i, j ] == false )
             continue;
          Rectangle rect = new Rectangle( );
          rect.Height = 10;
          rect.Width = 10;
          Grid.SetRow( rect, i );
          Grid.SetColumn( rect, j );
          rect.Fill = filler;
          ContentPanel.Children.Add( rect );
       }
    }
 }

Caveat: This is very much a first generation program written on a lark, and has virtually no redeeming social value.  To get a look at what a thorough Life simulation looks like, take a look at my buddy’s web site – on the fifth row, three from the left you’ll find Life Playground. Warning,  once you visit his site you may be stuck there for many days exploring his games and puzzles.