Conway’s Game of Life

Howdy. I’m in Russia. (Ok, not anymore, but I wrote most of this last week.)

I just wanted to get that out of the way, because I think it’s awesome and worthy of attention. Also, it explains why I haven’t been doing too much since around Christmas. I’ve been spending all my time between the opulent museums, palaces, & churches and hidden little corners of St. Petersburg. It’s fantastic and wonderful and I’m having the time of my life. I am not, however, accomplishing much on my computer.

That said, traveling is a mixed blessing when it comes to coding projects. Even though the art and history and architecture and LIFE of the city is distracting, I also spent a lot of time in planes and airports to get here. As it turns out, restricting oneself to 3x3x5 cube feet of space for 22 hours is pretty good incentive to write some programs — games, in this case — offline. Though I suppose Tetris would have been more appropriate given my destination, I used the journey to implement Conway’s Game of Life.

“Game” is a bit of a misnomer here. One doesn’t “play” Life. It’s a cellular automaton: a simulation performed on a tabular grid. In the Game, each cell starts either alive or dead. During each successive generation, the following rules apply to each cell:

  •     a live cell with 2-3 neighbors survives to the next generation
  •     a live cell with more than 3 live neighbors dies (due to overcrowding)
  •     a live cell with fewer than 2 live neighbors dies (due to undercrowding)
  •     a dead cell with exactly 3 live neighbors becomes alive (is birthed? That has some rather raunchy connotations. Saucy cells!)

That’s pretty much it. Conway’s Game of Life is fun, because with those very simple rules and a good starting pattern, you might see any number of interesting states in subsequent generations. Whether you’re drawing each frame with pencil & paper, or crunching everything with a high-powered supercomputer, the emergent properties of the simulation are very quick to appear. For instance, you might very quickly see one of these patterns, called “Still Lifes.” These are small, stable configurations — they will remain exactly as they are forever. Count for yourself: each live cell has enough neighbors to keep surviving, and no dead cell has sufficient resources to …come alive (maybe resurrect is a better term). Images, as usual, sourced from Wikipedia.

Block

Beehive

You might also see “Oscilators,” like these. Not quite stable, but they will stay in place and, barring any external influence, will cycle through their limited set of frames.

Blinker

Beacon

An entertaining type to find are “Spaceships,” which are like Oscilators, except they move across the grid over the course of several generations. Call these the migratory cells.

Glider

I’ve already written an implementation of Life at one point. My class group was using it as a benchmark to test parallel computing on a GPU (a piece of hardware particularly adept at crunching numbers, or in this case, cell life, in parallel) using CUDA (a parallel computing platform). Of course, that implementation was in C, and we really didn’t care about display, merely the runtime. This time around, my goal was to make it approachable — an electronic toy that anyone could play with without having to compile system-level code. Since I didn’t have access to the documentation for anything more complex on the plane, I decided to try it with something familiar: javascript. I was going to write Life as an HTML/javascript page, using the jQuery library. That would mean you would be able to open it in your browser and behold all the coloful fun of cells living and dying.

Unfortunately, I didn’t succeed. Or better put: I didn’t succeed well. I got the display working, and managed to apply Life’s rules to each cell. In effect, the grid would load (all via javascript), and you could set up an initial pattern, or call up a randomized configuration. That done, you could “step” from one generation to the next. However, I failed to run generations continuously in an efficient way. The net effect is that the browser locks up under the load of all the javascript computation, killing both the display of the grid and your ability to check your email.

There are two major reasons (and several minor ones) that cause this freezing-up. The most obvious one is the need for a slight delay between the processing of generations. Such a pause would allow you, slow human, to actually perceive the changes wrought on the Life board; it also helps compensate for the speed difference between the computation of life statuses (crunching numbers: fast) and the display update of any cell on the board (querying the DOM: slow, comparatively, a little more so if using jQuery). Unfortunately, by design, javascript isn’t meant to pause its own execution. It’s intended for DOM manipulation (Document-Object Model — essentially, the web page you’re viewing), so it’s better at performing small, quick interactions when invoked. There aren’t many resources for what I’m trying: an continuous job, with minute breaks intersperced everywhere.

The best option I found was setInterval(fn,dl), which, when called, will run the function named “fn” after every “dl” milliseconds. Sounds perfect for the job, right? Alas, putting this in the main game loop gave me a mystery error: something to the effect of “unnecessary call to setInterval at line #…”. Thanks, javascript. That told me exactly what was wrong. (You schmuck.) The only way of getting around setInterval() would be to refactor the code, making room for the use of a wait(seconds) function. But as I mentioned, there’s no way to make javascript sit idle. So the only way to write wait() would be to give it a meaningless computation for a certain amount of time. Something like this:

var x = 4000;
while (x > 0) {
x--;
}

Which continuously decrements x until it is equal to zero. The larger the initial value of x, the greater the delay. (Note that you could be a little more sophisticated by making the while-condition a comparison of the current time and the time at which javascript should stop waiting. This is just an example, after all.) The problem with this approach is that javascript is still doing something, meaningless though it may be. And since javascript is doing something, your browser is doing something — continuously. That causes the exact kind of lock up that I was trying to avoid in the first place. Argh. So ultimately, as best I can figure, if I am to create any other game loops in javascript, I must find out what the hell is wrong with setInterval().

The other fundamental issue I need to rethink is the algorithm I’m using. In my increasingly jet-lagged state, I wrote the most obvious implementation of Conway’s Game. Namely, you create a table with a given number of rows and columns, and for every generation, do something like this:

for each row r
    for each column c
        // count the number of live neighbors of cell (r,c)
        live_neighbors = countNeighbors(r,c)

        // assign life status
        if (live_neighbors > 3) or (live_neighbors < 2)
            cell is dead
        if (cell is dead) and (live_neighbors == 3)
            cell is alive

Though sufficient, this naive implementation has huge optimization problems. To begin with, it gives every cell equal consideration. That’s potentially a huge waste of time, if only a few cells are alive in the entire board. We can get much faster processing with equivalent behavior if we could target only the area surrounding clusters of live cells.

Secondly, though it isn’t immediately obvious, you actually need two boards whenever you run generation-updating snippet above: the original board, and the board for the new generation. This is because changing the life status of any one cell will affect its neighbors’ live_neighbor count before the neighbors themselves have been updated. In essence, though we must update the cells sequentially, we want it to appear as if they were all being updated at the same time.

I’m sure such an algorithm has already been figured out, so I won’t have to come up with anything from scratch. Fixing the setInterval() delay between generations may be a greater challenge in terms of research, but I’m positive that the challenge can be surmounted. Why such certainty? Because it’s been done. Here one particularly pretty javascript implementation for your perusal: http://pmav.eu/stuff/javascript-game-of-life-v3.1.1/

Maybe once I get the thing working properly, I’ll post the prototype I’ve been working on. At the moment, though, I consider it far too “rough” for public consumption.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: