Hoyvin Glavin!

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.