As mentioned in the initial blog post, I researched cellular automata when choosing the algorithm for the project. It's a computing architecture popularised in 1970 by Conway's "Game of Life" which I decided to program my own implementation for in Unity using C#.
The video below shows the implementation, it's basis is like the Wave Function Collapse algorithm (using a 2D grid of cells). This implementation begins with a random 30% of cells to be "alive". Another feature added is being able to restart on a keypress. then across the grid applying the classic rules of the game based on the cells:
If a cell is alive, it must have 2 or 3 alive neighbours or it dies
If a cell is dead, if it has 3 alive neighbours it becomes alive
In the video above, the red cells are "alive" whereas the black cells are "dead". Unlike Wave Function Collapse, there's no propagation within Cellular Automata, the entire grid changes each timestep. Each time the project is ran with the same seed, the outcomes are the same, which is in my post on pseudo random number generation.
The reason the rules are set up in this way is that, at the time, the algorithm was for biological research. And it's main idea was to see how unpredictable and interesting cell automation could be. In the actual version, the user could place the cells themselves and have more control over how fast the simulation is going. Which is something I may expand the program to do in the future, since creating known shapes which oscillate is something I may want to do.
Found on GIPHY illustration one of the structures within the Game Of Life which oscillates, specifically this is called a "Glider Gun" since it fires a pattern which moves out.
For the research I looked into several white papers, both to learn what it is and what it is used for. Due to how long ago Cellular Automata was created and how popular it became, the papers included many applications for it. On top of that many different rulesets, ways of picking rules and combinations with other algorithms. The white papers I looked at are referenced at the bottom, and if you're more interested I would recommend taking a look through them.
The applications across the papers include:
Image processing
Traffic Management which does include people
Replicating Digital Sound Data
Creating designs for dense residential buildings
Maze and level/map generation
Irreducible Semi-Autonomous Adaptive Combat Agents simulations (Combat Simulations)
Adding surface detail to 3D Models with voxel detail
I learnt that in 2D grids, there are many types of "Neighbourhoods" and the one used in Game of Life is a "Moore" neighbourhood. It's the 8 cells surrounding a cell at a distance of 1. Whereas there's another type called the "von Neumann" where each step away has to be horizontal or vertical.
 |  |
Moore Neighbourhood | von Neumann Neighbourhood |
Both images are from the user "Torchiest" on the Wikipedia page for Cellular Automata, there other other neighbourhoods within general graph theory but they're not generally used for Cellular Automata.
Since it's my first time delving into the topic, it took some time to understand a few of the papers, and I'm not sure if I even do! There's an incredible amount of depth in how much potential is in Cellular Automata. Recently, each cell can be seen as more as if they are small finite state machines, with a potential to change based on an environment. This allows them to reach more goals and the data from them is now combined with other algorithms like Evolutionary Algorithms as discussed in "Procedural maze level generation with evolutionary cellular automata".
However, understanding general graph theory will help when it comes to the City Generation project. Next post will probably be about the theory of Wave Function Collapse and will be the first post more closely looking at the ongoing city generation project.
Here are the references of the white papers I looked over during research:
Adams, C. and Louis, S., Procedural maze level generation with evolutionary cellular automata, 2017 IEEE Symposium Series on Computational Intelligence (SSCI), 2017, pp. 1-8, doi: 10.1109/SSCI.2017.8285213.
Johnson, L., Yannakakis, G. and Togelius, J., 2010. Cellular automata for real-time generation of infinite cave levels. Proceedings of the 2010 Workshop on Procedural Content Generation in Games - PCGames '10,.
Keane, T., 2011. Partial Differential Equations versus Cellular Automata for Modeling Combat. The Journal of Defense Modeling and Simulation: Applications, Methodology, Technology, 8(4), pp.191-204.
Khalili Araghi, S. and Stouffs, R., 2015. Exploring cellular automata for high density residential building form generation. Automation in Construction, 49, pp.152-162.
Knospe, W., Santen, L., Schadschneider, A. and Schreckenberg, M., 1999. Disorder effects in cellular automata for two-lane traffic. Physica A: Statistical Mechanics and its Applications, 265(3-4), pp.614-633.
Mazzolini, R., 2016. Procedurally generating surface detail for 3D models using voxel-based cellular automata. Master of Science. University Of Cape Town.
Rosin, P., 2006. Training cellular automata for image processing. IEEE Transactions on Image Processing, 15(7), pp.2076-2087.
Wada, M., Kuroiwa, J. and Nara, S., 2002. Completely reproducible description of digital sound data with cellular automata. Physics Letters A, 306(2-3), pp.110-115.
Xiao, X., Shao, S., Ding, Y., Huang, Z., Chen, X. and Chou, K., 2005. Using cellular automata to generate image representation for biological sequences. Amino Acids, 28(1), pp.29-35.
Comments