Hoyvin Glavin!

On technical minutiae, by Jeff Lee

Accessing Rails helpers outside views

fence

Prominent among my gripes about Rails is its handling of view helpers. These are mixed into the view object to provide easy access from template code, but the price of this convenience is a total lack of namespacing, reminiscent of ye olden PHP days.

What’s more is that Rails seems to have an excessively narrow opinion about what constitutes a “view”: view helpers are easy to call from HTML and email templates, but there’s no consideration paid to other possible outlets from your app, including HTTP headers, command line output, file streams, or email subject lines.

Solutions to the latter problem are divers and arcane, frequently involving an undocumented, hard-to-remember expression that dispatches helpers through the controller instance. Of course, this works if you’ve actually got a controller instance handy, but isn’t so great when you’re, say, running a Rake task. And in the first place, since most helper methods are just text filters, it seems silly that they should be coupled to this or that object. Why can’t we just call them from anywhere, as the generic utilities that they are?

As it turns out, most of the built-in helper methods are mixed into the ActionView::Helpers module as instance methods. In order to call them as globals, you need to host them in another module where they appear as class methods. And thus, my favorite workaround:

With this in place, you can call your helpers as globally-accessible methods, as follows:

The pleasant thing about this solution is that it’s easy to remember, and works from whatever context you’re in, whether it’s the body of a Rake task, a controller action, a method on a model class, or even your view templates.

JCVJ mini-postmortem

I knew Thailand very well, so I showed her my Thailand.

Over the weekend I participated in Babycastles’ 48-hour game jam tribute to the life and exploits of one Jean-Claude Van Damme. The event was inevitably titled the Jean Claude Van Jam.

My team consisted of David Mauro, who provided art and jazzy UI code, and Jen Taclas, who scoured the web for choice JCVD quotes and led the scriptwriting effort. I screamed profanities at a text editor and illegally downloaded Kylie Minogue songs from BitTorrent; I expect to be prosecuted for both. The game we made is called Show Her My Thailand. The source code is on Github, if that’s your thing.

Read the rest of this entry »

A C++ signals/slots library, mostly from the ground up

'Post Modern Times'

Having spent the better part of the last year monkey-patching, mixing-in, and duck-typing my way through vast brambled acres of Ruby code, I at last threw up my hands and decided it was high time for a brief retreat to the warm and fuzzy land of type-safe languages. The result was jl_signal, a C++ signals/slots implementation based on a system I used for a game project a while back. Source code and API documentation are available on GitHub.

This system lets you create a list of functions at runtime and invoke the entire list with a single function call. This is useful for writing GUIs and other event-driven systems where generic components can trigger all kinds of side-effects. The API has minimal syntax burdens and is easy to use, with certain caveats. It is also fast, and doesn’t allocate to the heap.

Here’s what it looks like:

Below are some remarks on motivation and implementation.

Read the rest of this entry »

Redis as a mutex service

Lock

TL;DR

Because Redis has atomic mutators that return useful information on what got modified, you can use it to provide test-and-set, the essential primitive operation for mutual exclusion. This means you can synchronize two or more independent processes, even if they are running on different machines, as long as they can both talk to the same Redis server.

WTF

I strongly suspect that the following is an insane, hacky workaround for a problem that most likely has a more robust and formal solution. But since I did not discover any such solution after ten minutes of looking, this is what I did.

Read the rest of this entry »

Hacking the NY Times paywall

Need to cut to the chase? Get the NY Times paywall remover for Chrome.

For some months now we’ve been suffering under the yoke of the New York Times’s subscription paywall, which has driven parsimonious, petit-bourgeois netizens like me to the journalistic doldrums of the LA Times and Washington Post. At least there’s less David Brooks in the world now, we mutter to each other, but it’s little consolation, as we’re forced to admit that there really isn’t a great substitute for the Old Gray Lady when it comes to mainstream news.

Slightly less well-publicized is the surprising porousness of said paywall (more of a “pay fence” according to some), which, as I have just now personally verified, is as easy to circumvent as editing the URL of the article that you happen to be reading. What’s more is that behind the paywall, it appears that article content is still delivered in its entirety, and anyone with a modern browser and a bit of tech savvy can browse away with impunity even after the monthly article limit has been reached.

