Grandma’s Game of Life (Grandma’s GOL) is the implementation of Conway’s Game of Life described in this post. Conway’s GOL is named after the British mathematician John Horton Conway who created it in 1970 after being inspired by John von Neumann‘s work on hardware organisms. John von Neumann defined “life” as being or organism that could reproduce itself and simulate a Turning Machine, Conway’s GOL grew to be the best known and most widely implemented cellular automata. Cellular automata are studied in computer science, physics, biology, biochemistry, economics, mathematics, philosophy and generative sciences.
In the video above, the pattern of cells is called a Glider, which is a famous pattern because it actually appears to moves on the board as the rules are applied from generation to generation. The Glider is the smallest of the spaceship patterns. When game rules are applied to the pattern of cells on the left below in the figure below, the pattern on the right is generated. Read on to understand how this works.
Conway’s Game of Life is a simple idea from which marvelously complex “living” patterns can emerge. Although, invented with serious intent, Conway’s GOL, has become a pastime, if not an addiction, for many. After Conway’s GOL was described in the October 1970 issue of Scientific American in Martin Gardner’s Mathematical Games column, computer scientists and mathematicians the world over became devotees, I among them. Many of us rushed to program Conway’s GOL in whatever programming language we had access to at the time. I remember printing reams of paper, in the absence of a CRT, from a FORTRAN program so that I could watch “living” patterns, which might emerge, move across the board, stabilize, oscillate and die. There was a rush to discover patterns with certain characteristics. Conway’s Game of Life has lost none of its popularityr. Today, there are databases of GOL patterns catalogued by their various characteristics.
In this game there are no players. The game is played on a board such as those shown above. Each square on the board is called a cell. Each cell can be alive (blue) or dead (white) , which is also referred to as on and off. The game has rules, which are applied to a board configuration to create the next generation. The rules are applied again and again to create successive patterns.
Each cell has eight neighbors, which includes the four diagonal cells as well as the cells above, below, left and right. A cell at the edge of the board has neighbors on the opposite side of the board. This makes the board wrap on both up/down and right/left sides so that all cells have eight neighbors. The wrap-around board is implemented here; however, another common, simpler implementation is to have cells at the edges have only 5 neighbors because thy have no wrap-around neighbors.
The rules for Conway’s Game of Life are simple. For a live cell to remain alive in the next generation it must have exactly 2 or 3 neighbors. In other words, if a live cell as fewer than 2 neighbors (underpopulation) or more than 3 neighbors (overpopulation) it is dead in the next generation. If a dead cell has exactly 3 live neighbors, it will be alive in the next generation. These rules are so simple that they can easily, albeit tediously, be applied by hand. You do it — I’ll use my computer.
To start a game, choose a board size and enter a pattern of living cells. Apply the rules to generation after generation. With some patterns, all the cells will die within a few generation. With other patterns, the living cell configurations may oscillate, repeat after several generations or repeat while moving on the board. There are even patterns that never change no matter how many time the rules are applied.
Wikipedia and LifeWiki provides good overviews and history of Conway’s Game of Life as well as examples of patterns from the more than 1,000 that have been studied. LifeWiki presents more than 1,000 patterns with running simulations of many.
Grandma’s Game of Life has 24 patterns built-in that you can explore by just typing the pattern name as a command. For example, pulsar is another well-known GOL pattern. It does not move, but repeats after 3 generations as you can see in the video below.
How to Operate Grandma’s Game of Life
The two tables below list the commands available in Grandma’s Game of Life.
|pattern title||There is a command for each pattern in the pattern list. (see next table)|
|pattern num1||Runs pattern number num1 from the pattern list|
|patterns num1||Runs all patterns starting with pattern 0 from the pattern list. num1 is the number of cycles (generations) each pattern can run If the stop command will cause the command to terminate with the current pattern.|
|new||Creates a new board with each side containing the number of blocks specified by the current size. This command can be used to create a new board for entering player specified on/off cells.|
|size num1||Sets the number of blocks per side of the board to num1, default 10.|
|random num1||Creates a new board then initializes num1 percent of the total cells to be alive (on). For example, if num1=50, half of the cells would be alive.|
|edit||Enables the player to edit the current board by changed the on/off value of cells. When the player has finished editing the board, the enter command is required.|
|enter||Completes editing by entering the on/off values for the edited board.|
|go||After a pattern has been entered, the go command starts the generation cycles. The program will cycle through generations until the limit is reached, there is no change in the board or the player stops or pauses execution.|
|1||Performs one cycle and pauses. Repeated 1 commands enable the player to study how a new generation is derived from the preceding by applying the GOL rules.|
|pause||Pauses after the current generation is completed. The game can be restarted with either a go or 1 command. During a pause, the board can be edited.|
|stop||Stops after the current generation is completed. After a stop, the game cannot be restarted.|
|limit num1||Changes the cycle (generation) limit to num1. If no parameter, defaults to 3000.|
|wait num1||Changes the number of seconds for the pause between each generation. If no parameter, defaults to 0.|
|out||Says the position coordinates of each on cell in the current board. The command is invalid if the game is running.|
|on-chat command||on-chat command||on-chat command||on-chat command|
|O spaceship||figure 8||H spaceship||blocker|
The video below shows 20 generations each of the above patterns.
The Code that Grew and Grew
Halloween is an appropriate time for feature creep. This code grew to be the largest MakeCode program that I have written. I’m not proud of it. I succumbed to my usual problem — the creepiest of feature creep. Feature creep is a common problem in software development. After the program is defined, someone thinks of “just one more feature.” Then, just one more feature. And so on. Some programs are cursed with such bad cases of feature creep that they are never released Fortunately, I am releasing Grandma’s Game of Life today no matter how big it is. But, I am planning a smaller version for release soon. Trouble is — just which features am I willing to give up?
An implementation of Conway’s Game of Life needs to do the following:
- Generate the board.
- Enter patterns on the board.
- Apply the rules from one generation to the next, making needed changes to the cells.
Two challenges proved particularly difficult;
- Including a pattern library in one of the standard formats. I chose Run-Length Encoding, (RLE).
- Fast application of the GOL rules to generate a new generation.
I wanted to use Run Length Encoding (RLE) standard format for the pattern library. This would enable me to copy/past patterns from LifeWiki. In the code below, the entries in the list RLE_patterns list where obtained that way. The patterns are arranged in order of complexity with simpler patterns first.
Each RLE pattern specifies the layout of on/off cells that constitute the pattern .The task was to translate the RLE pattern into Minecraft positions of on/off cells on the GOL board. This is a job for a parser. I’ve been writing parsers for more years than I like to admit. This one was challenging because MakeCode has very limited string (text) functionality.
Fast Rule Application
GOL simulators (like this one) can be very slow unless some cleverness is employed. Most of the slowness is caused by the fact that to apply the rules, the number of living neighbors for each cell must be counted. In this implementation, updating the blocks for a new generation was also slow. The algorithms I explored included the following:
- Using the Minecraft blocks to store the on/off information. If A block is blue, it is on. By cycling through the grid of blocks, I could test each neighbor to count it thus determining how many neighbors each cell had and whether it would be alive or dead in the next generation. Very, very slow. Testing Minecraft blocks in MakeCode is much too slow to use this method.
- Next I tried using a 1-D array to simulate a 2-D array of Boolean values that represented the alive/dead state of each cell. But, again ALL cells would need to be cycled through to calculate neighbors, then assign values for the next generation, then place the blocks in the board to match the result. In this method, the program spent too much time testing array values that could never be alive in the next generation because they had no living neighbors. That made me think of the final method.
- After a few refinements, I found the following method. I used two lists, not arrays; that is, the lists only contained cells on the board that could change in the next generation, not the entire 2-D array. The lists are:
- GOL_on_cells_list — This list contains all the cells that are alive in the current generation. The companion list — GOL_on_cells_list_prior — is the list of all cells that were on in the prior generation.
- GOL_changed_cells_list — This list contains the Minecraft world positions (relative to origin) for the cells that will change in the next generation. The MakeCode X and Z coordinates are the row and column, respectively, in the GOL board grid. The Y coordinate is 0 if a cell is the be turned off and 1 if it is to be turned on.
I will explain how this works in a later post, but for now it is left as a exercise for the student. The code is shown below in three sections. The first is pattern processing. The second is the main parts of the program. The third is the string library.
This code assumes a flat world such as that described in MakeCode for Minecraft Sandbox World: Make It Flat and Simple.
Smaller Code Coming Soon
Depending on the power of your computer, this code may be difficult to work with; however, it should run, albeit slowly.
Get the Code
Grandma’s Game of Life code is shared on Code Connection at this URL
To get and use the code, follow these steps.
Click the Import button , which is upper right in the Code Connection window just below the banner. This will open the window shown below.
Click the Import URL button , which is on the right, to open the window shown below.
Paste the URL supplied for the program you want to use in the space under the text “Copy the URL …”
Click the Go ahead! button .
The next window you will see will be the MakeCode window with the code downloaded from the URL. At this point, you can treat it like any other code, e.g., run it, save it locally, modify it, publish your changes or whatever else your heat desires.
We have tested several other methods of downloading the code using the URL, for example, pasting the URL in a browser. No joy. For more detailed instruction see our post How to Use Shared MakeCode on Microsoft Code Connection for Minecraft.