Join us and get access to thousands of tutorials and a community of expert Pythonistas.
This lesson is for members only. Join us and get access to thousands of tutorials and a community of expert Pythonistas.
Calculate Frames
00:00 In the previous lesson, I showed you the rules to Conway’s Game of Life. In this lesson, I’ll spend some time talking about different ways of representing the simulation’s data and how the algorithm works.
00:12 Except with the simplest programs, there’s almost always more than one way to approach a problem. In an earlier lesson, I hinted that one of the things to think about is how to represent the grid as data.
00:23 My first thought with a grid of data is to store it as a list of lists.
00:28 The blinker pattern would look like the code on the right here when using this format.
00:34 Although this will work, consider what’s involved in accessing the eight neighbors for any cell. That’s a lot of index calls.
00:42 You could use some list slicing to optimize it a bit, but this still feels like a bit of a clunky approach. It’s good from a storage standpoint, but not so good from our next frame algorithm.
00:54 Instead, you could use a list of strings where each string represents a row, but you end up with the same index access problem just referencing a character in the string instead of an item in a list.
01:06 Memory wise, this might be more compact as there’s a bit more overhead destroying an integer than a character in a string, but it might also thrash more as strings are immutable, so when you modify a cell, you’d be replacing the entire string, meaning more garbage collecting going on.
01:22 Python does have byte sequence data types, and you could use a list of bytes with a bit being on or off for alive or dead. These are immutable, so you don’t have the problem I mentioned with the string, and definitely would be more compact than a list of integers.
01:38 With clever use of bit masks, you could calculate the sums rather quickly, but you’re still having to access three rows to see all the neighbors for any given cells.
01:49 You might have guessed by the tone in my voice that I’m not going with any of these choices. Instead, I’m going to use a set of tuples where each tuple is the coordinates of the alive cells in the grid.
02:02 Dead cells take up no space, and each alive cell translates into a single tuple. By storing the coordinates in a set, I can take advantage of set math when applying my logic to things currently alive or dead.
02:16 I’ll show you what that means in a bit.
02:19 This kind of storage is sometimes referred to as sparse storage as I’m only storing the bits of the grid with information rather than the entire grid. Sparse storage is the right approach if the majority of a grid system is empty like it typically is with the game of life.
02:36 Okay, so set of tuples with alive coordinates, it is. What’s that mean for figuring out the neighbors? Consider this grid with each cell labeled using a coordinate pair. To calculate the coordinates of the neighbor to the right of cell 2, 3, I add one to the column and nothing to the row.
02:59 Applying that same logic, I can come up with a list of deltas to determine all the neighbors. To find all of the cell’s neighbors, I add each of the eight delta tuples in the column on the right to the cell coordinates. That’s accessing the neighbor.
03:15 How about counting how many are alive?
03:18 I’m going to come at this a bit backwards. First off, note that you only have to deal with cells that are currently alive. Only alive cells increase the count of a neighbor, and this is what I mean by backwards.
03:30 Instead of looking at a cell and counting its neighbors, I’m going to look at a cell and use it to increment a count on its neighbors. Once I’ve processed the whole grid, I’ll have a single number for each cell containing the count of alive neighbors.
03:45 This hurts my brain a little. Let’s look at an example starting with a blinker pattern with three alive cells, again, only processing the alive cells. The green cells are the neighbors to the cell I’m currently processing. All the green cells get an initial count of one neighbor as my current alive cell increments their neighbor count.
04:08 I then move to the second alive cell and repeat. The green cells this time are this cell’s neighbors and they all get incremented. Those values that were one in the previous iteration now become two.
04:22 Finally, I move to the third cell and repeat the process. Like I said, backwards hurts my brain, but if you pick any cell and count the alive neighbors around it, you’ll find this has worked.
04:34 Taking this approach means you can store all of the neighbor counts in a dictionary where the key is the coordinates of the cell and the value is the number of neighbors.
04:44 Again, this is sparse. Cells without neighbors won’t have a value in the dictionary.
04:50
A handy tool for building this kind of dictionary is the defaultdict in the collections module. This kind of dictionary provides a default value for a key.
04:59 If the key is new, by making the default an integer, you can access a key and add one to it. If there was no key there before, you’ll get zero plus one. If the key existed before, you’ll get the current value plus one.
05:15 This saves a bunch of if-then-else clauses checking if the key exists. With the neighbor counts in place, it’s time to use them to implement the rules. Let’s start with those cells that are alive and have two or three neighbors.
05:30 They’re the ones that stay alive. On the left, I’ve highlighted the cells that have two or three neighbors using the color blue. In the middle, I have the set of currently alive cells.
05:42 Because I’m storing these as sets, I can do set math on them doing an and operation. Any cell that is blue on the left and blue in the middle is staying alive in the final frame, which in this case is just the center cell, of course, that only handles those cells that are staying alive.
06:01 What about those that are coming alive? On the left, I have all the cells that have exactly three neighbors, once more highlighted in blue. Then in the middle, I have everything that is currently alive. As reproduction only happens for dead cells, I subtract the middle from the left to produce the two cells that are dead, becoming alive.
06:23 Finally, I take the results of the first and second calculations and union them together, giving the final result for the next frame, my blinker linked.
06:35 Although the approach taken here might not have been your first thought, it is particularly efficient, which is important if you start simulating large grids.
Become a Member to join the conversation.