Elsewhere in this issue you’ve seen our article on Conway’s Game of Life and how this strange game played on a big checkerboard has all the computational power of any computer.
What you may not have noticed is that all our examples actually came from an implementation in Scratch of the Game of Life. In this article we’ll give some guidance on how to code it up yourself because there are some pretty neat tricks involved in this one!
First, let’s review the very basics of the Game of Life:
- It’s a simulation that takes place on a square board of cells
- Each cell can either be “on”, or “alive”, or it can be “off”, or “dead”
- Whether a cell is alive or dead on the next round of the simulation is determined by three rules. These rules are:
- If a cell is alive and has either two or three neighbors then it’s alive on the next round
- If a cell is alive and has less than two or more than three neighbors that are alive, it’s dead on the next round
- If a cell is dead and has exactly three neighbors that are alive then it’s alive on the next round
How do we encode this game in Scratch? There’s a few tricks we’re going to use.
The first important concept is that each cell is going to be represented by a Scratch sprite. Specifically, by a clone of a generic cell sprite. This, in my opinion, makes it a lot easier to handle the user interface by letting you click on cells to turn them on or off individually.
You might be wondering “if each cell is a separate clone how do we figure out what each of their neighbors is doing so we can run the simulation?”. I wondered this myself for awhile! After all, Scratch doesn’t give you a way to send a message to just one clone. I decided to have a two-part way of representing the board.
The cloned cells are the first part of the representation and they handle the user-interface and displaying the state of the simulation. The second part of the representation, the board itself, is actually a list! Each item in the list is a row of the board. Each row of the board is a string of 0s and 1s, with 0 meaning the cell is dead and 1 meaning that the cell is alive. We link the two by giving each cloned cell “this sprite only” variables keeping track of what row and column in the board they represent!
This is a pretty common trick in a lot of programming languages: you fake having a 2d thing like a board by using a 1d thing like a list but putting some extra structure in each element of the list. In some languages you would make a list-of-lists but that’s not easy in Scratch, so instead we use strings as the content of each row.
(If you’re wondering why it’s not easy to have lists-of-lists in Scratch, it’s not impossible but you’d have to make all the row-lists by hand before starting the program. Since we actually want to allow for different sizes of boards, this is super awkward and inconvenient. You could try doing it that way, though, and see if it makes the code simpler!)
Using lists-of-strings means that we need to write some custom blocks that allow us to treat a string like a list. These are the Modify string and Modify string2 blocks! There are two of them to prevent name overlaps between the one on the Backdrop and the one on the Cell sprite.
Now, the final trick we need is that we actually need two boards: the “real” one and the “working” one. The reason we need two boards is that when we’re calculating the new state of each cell we need to keep the original board intact, not change it as we’re working. An example is in order! Let’s take a blinker as an example:
Let’s assume that we’re just modifying the same board as we go. Then after the row above the blinker is finished the board will look like:
The problem, though, is that now the left cell in the blinker has two neighbors which means it sticks around instead of disappearing! The same ends up being true of the right cell in the blinker so by the time the next step in the simulation is done you’ve got:
Instead of:
That’s not good!
So in our custom block Update space, which does the real work of enacting the rules of the Game of Life, we read the state of the list variable called Board and write the result of the calculation to the list variable called TempBoard. At the very end, after we’ve calculated the state of every cell on the board we copy the temporary board back to the real board.
At that point we broadcast a message to tell all of the cell clones to update their internal state and costume based on the state of the board!
I really liked making this little program, in part because it’s not the kind of thing people usually make in Scratch! I think it makes a nice demonstration, though, of the kinds of “serious” programs that Scratch is good at!
So I encourage you to mess around with the code, try playing with the rules of the Game of Life, or even just try to recreate the code yourself in your own way!
Learn More
Game of Life in Scratch
https://scratch.mit.edu/projects/235622299/
Game of Life in TIC-80
http://clarissalittler.github.io/GameOfLife.tic.html
A Turing machine in the Game of Life
http://www.rendell-attic.org/gol/tm.htm
Game of Life useful links
http://www.radicaleye.com/lifepage/
http://www.radicaleye.com/lifepage/
Stack Overflow thread about Rule 110, the 1D Turing complete automata
John Conway explains game of life
https://www.youtube.com/watch?v=E8kUJL04ELA