Read the rest of this entry »

On the productive use of metrics in the development of gory vampire games

This blog entry was featured on Gamasutra on 2011.6.22

I spent the last six months working with my good friends at WayForward on the upcoming 360/PS3 downloadable title BloodRayne: Betrayal. BloodRayne is WayForward’s somewhat-ballyhooed first attempt at an HD console game, and as such, there’s probably a lot of interesting technical remarks to be made about our frequent missteps, and occasional successes, along the gory path to its completion. But for various NDA- and time-related constraints, this entry will stick to a somewhat peripheral subject: the use of game-generated, server-tracked statistics to supplement the development process.

The shorthand terminology I’ll use for this topic is metrics, which for most game industry establishment-types tends to conjure images of the back room at Zynga, where cackling MBAs with protractors and slide-rules measure the exact point where the dilation of one’s game-addled pupils goes from signifying Mind-Numbing Tedium to Big-Time Profits. This being a technical discussion, I’ll elect to sidestep the precarious, albeit interesting, debate over the aesthetic and spiritual merits of metrics-driven game design. Suffice it to say that BloodRayne, very much a product of an old-school design and development process, benefitted greatly from a very moderate application of metrics, and could have used even more had we had the time and wherewithal.

The imaginary ideal, as proffered by our illustrious lead programmer, was to produce a “heat map” system that would enable us to overlay our gameplay worlds with a dense mass of visually-rendered statistical data, which would in turn allow us to tell at a glance how quickly testers were progressing through our levels, where they were most likely to die, which moves they were using to deal the most damage, and so on and so forth. Unfortunately, the inspiration for this system hit us with roughly two months left on the schedule, and with a fair amount of feature implementation still on the docket, we were forced to settle for something much more modest. What we ended up with was still very important to tuning the game’s scoring system, and played a surprisingly useful role in the debugging process.

Basic design

The technical scheme we came up with for BloodRayne’s metrics system was nothing particularly fancy: we’d a) send JSON-encoded data in the body of an HTTP POST request to our in-office web server, which would b) invoke a PHP script that threw all of the incoming data into MySQL, and then we’d c) write one-off scripts to collate and present the data as we needed them.

We decided fairly early on that the data produced by the game would determine the database schema. In other words, we did not define our SQL tables in advance. Instead, we let the gameplay code generate data in the form of arbitrary key-value pairs, and made sure the server script was smart enough to create tables or modify pre-existing tables when necessary.

Having been weaned on certain data design paradigms that preach the sacredness and run-time inviolability of one’s table schema, I at first found such cavalier treatment of the database to be sort of gross and philosophically outrageous. But it did turn out to be the fastest way to churn out lots of data, since it relieved us of the duty of preparing the schema before we started pumping statistics into the database. With the table schema defined implicitly by whatever was in our gameplay code, our only real responsibility was to make sure that we were type-consistent about the values we were sending to the database; e.g., if the health field was initially sent as a floating point value, we needed make sure it wasn’t later sent as a boolean.

Our JSON encoding of a row of data was about as concise as is theoretically possible, and looked something like this:

Here, the types of each field were single-letter strings, indicating your usual data primitives: integers, unsigned integers, floating point numbers, booleans, and strings. Specifying the type allowed us to generate new table columns if necessary, and to type-check against pre-existing columns as well. The values for each field were encoded as strings, produced by running plain old C data through sprintf(). In order to keep string length down, we didn’t bother to use JSON objects with named properties—we just stuck with arrays and inferred the role of each string token based on its context.

Run-time implementation

The C++ API for this system was also designed to be as simple as possible, so that gameplay programmers could instrument their code with just a few calls to the metrics library and see immediate results in the server. We wanted the code to be no more complicated than the following example:

We used a variety of tricks to make this as fire-and-forget as possible. We made sure that gameplay programmers didn’t have to worry about cleaning up any allocations that the metrics API might have made, and also designed the API so that metrics code could be safely embedded in gameplay code even if the metrics system had been disabled or compiled out of the build.

