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:

- 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.
- We have to bring some dead cells to life. This is called
**spawning** a cell.
- We have to
**kill** some cells.
- 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:

- 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.
- 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:

- Iterate through
`toExamine`

. This will determine which cells to insert into `toSpawn`

and `toKill`

.
- Iterate through
`toSpawn`

and `toKill`

. This will both insert and remove cells from `alive`

. It will also determine which cells to insert into `toExamine`

.
- 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:

- Iterate through
`toSpawn`

and `toKill`

. This will both insert and remove cells from `alive`

. It will also determine which cells to insert into `toExamine`

.
- Iterate through
`toExamine`

. This will determine which cells to insert into `toSpawn`

and `toKill`

.
- 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:

- 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.
- 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.
- 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.