Multi-State Automata
Sep 26 2024Arduino/ESP32 (C++)
Github: https://github.com/davidjihwan/Multi_State_Automata/tree/main
Ideation & Planning
The first thing that came to my mind after being handed an ESP32 TTGO was to try implementing some form of cellular automata. I could look at simulations of automata for hours, and with the standalone ESP32 having a relatively large display compared to its input and feedback systems, it seemed like the perfect application for this project.
The most popular, and one of my favorite, forms of cellular automata is Conway’s Game of Life. With the display being relatively tiny, however, I didn’t think I would be able to see the intricate details of the simulation. Instead, I was more drawn towards a variant called a multi-state automata, in which cells had more than the traditional alive or death states. I was inspired by this video by Erik Fransson, where he shows the complex and visually stunning behavior of multi-state automata systems. Watching some of the simulations, I decided that even if I was only able to play the simulation on a small scale, it would still create interesting patterns.
I made the design decision to update cells individually instead of updating the screen for every simulation step. I made this decision for two reasons: 1. I didn’t know how the computation power of the ESP32 compared to its ability to write to its display. I knew that the display refresh rate would probably be my bottleneck, but I wanted to make sure that in the case the computation was also a limiting factor, there would still be movement on the screen. 2. I wanted to take advantage of how human vision worked. Even though I was processing the simulation top-down, side to side (imagine a line sweeping across the board), if most of the pixels were unchanged, then it would be pretty difficult to tell tha tthe pixels were being updated in this sweeping manner and instead looks a lot more uniform.
Media
This effect becomes much more clear in the gif below. If you try hard enough, you can see the lines that sweep across the screen and update the pixels, but it isn’t too obvious.
(Cell size: 4px, Threshold: 2, Moore Neighborhood)
To keep things interesting, I also made the decision to start a new version of the simulation every 140 simulation steps, wiping the screen and starting with random values each time.
(Cell size: 4px, Threshold: 2, Moore Neighborhood)
Here are all of the configurations I tried that seemed to yield interesting results:
(Cell size: 4px, Threshold: 1, Moore Neighborhood)
(Cell size: 4px, Threshold: 2, Moore Neighborhood)
(Cell size: 2px, Threshold: 2, Moore Neighborhood)
(Cell size: 4px, Threshold: 3, Moore Neighborhood)
(Cell size: 2px, Threshold: 1, Neumann Neighborhood)
For the actual showcase, I decided on the configuration of (Cell size: 4px, Threshold: 2, Moore Neighborhood, Step limit: 200). I housed my ESP32 inside an envelope (that was also decorated in a fitting manner) and hung it from the ceiling of the Valegos Computational Center in Barnard College, as seen below.
Techical Details
I preferred using the Moore Neighborhood model, with a threshold of 2. In this configuration for each simulation step, if a cell has 2 or more “enemy” cells in its neighborhood, it is assimilated by the enemy cells and take on their state. As can be seen, this leads to incredibly interesting patterns, with the simulation stabilizing into stable spiral patterns over time. The threshold is the same as in Erik Fransson’s simulations, as it seems to be the configuration that produces the most visually interesting results.
If you take a deeper look at the code, you might notice that there are some workarounds I implemented both due to Arduino’s coding environment and my limited expertise. The simulation is typically run using a 2D matrix corresponding to how the cells are arranged on the screen. I wanted the dimensions of the matrix to be variable in order to test out different cell sizes. Instead of wrangling the compiler to accept a ‘variable dimensioned’ 2D matrix and worry about memory allocation, I opted to use fake matrices in the form of int* pointers (basically an array). I implemented a helper function, M_indexer, to index these arrays as I would a matrix. I also implemented the helper function as a functor in an attempt to optimize the code, but I don’t know enough about how the Arduino compiler works to know if the function code was unpacked as it would be in a standard C++ compiler.
The main code improvement that I would implement if I have the chance to tackle a similar project would be to change the way I am writing to the screen. Currently, the code is written in a manner that gives both the computation and screen-update ample room for bottlenecking, meaning that the simulation shouldn’t be too affected if one or the other was the limiting factor. However, I seem to have greatly underestimated how much faster the computation would be than the screen update. If there is an efficient manner to use buffers to “build” the image corresponding to the next simulation step and load those images every screen update (instead of just individual cells), it may be possible to run much larger simulations. However, more testing is needed on how the ESP32 writes to the screen and if the code for writing to it could be optimized to any degree for our purposes.