As a final expedient, we made it so that gameplay programmers could specify project-specific metadata that would be included into every row of data sent to the server. This included fields that would describe the source of the data, such as the revision number of the executable, and the timestamp corresponding to the moment that the data was inserted. So the actual JSON data sent from the above sample would look something like this:

It’s amusing to recall that despite all the effort put into making this system as generic and flexible as possible, we were still too lazy to implement DNS support in our network wrapper functions. We just left the IP address of our local database server hardcoded into the source.

Usage example 1: scoring system

Our first application of this metrics system was to collect information about player performance. BloodRayne consists of several five- to ten-minute levels, each broken down into platforming sections and intermittent “screen-lock” battles, in which all enemies must be defeated before the player can progress. At the end of each level and screen-lock battle, we fired a slew of performance statistics at the database server: the time relative to the start of the level, the amount of health lost by the player up to that point, the number of points accrued from defeating enemies, the specific means by which an enemy was killed, etc. etc.

This data enabled us to answer questions of a very specific nature, such as “For level X, given the player’s accumulated score, what canonical letter ranking (i.e., F, C, B, A, or S) should we award?” It also gave us a fair amount of insight into which levels and which battles were too long or too difficult.

The process of analyzing this data was, as with much that goes on behind the scenes in game development, decidedly unsexy. Rather than writing a script to iterate through the data and present statistical summaries, the programming staff elected instead to deploy the tried-and-true Browse The Raw Data Directly strategy. Pleading overwork, we swiftly passed the buck around the cubicles, until it devolved to our harried and unsuspecting designer-director, who was deemed more than fit for the task after he produced this fine piece of analytical demagoguery concerning the overdeployment of air freshener in the WayForward bathrooms:

Eyeballing data in phpMyAdmin may seem to be, in the parlance of our times, a ghetto tactic, but it works surprisingly well for producing ballpark estimates and alternatively supporting or refuting one’s hunches about the quality of the game’s play-balancing. We spent a lot of time trying to see what peak gameplay performance looked like from a numerical perspective, and in many of these instances, we could simply have a designer or an expert tester play through a level and then immediately load up the raw data to take notes.

Usage example 2: tracking memory leaks

The conversation about game statistics had always been framed in terms of measuring some kind of player behavior, but we eventually ended up using metrics to great success for debugging under-the-hood systems such as dynamic memory allocation.

BloodRayne splits its memory allocation into several system-specific heaps. A simple technique for making sure you aren’t leaking memory is to record the allocation size of a heap, perform allocations and deallocations, and then re-sample the heap’s allocation size to verify that it is the same as your initial sample. But for various structural reasons, it wasn’t easy to come up with a consistent method of performing checkpoint operations on our heaps. Some subsystems made allocations that were meant to survive in perpetuity, making it hard to know what allocation values to verify against. On top of this, not all subsystems performed deallocations during the same moment in the game flow, so it was difficult to find a single, general spot to situate our checkpoints.

However, one thing we could do was plot heap allocations over time, and see if there were any patterns—in particular, an upward trend in allocation size would strongly imply a memory leak. So we hooked up our metrics system to broadcast the allocation state of each heap at transitional moments in the game flow, mostly when the player progressed from one game level to the next. We could gather this data from our testers without interrupting their playthroughs, and since we had data from multiple sources, we could get a rough idea of how consistent our memory leaks were.

Since it fell on me investigate most of our memory leaks, I afforded myself the extravagant luxury of creating a visualizer script for our heap allocation data. I promised my colleagues in no uncertain terms that it would be a cold day in hell before I would be railroaded into squinting at thousands of rows of data from phpMyAdmin. After all, what was I, a peasant?

A search for “javascript plotting” led me immediately to flot, a relatively simple graphing library that produced unambiguously pimp-looking results. A few days of fiddling resulted in graphs such as the following:

Above, we see a graph of 123 allocation samples, constituting about an hour or two of gameplay, to the misc heap, which is BloodRayne’s primary heap for game object allocations. The allocations here are considered well-behaved, in that there is no identifiable upward trend in their size. Any sustained peaks in the allocation pattern are due to level reloads (almost always attributable to a player’s death), which do not flush loaded game assets from memory.

Here, on the other hand, is a pattern of allocation that is not well-behaved:

