Sunday, November 20, 2011

DDTe4 Hours 1 to 6 - The Basics of Life

When my mother went to the hospital and discovered that she had cancer, I spent some time researching the subject. Perhaps not as much time as I would have normally spent when researching a topic that strikes my interest, but enough to discover what a truly evil disease it is. Essentially, cancer is when a cell not only decides it does not want to die (I can’t blame it for that), but then starts reproducing replacing otherwise health cells. Thinking of the reproduction of cells got me thinking of Conway’s Game of Life. This is a zero player game as the game essentially follows a number of simple rules. The fun comes from setting up the world and watching it evolve.

There are a lot of features that I would like my implementation of life to support, and will implement as many features as I can within the 16-24 hours of development time allocated to this project, but the first step is to get the simulation running.

The first thing that has to be taken into account with life is the grid. I wanted to have a flexible size of grid but the key question of dealing with the grid is that in theory, the grid is suppose to be infinite. This is not necessarily realistic so the issue becomes how to deal with borders. I decided to support three different types of borders. Always dead, Always alive, and wrap-around.

The border issue makes the getCell function that I wrote for grabbing a cell a bit complicated as it has to see if the desired cell is within the bounds. If not, it then has to figure out how to deal with it, with wrap-around being a bit complex as it has to convert the passed coordinates into valid coordinates. All this condition testing has me concerned about performance, but I figure if it proves to be an issue I can do some optimization later.

Iterations of the game use the existing grid to spawn the new grid so the LifeGrid class actually creates two grids. The current grid and the old grid. Because the getCell function which I am using uses the current grid, the new grid is created in the old grid space and then the two grids are swapped. For each tile in the grid, the number of alive tiles surrounding it are counted. The rules of life are then applied and we know what the cell is going to be in the next iteration. The rules are fairly simple:

1 - If there are less than two neighbors, a living cell dies of loneliness.
2 - If there are more than three neighbors, a living cell dies of over-crowding.
3 - If there are exactly three cells, an empty (dead) cell becomes a living cell (newborn).

Because of some of the features that I know I will want in the future are dependant on knowing the age of the cell, the age is adjusted as well for each iteration.  The LifeGridViewer right now simply draws the cells in red for dead and green for alive. This will change soon, however.
DDTe4 Hours 7 to 12 - Controlling Life

With the game functional, the next step is to implement controls that allow the user to modify the game. While the controls that I implemented could have been completed quicker, I found myself spending a lot longer testing the game then was absolutely necessary as there is just something fascinating about watching the simulation.

Before it is possible to watch a simulation, the simulation must first be animated. In the case of Life, this is simply a matter of displaying consecutive iterations automatically. In browsers, there are two ways of handling the timing. You can set an interval which calls a function after at least the specified time interval has expired. This happens repeatedly until the interval is stopped. For a bit more control, there are timeouts, which work just like intervals except they only call the function once.

To control the animation, a small set of controls are needed. For  this game I opted to use html controls that appear below the game display. This is largely due to the fact that the controls are more for options and the real joy comes from watching the display. For the animation, a combo-box is used to allow for different playback speeds, the play button which will become a pause button when clicked, and a single step button for those people who want to analyze the progress of the simulation.

Once the animation was working and tested, adding more control over the colors became my next challenge. I wanted the ability to see the aging of the cells but also wanted the more traditional monochromatic style of display. To allow for these, I decided to use a color set approach where an array of colors are used to determine what is shown for different ages and states for the cells. By setting all the ages to the same color you can create a monochromatic style display. I created a large number of color sets so players should be able to find a color scheme they like.

With a more colorful display finished, controls over the size of the display and whether or not to show borders were added. As different sized grids were already implemented in the core game classes, this was very simple to implement. However, when the simulation was ran at a higher resolution, the speed slowdown was quite significant. Running the firebug profiling tool showed the problem was with the display code.

This had me confused as the display of the simulation is remarkably simple as all it is doing is drawing a large number of rectangles. These should be drawn exceedingly fast. As I looked over the code to see if I did anything stupid, it dawned on me that the color was changing for every rectangle. This shouldn't be a big issue, and with most graphics API's it would not be a problem. However, the Canvas API uses the DOM color model which is string based. This means that for every color change, the string gets converted into a number. The overhead for all this string processing is very high.

At this point, I was banging my head trying to figure out a way of speeding things up without resorting to the lower level canvas ImageData API. While this API gives you access to the raw color data, it would be a lot of work to implement. Then it dawned on me that most frames consist mostly of long-dead cells. Instead of drawing every cell, I really only need to draw the living and recently killed cells. By blanking the display and drawing only the living cells, the speed of the simulation increased dramatically.

The final feature that I knew I must have before I could consider this project releasable would be the ability to manually add cells to the display. This was handled by simply converting the mouse click to a tile coordinate and setting that tile to alive.

With this done, the project is in a releasable state, but I still have at least four hours to invest into this project so the question is what to work on next? More optimization would be nice to speed things up a bit more, but for some reason the idea of adding cancer came to my mind.

No comments: