In a
previous article, we created a rules library for Conway's Game of Life (
code download). This was just the rules for whether a cell lives or dies based on its neighbors. But we did not implement any type of UI. That's what we'll do here.
The Rules
As a reminder, our rules engine consisted of a single method:
This takes the current state of a cell and the number of live neighbors that it has. But this doesn't tell us anything about the grid of cells or the state of that grid. For that, we'll need to create a new object.
The Grid
So, I added a new class to the Conway.Library project called "LifeGrid". Here are the fields and constructor:
I made some tough decisions here. I don't like the idea of dealing with a multi-dimensional array (If you know anything about me, you know that I love generic lists). To make things easier to start out with, I hard-coded the dimensions of the grid to 5 x 5.
The reason that I have a "current state" and "next state" is to make it easier to run the rules. When we get the rules for a single cell, it depends on the current state of all of it's neighbors (8 neighbors in our case). That means we can't change the state of any of our cells until after we've processed the rules for all of the cells. We could do this by taking a snapshot, but I decided to create "current" and "next". You can think of this as similar to the way that we used to double-buffer graphic animations to make them faster to load.
After instantiating both of our states, I initialize the current state to all "Dead". (An easier way might have been to flip the enum so that "Dead" comes first (i.e. position 0). That way it would automatically be in that state when it's instantiated. I expect to do a lot of refactoring of this code, so I might end up doing that later.)
Running the Rules
With the grid in place, we need to run the rules on all of the cells. Here's our method for UpdateState:
For this, we loop through both dimentions of our array. This is one of the reasons I don't like dealing with them. The nested "for" loops rub me the wrong way. Inside the loop, we get the number of live neighbors for the current cell (we'll look at this method in just a bit). Once we have that, we can call our GetNewState method that we created before. Once we have that result, we can assign it to the same position in the "next state" grid.
After completing the loops, we assign the "next state" to the CurrentState property. This replaces the old values with the new values. Then we create a new instance for the nextState variable.
Getting the number of live neighbors for each cell is an interesting problem.
I'll admit that I haven't looked up other implementations of Conway's Game of Life for this coding session. That's because I wanted to try to figure things out and then optimize as needed.
There are a lot of nasty conditionals here. The method takes the X-Y coordinates of the current cell. Then it has nested "for" loops to go through the cells to the left, right, top, bottom, and diagonals. It does this by subtracting 1 and adding 1 to the current position.
But we have a problem. These "for" loops will hit the current cell. We want to skip this, which is why we check for "i == 0 && j == 0".
The next trick is that we need to make sure that the neighbor cell is still on the grid. So we check to make sure that the X-Y values are greater than 0 and less than 5 (our current grid size).
Once we've validated that we're looking at a cell that is a neighbor of the current cell and not off the grid, we check to see if it is alive. If so, we increment our liveNeighbors count. Then we just return the total when we're done.
This completes the implementation of our grid. We'll make a few adjustments to it so that we can have an arbitrary size, but this is enough for us to hook this up to a UI.
Creating a Console UI
We're going to start out pretty simple: we're just going to hook up a console application to our grid. This will output the cell state as dots or Os. To create this, I just added a new project to our solution called "Conway.ConsoleUI". As you might imagine, this is a console application. Then we just need to add a reference to our Conway.Library project.
Here's our console application:
For this, we create an instance of our LifeGrid class. Then we set some cells to a live state (since they default to all dead).
After that, we show the grid (and we'll see this method in just a bit). Then we have a while loop hooked up so that we can update the grid every time we press the Enter key.
Here's how we show the grid:
I was able to get away with not using nested "for" loops. This is because we don't care about the position of the cells, we just need to print them out. We're going to output a character for each cell, and then we just need to put in a line break when we reach the end of the row.
I did brute force this. The "x" variable keeps track of our current column. When we reach the end, I reset "x" and then output a line break.
Visual Verification
Up to this point, we really don't know if anything will work. Let's run the application to see what we get:
And when we press "Enter":
And if we keep pressing "Enter", we'll see these states alternate. That's good. This is a "Blinker" (
Conway's Patterns).
Arbitrary Grid Size
Our next step will be to allow for an arbitrary grid size. This isn't all that difficult. For our LifeGrid class, we just need to add some field to hold the state. Then we update anywhere we have a "5" to the appropriate field.
Here are the basics:
The constructor now takes parameters for the height and width. These values are used to initialize the grid.
And these values are used in the UpdateState method as well:
So, not a whole lot of work.
The console application takes a little more work. First, we update the Main method to pass in the grid size (we'll stick with 5x5 for now):
And then we need to update our ShowGrid method:
This is little more interesting because we need to know the length of the row (to put in our line break). Instead of using "5", we check the array. We get the upper bound of the array and add 1. This is because our 5x5 grid would have an upper bound of "4", and we want to have the same row length value that we had before.
When we run the application, we see the same output:
So let's make a bigger grid.
A Bigger Grid
Since we have an arbitrary grid size, we can make it bigger by just changing our Main method:
And here's the output:
It looks like we have a problem. Our grid is going the wrong way. It turns out that there's a problem with our "ShowGrid" method. Here's the fix:
Before, we were checking the upper bound of dimension "0" (which happens to be our height). Instead, we should be checking the upper bound of dimension "1" (the width). We didn't run into this problem earlier because we were using a square grid -- both dimensions were the same.
With this update, we get the output we expect:
Adding Randomization
Making a bigger grid isn't really all that interesting. If we have to manually set the initial state, it could get pretty tedious. What we'll do instead is create a randomization method that we can run on our grid.
To make this easy to call, I added this to the LifeGrid class:
This loops through our grid and sets Alive/Dead values based on an random number.
Here's our updated Main method:
We just call "Randomize" after we create our grid. And here's the output:
And here's Generation 2:
And Generation 5:
And Generation 15:
Eventually this settles down into one of the static states: items that don't move or patterns that repeat.
Output Optimization
Let's try this with a larger value. Let's try 25 x 65. Here's the output after several generations:
The output is interesting, but there's a problem. This is slow. For small grids (like our 5 x 5), the display was instant. When we press the Enter key, there's no delay when the new grid shows up.
But on the larger grid, there's a definite re-draw that is apparent. And this ruins the illusion of watching Conway's Game of Life. The fun part is to watch generations go by quickly and seeing the patterns evolve. When the screen redraws from top to bottom, there's a break in that flow.
But we can fix this by changing the way that we're displaying our grid. As a reminder, here's our current ShowGrid method:
This calls "Console.Write" a lot -- once for each character. For a 5 x 5, that's only 30 times (including the new lines). But for a 25 x 65 grid, that's 1,650 calls.
So we'll minimize the number of times that we call "Console.Write". In fact, we'll only call it once:
All we've done is add a StringBuilder. Instead of directly writing to the console, we add the characters to the StringBuilder. Then at the very end, we call Console.Write one time.
This makes our display much faster. When pressing the Enter key quickly, there's no perceptible redraw (at least on my i7 laptop). If we hold the Enter key down, then there is some flicker, but this is definitely acceptable for what we have.
More to Add
Now we have a working application that displays Conway's Game of Life in action. But we're not done yet.
Back when I created the original rule method (GetNewState), I was thinking that this problem (recalculating all of the states) would be a good candidate for parallelization. And that's why I wrote the method the way that I did:
I created this as a static method: that means that we're not allowed to interact with any instance objects that are part of the class. The result is that we don't modify any shared state in this method (good). Next, since CellState (the type of our return value) is a value type, I don't have to worry about accidentally modifying state of the parameters. We will always get a new copy of the value (even if we don't change it in the method).
This means that if we run this method on different threads with different parameters, we don't have to worry about them interacting with each other.
But to take advantage of this, we'll need to make some changes to how we are updating the state in our LifeGrid class. We'll explore this in a future article.
In addition, I'd like to support some different UIs (like a WPF or Windows Phone application) that we could make a bit prettier.
Wrap Up
In implementing the UI for Conway's Game of Life, we had to take a look at how we are storing the grid data, how we update it, and how we display it on the screen. As mentioned, I'm not a big fan of having the nested "for" loops in so many methods, but we may be able to take care of that as we look at things further.
It's always good to practice our craft. Sometimes that means taking a well-known problem and implementing our own solutions (even when there are lots of implementations already). This lets us focus on things that we care about (such as parallelization) and also work our way out of problems that we might create for ourselves.
Practice is how we get better.
Happy Coding!