The above graph provides smoking-gun evidence of a memory leak in our physics system. Total allocations clearly jump up by a similar amount at certain moments. Because all ticks along the x-axis are labeled with the same index, we know that the same level is being loaded over and over again. But since the jumps don’t occur at every instance, we also know that the leak is intermittent.

Tracking allocations in this manner wasn’t just useful for finding memory leaks. It occasionally helped us realize when we’d done something stupid. For example, at one point I’d unwittingly broken the game’s sound asset preloading. Following my mistake, allocations to our sound heap ended up looking like this:

Pretty gross-looking, but in the case of our sound system, the upward trending was not a sign of leaks. Rather, commonly-used sound effects were being loaded on-the-fly and were remaining resident in memory. After re-enabling the preloads, sound allocations returned to a calmer allocation pattern:

Regrets

During BloodRayne’s post-mortem meeting, there was much mutual back-patting about the success of our metrics system, but it was generally agreed that we could have used more of it, and we could have used it earlier. Still others bemoaned the fact that we didn’t have a system like this in the final version of the game, so we could see what players were doing with the game after it was released into the wild. In any case, the consensus was that we’d barely tapped the potential of our metrics system, and that there was no way any of us was going to make a another game without it or something similar.

From a technical standpoint, there are some obvious things that would really improve the system described above. Clearly, if we’d really wanted to receive player data from the consumer version of the game, or if we wanted an external QA team to help us produce data, we’d need proper support for DNS and HTTPS. Also, if we wanted super-granular datasets, of the kind that could produce “heat map”-style data visualizations, we’d probably have to sacrifice some flexibility in the data schema and use something that allowed us to reduce the relative verbosity of our outgoing data.

But beyond the boilerplate network tech, what we really could have used was a more precise means of describing where each piece of data was coming from. We did in fact supplement our data with a timestamp, an ID for the source hardware, and the executable’s revision number, but we had no generalized method of identifying each unique boot-up or playthrough of the game (heap allocation tracking used an ad-hoc method of passing an integer counter that was incremented for each successive sample sent to the server). Moreover, we had no means for filtering out junk data that we didn’t need. For example, if a QA guy is playing the game to see what happens when he dies a hundred times in the same spot, then the data he is generating will not be particularly useful for the purposes of play-balancing the game. My impression is that a mature metrics system essentially needs some way of managing demographics—that is, it needs to be able to collate and filter the data based on where the data is coming from, who generated it, and the context it was generated in.


The uncanny just gets uncannier

Here was have a three-month old video, showcased by Epic at this year’s GDC. It might be because I’m watching through the lens of someone’s phone camera, but I just feel slightly creeped out and bored by this video. What titillation I do feel is decidedly intellectual, rather than visceral—there is surely a huge amount of technical wizardry behind the lighting here.

Perhaps just as pernicious as the uncanny valley curve is a curve of diminishing returns on whizbang graphics, where we as viewers become so inured to graphical realism that major technical advances in the field no longer seem to deliver the same wow factor. “Wow factor” is a terrible phrase, but it’s probably better than “impressiveness”. But you get my point, yes?

Opening folders in TextMate via Finder context menus

OSX’s Finder allows you to send files to applications through the “Open With” context menu option. However, this is not available when the context menu is opened over folders.

Some applications, however, do interesting things when you open folders in them. TextMate, for example, opens the folder in project view, so you can use its drawer to browse documents in the folder and its subfolders.

There are various guides on the web that explain how to setup folder access to TextMate from Finder context menus, but I noticed that they contain some superfluous steps and don’t work with pathnames that have spaces in them. Here’s my slight variant:

  1. Make sure that the mate command is in your execution path. (cf. the entry in the official blog on how to do this).
  2. Launch Applications > Automator.
  3. Select File > New and choose the Service template. This will create a new workflow, which is a GUI script that will perform some task.
  4. Change the Service receives selected drop-down option from text to files or folders.
  5. Add a Run Shell Script action to the workflow. You can do this by searching for the phrase “run shell script”, and then double-clicking on the resulting option.
  6. Change the Pass input: drop-down option from as arguments to to stdin. Each file or folder selected in Finder will be passed to our workflow via standard input, separate by newlines.
  7. Paste the following shell command into the text area:
    sed 's/ /\ /g' | xargs mate

    This takes each file or folder selected in Finder, escapes all spaces in their pathnames, and passes them one by one to TextMate.

  8. Save the workflow, using the name of the option you want to appear in your context menu. I used “Open in TextMate”.
  9. This workflow will get saved into ~/Library/Services. It will appear automatically in your context menu.

