These three Cornell students created a sandbox for interacting with Conway’s Game of Life to explore some of life’s deepest questions—and to have fun, of course.
The advent of artificial realities and their supporting technologies, Metaverse and Neuralink to name a few, leads to some interesting existential questions. If we can recreate reality in a virtual space, is it possible that we too live inside a generated simulation? Of course the validity of this question is quite suspect when looked at critically, but out of sheer interest we may consider a much smaller-scale example of this exact phenomenon. Turing Complete systems are systems that can be replicated inside of themselves, and the one we chose to explore was Conway’s Game of Life.
We created a sandbox for interacting with Conway’s Game of Life—a famous cellular automaton. The user configures the system via buttons, switches, and a graphic-user interface (GUI) running on a PC. These configurations are communicated to a PIC32 microcontroller, on which all of the automaton logic is implemented. The PIC32 communicates with a thin film transistor (TFT) display to visualize each generation. We built this system to explore our own interest in Conway’s Game of Life and its unpredictable nature. We explored the remarkable variety of patterns, structures, and logic elements that Conway’s Game of Life can generate, and used our sandbox to ponder the nature of our reality.
A simple set of rules govern Conway’s Game of Life. The automaton runs on an infinite grid of cells, each of which is either “dead” or “alive.” Each generation, a particular cell decides whether it should transition states based on the states of its eight nearest neighbors. In particular:
- Any live cell with two or three live neighbors survives.
- Any dead cell with three live neighbors becomes a live cell.
- All other live cells die in the next generation. Similarly, all other dead cells stay dead.
- Each generation is dependent of those preceding it.
Due to the simple nature of the game, structures that produce known outcomes exist. Some examples of such structures are:
- A blinker that is three live cells in a line, where each iteration the cells transition from vertical to horizontal or horizontal to vertical
- A glider gun that infinitely recurses, creating microstructures that travel in a single direction
- A galaxy that oscillates between expanding out chaotically and neatly receding
In our implementation, we represented the grid as a two-dimensional NxM array. The row and column index for an element in that array represents a particular cell’s location on the grid, and the value at that set of indices represents its state (dead or alive). Each generation the software iterates over each cell in the grid. Every cell has the basic rule set applied to it and copied over to the next generation’s grid. The algorithm was implemented using the C language. A slight discrepancy exists here as the real Game of Life exists on an infinite grid, however, in any implementation, setting boundaries is necessary due to the limited memory of the computer performing the calculations.
The user interacts with the Game of Life via a potentiometer and a Python GUI running on a separate computer. These components facilitate parameter modification for the current game instance. The Python GUI allows users to change the number of cells and the status of each cell, as well as placing premade structures that have interesting effects, such as a blinker or a glider gun. The user modifies the animation rate via a potentiometer connected to the PIC32’s analog-to-digital converter (ADC). More external components could be added to reduce dependency on the Python code, or the external components could be abandoned in favor of having all functionality moved to the GUI.
PLAYING THE GAME
Although the extent to which the Game of Life can be “played” is quite limited, our implementation has the ability to manipulate initial and boundary conditions of the environment. There are two ways a user can interact with the game. The first is a Python GUI which, as stated above, controls the initial state of the game.
THE PYTHON GUI SCREEN
Figure 1 is a screen capture of the GUI screen showing the types of interaction that the “player” can have in our implementation. Notable ones would be the Grid Size option, which changes the dimensions of the grid represented on the TFT; the Wrap option, which toggles a spherical “world” where all edges are connected; and the Grid button, which displays an interactive grid so as to allow the player to set initial cell states.
THE GRID INTERFACE
Figure 2 shows a blank grid in which all the cells are dead. The player can then press any individual cell to change its state to alive, or press again to revert to death. It is worth noting that when the Grid Window is opened on a live ecosystem, the current state pauses and that state is transferred to the open Grid Window. On the bottom there are some preset patterns for toggling multiple cells at the same time. Selecting any of them and then pressing a cell on the grid will populate the grid with said pattern.
Figure 3 shows a Galaxy pattern entered on the GUI grid and Figure 4 shows the resulting active Galaxies running on the TFT.
THE POTENTIOMETER AND ASSOCIATED CIRCUITRY
Interacting with the physical component of the project, namely the potentiometer, is much simpler than the GUI. Figure 5 shows the potentiometer and associated circuitry. The technical details will be explored later, but the important thing is that turning the dial shown in Figure 5 directly updates the rate at which a generation evolves to the next. This generational update speed is represented on the TFT as frames per second (FPS). At its minimum value the knob’s white pointer is pointing downward. FPS will increase when the pot is turned clockwise—maxing out at 31 FPS when at the 3 o’clock position.
TECHNOLOGY STACK OF THE PROJECT
As shown in Figure 6, the technology stack can be organized neatly into different layers. The user interaction layer at the top is where the user configures the game and the TFT display layer at the bottom is where the evolving generations are displayed. The C code running on the PIC MCU resides between these two layers—each element of the C code will be discussed in depth later. What’s notable is that each type of data has a specific path and that these paths are controlled by protothreads, henceforth referred to as threads. Therefore, adding either additional GUI elements or physical component functionality is easy. The Timer Thread handles all physical components and the Serial Control Thread handles all serial communication.
THE CIRCUIT DESIGN
We chose to implement both the physical and the software-based control inputs to the Game of Life simulator. These take the form of the Python GUI discussed above as well as a physical potentiometer. The Python GUI communicates with the PIC32 through a UART channel mediated by a USB-Serial bridge adapter.
The potentiometer controlling FPS connects to the PIC32 via three pins: the 3.3V supply, an ADC pin, and GND as shown in Figure 7. Rather than have a direct connection between the potentiometer and the PIC32, it was necessary to insert a low-pass filter between the two in order to remove noise above a frequency of 1kHz. We did this to achieve a stable and consistent reading from the potentiometer. To achieve a sampling frequency of 1kHz, resistance of 100kΩ and capacitance of 1nF were used, giving a cutoff frequency of 1.59kHz—above the desired limit but still functional. The potentiometer’s wiper terminal was fed to the RC filter, buffered by an MCP6242 op-amp. The filter components themselves can be seen in Figure 5 and the schematic shown in Figure 7. The MCP6242 buffer amplifier’s output was then directly connected to an ADC pin.
As discussed earlier, this project’s functionality revolves around the communication between the PIC32’s “C” code and the PC’s GUI, running in Python. First, let’s discuss the PC-based Python GUI.
The basic structure of the GUI’s main page, shown in Figure 1, is simple. It has a series of four interactive parameters that influence game state. Powering the GUI was the PySimpleGui module that tracks on-page button events—whenever a button or dropdown menu is pressed, that press is tracked via an “ID” specific to that element. By tracking these IDs, element-specific logic can be executed. The GUI also has a Grid Screen that displays and tracks a grid, the dimensions of which match that of the currently running game.
The buttons work as follows:
Grid Size: The left button seen in
Figure 1 opens a drop-down menu that allows you to select different X, Y dimensions for the game’s grid. The right button updates the grid size locally, as well as on the PIC32, via the serial (UART) link.
Wrap: This is a toggle button that enables/disables the Game of Life’s ability to wrap on the TFT display. This means that once a cell or cell structure is at the edge of the visible grid, the cells on the opposite side—both vertically and horizontally—will act as neighbors. This toggling is instantaneous (made over the serial connection) meaning that there is no need to pause the game while toggling the wrapping feature.
Grid: This opens the Grid Selection window for editing the initial or current state of the Game of Life. When opened, a message is sent via serial to the PIC32 informing the board to pause the current game state, and a simple sentence is returned to the GUI containing information about the locations of the currently alive cells. This information is parsed and displayed on the grid as the filled/unfilled state of each button. These buttons can also be selected manually (using the mouse) to toggle each cell’s alive/dead state. Figure 2 shows a Grid Window where every cell is dead. Referring to Figure 3 and Figure 4, once the desired environment is created, closing the Grid Window will send the current grid via the serial link to the PIC32—updating the TFT and resuming the game. Also included in the Grid window are a number of selection buttons, which allow for the placement of preset structures.
PIC32 “C “CODE
The “C” code implements the rules, calculations, and animation of Conway’s Game of Life. We used threading in this application with separate threads for the animation, timer, and each of the serial data streams. As shown in Figure 6, each thread communicates with the Game Thread by taking readings from external sources and changing global variables accordingly. The Game Thread accesses these variables.
Timer Thread: This thread configures the initial state of the grid, keeps track of the elapsed seconds since startup, and reads the ADC for potentiometer information. The ADC values were scaled up and a square root taken. This value was divided by 15 and used to represent the FPS rate. This made setting an exact FPS a bit easier.
Game Thread: This thread handles both the drawing of the cells onto the TFT and updates to the grid. This is where Conway’s Game of Life’s logic is implemented. Before calculations begin, we copy the current game array into the previous status array. The thread then loops through every cell in the previous status array, applies the rules, and updates each cell’s value in the current game array. The first step in this calculation is to check each of the surrounding cells and determine the number of them that are “alive” or “dead.” This is different depending upon whether wrapping is enabled or not—however calculations only change on edge cells when wrapping is enabled. With wrapping enabled, edge cells’ neighbors include those on the opposite side of the grid. When disabled, all cells outside the array are considered dead. Once the number of surrounding live cells is determined, we apply the game’s rules and update the cell’s state.
If the cell is currently alive and the number of surrounding live cells is not two or three, the cell dies. If the cell is dead and has three live cells around it, then the status updates to alive. These are the only cases where the cell’s state changes, so that is the only time that the cell must be redrawn. Figure 8 shows pseudocode, which determines whether a cell is dead or alive.
Displaying on the TFT screen involves dividing the current size of the grid by the TFT’s X, Y dimensions, thereby creating a definitive pixel size and a relative position for each cell. If a cell is alive, it’s colored in red, otherwise it is left blank (that is, black). Drawing is to be avoided as it’s a slow process, so we only redraw pixels that have changed between generations. Figure 9 shows the pseudocode implementing the drawing logic.
Each of the serial communication threads handles changes to global variables and arrays, based on messages received over the serial link. The GUI sends strings via the serial link, and based upon the content of each string different logic needs to be executed. As shown in Figure 6, any time serial communication is established the PT_Thread reads the first letter of the string and forwards the message to the appropriate serial thread: cells, buttons, or window. Additionally, any time data needs to be sent from the PIC32 to the GUI, the PT_Thread handles that logic.
The cell’s thread is initialized when the GUI’s grid window has been closed. The received string gives a list of indices of the alive cells, and this thread updates the internal array based on those live cells.
The buttons thread is initialized when either the LED or wrap buttons are pressed. This sentence contains information about the specific button pressed and the thread would either toggle the LED or toggle a global variable which tracks whether wrapping is enabled or not.
The window thread is initialized when the grid window is opened or closed. This pauses or unpauses the animation thread accordingly.
RESULTS AND CONCLUSION
Our objective was to try to eliminate as much variability as possible so that the game creates a consistent, repeatable simulation. Initially maintaining a steady framerate when using higher X, Y dimensions was a worry. However, that ended up being a non-issue. The calculations scale with the size of the grid, but they are independent of the state of the grid. Even at the largest grid dimensions (120×160) and the highest FPS speeds (30 FPS), which results in over 4.6 million array accesses, conditional checks, and cell re-draws per second, the TFT was still able to maintain the desired framerate. There was some latency when adjusting the FPS potentiometer however. When adjusting the knob, it would take approximately a second for visible frame rate changes to be seen. This was caused by the Timer Thread being set to run once per second—therefore not updating the ADC value until the next second’s iteration. Since it did not impact the accuracy of the simulation, we left it as-is.
While we were implementing two-way serial communication, there were some time issues with larger grid dimensions. If there were too many live cells the serial data stream would take too long sending them to the GUI—not all would be captured. This resulted in the GUI and display not matching up. Later, we adjusted the baud rate higher so that there was only a minimal delay needed to transmit and receive data, and the two-way connection was achieved without data drop-outs.
The only part of our simulation that is not perfectly consistent with repetition involved the potentiometer. The circuit is fairly sensitive and can be a little fickle when trying to reproduce a previously used speed. While the speed adjustment knob does require a relatively precise touch to get the desired timing, it does properly implement the square root scale. Originally we used a linear scale, but we switched it to make the FPS changes more gradual at the higher ADC values. Our game is very accurate and doesn’t have any glitches that we have been able to discover. Not only do the components communicate with each other quickly and accurately, but we have no visual glitches that detract from the user experience.
Due to the nature of the game, testing was all encompassing in its nature. For example, testing the logic of our implementation of the Game of Life involved testing the GUI’s proper setting and updating cell states.
Our design effectively met our expectations. We wanted to simulate Conway’s Game of Life using the PIC32 and display the game’s progression on the TFT screen. We also wanted to create a Python GUI that would allow users to configure the game as they desired. Ultimately, this goal was met. Our GUI allowed users to select any cell to be alive or dead, and included pre-made structures that users could place. Users could also pause the progression of the game and even make changes to an ongoing environment.
To expand on the project, one could take away some functionality from the GUI and build external circuits to handle the same functions. For example, rather than setting the wrapping inside the GUI, a simple push-button circuit could be added to achieve the same effect. The same is true for setting the grid dimensions. Similarly, a keypad accessory could be added to reduce the dependence on the PC GUI completely. Another interesting avenue would be the potential of going back in time to find previous game states, although this is a bit more difficult as reversing the game’s rules does not lead to a reverse in iteration. Some sort of backtracking algorithm would be necessary to implement this. Lastly, it is unfortunate that we were unable to implement a dimension large enough to showcase the true Turing Complete nature of the Game of Life. If you’re interested in what this would look like, there is a fascinating video (Figure 10). Although it is a shame that this existential possibility cannot be explored in our implementation, we’re pleased with the final result. Figure 11 is the QR code to the final project.
Microchip Technology | www.microchip.com
URL corresponding to QR code in Figure 10: https://www.youtube.com/watch?v=xP5-iIeKXE8
URL corresponding to QR code in Figure 11: https://www.youtube.com/watch?v=KZ1KyEwHKZY&list=PLDqMkB5cbBA7F_Rn8Jfj8CVBKGlAzMNA3
PUBLISHED IN CIRCUIT CELLAR MAGAZINE • OCTOBER 2022 #387 – Get a PDF of the issueSponsor this Article
Ian Kim Riley (email@example.com) is a Senior at Cornell University studying Electrical and Computer Engineering.
David Wolfers (firstname.lastname@example.org) is a Junior at Cornell University studying Computer Science.
Connor Thomas (email@example.com) is a Masters student at Cornell University studying Electrical and Computer Engineering.