This should allow you to open any number of files or folders in TextMate via Finder, including pathnames that contain spaces. It may run into issues if your pathnames contain quote characters, but let’s hope those are few and far between.

MySql TIMESTAMP column type considered harmful

Time Selector

MySQL has a weird auto-updating field type called TIMESTAMP, which can be automatically populated or updated with the current time when you insert or update a row. It’s probably not 100% kosher practice to have a system changing your data without your explicit approval, and yet one could imagine this being useful for logging purposes, or for simplifying your insertion queries.

Unfortunately, this auto-updating functionality operates under very awkward and seemingly pointless constraints. The details are laid out in the MySQL 5.0 reference manual, but the upshot is like this:

  • Regardless of how many TIMESTAMP fields your table contains, only one of those fields may be automatically populated or updated with the current time.
  • The first TIMESTAMP field will have the auto-populating, auto-updating functionality enabled by default, and the only way to disable it is to force a default value on the field.

In other words, you have very little flexibility in terms of which fields can use this feature, and you could have automatic changes to your data that are not obvious in your schema unless you are well-versed in the idiosyncracies of MySQL’s time types.

This behavior has evolved only slightly over the past decade, and in such a way as to complicate and exacerbate the problem rather than fix it. With MySQL 4.1, you gained the ability to apply the auto-update feature to a TIMESTAMP field other than the first, but the process of doing so involves setting a default value on the first TIMESTAMP, a pointless and potentially damaging restriction.

Moreover, you are still forced to contain all automatic behavior to a single field. This is fine in the case of automatic updates, since any auto-updating timestamp beyond the first would be redundant. But it also applies to auto-populating, which means you cannot have a field that automatically populates itself with the time of insertion (a creation timestamp) alongside a TIMESTAMP field that automatically updates itself when the row is updated (an update timestamp).

I’m sure the longevity of this “feature” is due to backwards-compatibility reasons, with so many extant schemas in the wild relying on it, but it really ought to be deprecated and highlighted in the documentation with red 24-point Impact and <blink> tags.

For keeping time data, I use the DATETIME type almost exclusively in my schemas. It obviates the issue by providing no automatic behavior whatsoever. If I use TIMESTAMP at all, it only occurs once in a table, and it is always used to track when a row was updated. I even mark it with the verbosely redundant attributes “DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP”, which might be pedantic or paranoid or both, but at least one can tell how the field will behave when glancing at the schema.

A simple implementation of Life, part 2

In the first part of these notes, I described the simplest imaginable algorithm for simulating the Game of Life. That approach wasn’t so great, since it required us to visit every cell several times in order to produce each successive generation of cells.

In order to speed the simulation up a little bit, or at least to make it a bit more efficient in theory, I’m going to complicate the algorithm by keeping some extra data on the side that summarize some information about the current generation. Specifically, this extra data tell us which operations need to be performed on which cells.

Wait, what were our operations again? Let’s review:

  1. We have to count the live neighbors for each cell. Let’s refer to this operation as examining a cell. When we examine a cell, we count how many of its neighbors are alive.
  2. We have to bring some dead cells to life. This is called spawning a cell.
  3. We have to kill some cells.
  4. We have to draw all of our live cells.

We’re going to end up maintaining a separate list of cells for each of these operations. I’ll discuss these one by one, but it’s easiest to do it in reverse order.

alive as a list

In the original implementation, we used a grid of boolean values, alive, to keep track of which cells were alive and which cells were dead. Let’s instead treat alive as a list containing the coordinate pairs for every cell that is currently alive. We just assume that if a coordinate pair is not inside alive, then it represents a dead cell.

When treating alive as a list of coordinate pairs, rather than as a grid of booleans, our procedure for examining cells doesn’t change a whole lot:

for each row "i"
for each column "j"
    set liveNeighborCount[i, j] to 0
    for each neighbor of the cell at (i, j)
        if neighbor is in alive
            add 1 to liveNeighborCount[i, j]

Spawning and killing don’t look all that much different, either:

for each row "i"
for each column "j"
    if (i, j) is in alive
        if liveNeighborCount[i, j] is not 2 or 3
            remove (i, j) from alive (kill!)
    else
        if neighborCount[i, j] is 3
            insert (i, j) to alive (spawn!)

But check out how much simpler the draw operation is, now that we have an exact list of the cells that need to be drawn:

Draw a blank grid

for each (i, j) in alive
    draw a square at (i, j)

Importantly, we’re no longer examining every single cell in the grid in order to determine whether or not we should draw it.

The toSpawn and toKill lists

In our original implementation, we used two exhuastive passes through the grid to handle 1) examining our cells (i.e., counting each cell’s live neighbors) and 2) applying our rules for spawning and killing cells. These had to be distinct passes, since we had to determine the live neighbor count for every cell before we could start spawning or killing anything.

Now let’s try something new: during the first pass, while we are examining each cell, we’ll apply our spawning/killing rules as soon as we determine an individual cell’s live neighbor count. But instead of directly changing the contents of alive, we’ll put the cells we need to spawn into a list called toSpawn, and put the cells we need to kill into a list called toKill.

The combined examining-spawning-killing pass looks something like this:

for each row "i"
for each column "j"
    # First, count this cell's live neighbors
    set liveNeighborCount[i, j] to 0
    for each neighbor of the cell at (i, j)
        if neighbor is in alive
            add 1 to liveNeighborCount[i, j]
    # Next, apply the spawning and killing rules
    if (i, j) is in alive
        if liveNeighborCount[i, j] is not 2 or 3
            insert (i, j) into toKill
    else
        if neighborCount[i, j] is 3
            insert (i, j) into toSpawn

Once this is done, we can now update the contents of alive by iterating through our two new lists, toSpawn and toKill:

for each (i, j) in toSpawn
    insert (i, j) into alive

for each (i, j) in toKill
    remove (i, j) from alive

empty out toSpawn
empty out toKill

Note that we have to empty out toSpawn and toKill once we’ve finished, or else their contents will affect the processing of the next generation.

It doesn’t look like this particular modification has actually bought us very much efficiency. Sure, we’ve gone from having two passes through the grid to having a single pass, but that one pass does twice as much stuff at each cell. On top of that, we’ve piled on some additional iterating thanks to our new lists.

The efficiency advantage of organizing our algorithm like this won’t be clear until we get to our final improvement, the toExamine list. But having a list of all the cells that get spawned and killed does have at least one neat side-effect: we can use them to display a preview of which cells will change when going to the next generation. In other words, it lets us make pictures like this:

(blue dot -> toSpawn, red dot -> toKill)

The toExamine list

By this point, we’ve modified the simulation so that drawing, killing, and spawning all occur using a quick iteration through a list. These operations now process only the cells they have to, and no more. But examining cells still requires a complete pass through every cell in the grid.

Following the previous pattern, we’ll keep a list of cells called toExamine. This list will tell us exactly which cells need to be examined, and thus eliminate the need for any complete passes through the grid.

But how do we know which cells need to be examined?

To answer this question, it helps to observe a useful property that emerges from the rules of Life: if none of Cell X’s neighbors were spawned or killed in the previous generation, Cell X itself will be neither spawned nor killed in the current generation. In this situation, Cell X’s live neighbor count in the current generation is exactly the same as it was in the previous generation, which means its own state won’t change going into the next generation.

This implies that we don’t have to bother examining Cell X as long as none of its neighbors were spawned or killed in the the previous generation. Obversely, this means that the only cells we need to examine are the neighbors of cells that we’ve spawned or killed.

Another way to think about this is that when we spawn Cell X, we have just increased the live neighbor count of each of Cell X’s neighbors by one. Similarly, when we kill Cell X, we have just decreased the live neighbor count of Cell X’s neighbors by one. In either case, we’ve changed the live neighbor count for each of Cell X’s neighbors, and so we’re forced to consider whether any of those neighbors need to be spawned or killed as a result.

The upshot for our algorithm is that every time we spawn or a kill a cell, we should insert all of its neighbors into toExamine. With this in mind, we can change our spawning and killing process to the following:

for each (i, j) in toSpawn
    insert (i, j) into alive
    for each neighbor of the cell at (i, j)
        add 1 to liveNeighborCount[neighbor]
        if neighbor isn't already in toExamine
            insert neighbor into toExamine

for each (i, j) in toKill
    remove (i, j) from alive
    for each neighbor of the cell at (i, j)
        subtract 1 from liveNeighborCount[neighbor]
        if neighbor isn't already in toExamine
            insert neighbor into toExamine

empty out toSpawn
empty out toKill

It’s important to point out two things here:

  1. Notice that each time we process a spawn or kill, we are modifying the live neighbor count for every neighboring cell. The live neighbor count is no longer something we have to recalculate from scratch at the start of each generation—it is now a cumulative value that changes with every spawn or kill. Of course, this means that we’ll have to set the live neighbor count to zero for every cell at the start of the simulation.
  2. We have to make sure a cell only gets inserted into toExamine once, even if more than one of its neighbors gets spawned or killed.

Once we’ve populated toExamine, we can move on to processing it:

for each (i, j) in toExamine
    if (i, j) is in alive
        if liveNeighborCount[i, j] is not 2 or 3
            insert (i, j) into toKill
    else
        if neighborCount[i, j] is 3
            insert (i, j) into toSpawn

empty out toExamine

With this modification, we’ve eliminated the last remaining pass through the grid. All of our operations now work by iterating through small lists of cells.

Seeding the grid

You may have noticed that there’s a bit of a chicken-and-egg problem here. We’ve thus far assumed our operations will occur in the following order:

  1. Iterate through toExamine. This will determine which cells to insert into toSpawn and toKill.
  2. Iterate through toSpawn and toKill. This will both insert and remove cells from alive. It will also determine which cells to insert into toExamine.
  3. Draw cells using alive.

Step 1 and Step 2 produce what the other requires. This puts us in a bit of a pickle, since it’s not clear how or where this algorithm is supposed to start. It seems like we either have to re-organize our steps, or be very crafty in the way we seed our grid. Or both.

The first thing to notice is that our simulation doesn’t change much if we flip the ordering of Step 1 and Step 2:

  1. Iterate through toSpawn and toKill. This will both insert and remove cells from alive. It will also determine which cells to insert into toExamine.
  2. Iterate through toExamine. This will determine which cells to insert into toSpawn and toKill.
  3. Draw cells using alive.

Think of it this way: Step 3 doesn’t change the state of our simulation in any way—it merely reports the current status of the grid to the outside world. So we are really just alternating between Step 1 and Step 2. Once the simulation gets going, it really doesn’t matter which of the two we treat as occurring “first”.

With our re-ordered algorithm, we can seed our grid by inserting our initial live cells into toSpawn, rather than directly into alive. This will not only cause the cells to get spawned in the first step of the first generation, but it will also ensure that the neighbors of our seed cells will get examined properly.

And if we only did this much, we would be almost correct. When I wrote my implementation of Life, it actually took me a couple of hours to figure out why this wasn’t completely correct. The problem here is that when toSpawn gets processed, only the neighbors of the spawned cells get inserted into toExamine. But imagine if we seed the grid like this:

According to the rules of Life, this seed cell should die when entering the next generation. But if we only add this cell to toSpawn, it will never itself get examined—when we spawn the cell, only its neighbors will be inserted into toExamine.

Thus, we can’t insert the seed cells into toSpawn only. We also have to add them to toExamine as well. That way, we can make sure that we examine any seed cell that isn’t itself a neighbor of another seed cell.

Visualizing the algorithm

We’ve gone from an algorithm that does three complete passes through each cell of the grid to a tidy little algorithm that only processes the cells it needs to. I’ve written a lot of words on this, so let’s review with pictures.

We start by inserting our seed cells into toSpawn:

The seeds will be spawned into live cells in the first generation.

When toSpawn is processed for the first time, all of the neighbors of the seed cells will be inserted into toExamine. In addition to this, each of the seed cells will also be added to toExamine.

(light blue -> toExamine, dark blue -> alive AND toExamine):

We check the live neighbor counts of each cell in toExamine to determine which cells to insert into toSpawn and toKill:

(blue dot -> toSpawn, red dot -> toKill)

We spawn and kill the cells in toSpawn and toKill, leaving us with a new generation:

Here is how alive, toExamine, toSpawn, and toKill look for this generation:

And so on, into a third generation:

…and then into a fourth generation:

Notice that in this last image, some of the live cells appear in pure black. They were not inserted into toExamine, since none of their neighbors changed between the third and fourth generations.

The whole simulation in pseudocode

Seeding the grid:

for each row "i"
for each row "j"
    set liveNeighborCount[i, j] to 0

for each (i, j) in our initial seed pattern
    insert (i, j) into toSpawn
    insert (i, j) into toExamine

The simulation loop:

loopStart:

for each (i, j) in toSpawn
    insert (i, j) into alive
    for each neighbor of the cell at (i, j)
        add 1 to liveNeighborCount[neighbor]
        if neighbor isn't already in toExamine
            insert neighbor into toExamine

for each (i, j) in toKill
    remove (i, j) from alive
    for each neighbor of the cell at (i, j)
        subtract 1 from liveNeighborCount[neighbor]
        if neighbor isn't already in toExamine
            insert neighbor into toExamine

empty out toSpawn
empty out toKill

for each (i, j) in toExamine
    if (i, j) is in alive
        if liveNeighborCount[i, j] is not 2 or 3
            insert (i, j) into toKill
    else
        if neighborCount[i, j] is 3
            insert (i, j) into toSpawn

empty out toExamine

Draw a blank grid

for each (i, j) in alive
    draw a square at (i, j)

go to loopStart

You can check out the Python source of my implementation online at GitHub.

Appendix: When I say “list”, I actually mean “set”

In using the word “list” in the plain-old-English sense of an unordered collection of things whose internal structure is unspecified, I have been playing it a little fast and loose with my word choice. But as most of you are probably aware, the term “list” actually has certain structural implications to computer nerds: it could refer somewhat generically to a linked list, or to a specific primitive collection type in languages such as Python or Lisp.

If we look back at the way our lists are being used in the above pseudocode, we can glean some idea of how they should behave from a structural standpoint. For example:

  1. When examining cells, we do a lot of checking to see if alive includes a particular coordinate pair. It would be pretty nice to be able to do this in O(1), i.e. in constant time. In other words, we would rather not have to perform an exhaustive search through the contents of alive until we either a) found the coordinate pair we were looking for, or b) reached the end of the list.
  2. When spawning and killing cells, we are inserting and removing cells arbitrarily from alive. We’d want this insertion and removal to occur in constant time as well. It wouldn’t be great if we had to reorganize the contents of our “list” just because we removed a coordinate pair from the middle somewhere.
  3. When drawing cells, we just need to be able to iterate through alive very quickly.

I am unaware of any basic data structure that covers all these requirements intrinsically. The hash table comes closest: inclusion checks (#1), insertion (#2a), and removal (#2b) all work more or less in constant time.

But it’s not necessarily that easy to iterate (#3) through a hash table’s contents. Under the hood of your garden-variety hash table, you have a big array of bins and buckets, and trying to iterate directly through it would be painful.

Of course, you could try maintaining a linked list alongside the hash table. Since iterating through linked lists is very simple, you could keep the linked list around for the sole purpose of fulfilling the fast iteration requirement. You’d then use the hash table for inclusion checks, and also perhaps to retrieve references to the linked list’s buckets. And of course, insertion and removal are simple for both data structures.

In my own implementation, I used Python’s set data structure, which since version 2.6 is built directly into the syntax of the language. Handily, it more or less does everything we need it to do. Internally, it uses some kind of hash-centric structure, as indicated by the requirement that all insertable elements be “hashable”. Moreover, its interface is very convenient for inclusion checks and for ensuring that inserted elements are unique. As for the iteration issue, Python sets are treated implicitly as iterables by the syntax of the language. I’m not sure how this is implemented, but I’ve assumed it’s implemented in an efficient manner.