Using 3D cellular automata to create unique procedural island shapes
Over the last two weeks, I decided to work on something new. I had a little idea for a relaxing game about decorating procedural islands. This blog post is the result of that work as I developed my own 3D cellular automata system that generates unique island shapes for use in my game. In this blog, I will go over how my system works and the process of overcoming performance issues when building it. I implemented this using GDScript in the Godot game engine, but the concepts can be used in any 3D engine or framework.
So what is procedural generation and how can we use cellular automata to generate things? Procedural generation is simply generating content using code or maths, as opposed to manually creating assets by hand. Anything can be procedural, terrain, assets, animations, and so on. Cellular automata is a model of computation based around a grid of cells that hold values. The cells can change over many iterations based on the values they hold and the values held on their neighboring cells. This can be very useful for creating unique and interesting patterns and shapes or in my case 3D islands.
Some interesting patterns and shapes created using 2D cellular automata.
The theory
Ok, so I want to create a cellular automata system in 3D that will consistently create unique blobby island shapes. Let’s get into it.
At a base level, the process is quite simple. First, we create a grid. We can loop through a vector of our desired size and initialize each value to zero.
Then we can randomize our grid, setting each value to either alive or dead at based on a random chance that can be altered for different results.
Then, for each iteration, we need to loop through our grid, and for each cell, check how many neighbors it has. If it is above a certain amount of neighbors we can make sure the cell is alive, if not, we can kill the cell. Finally, we can ‘draw’ the grid, by placing blocks in the relevant places. This can be done just once at the end, but I decided to do this every iteration as the effect of seeing the island take shape is pretty interesting.
Optimisations
Nice, so that’s nice and simple conceptually but after my first implementation, I was running into some performance issues. We are attempting to loop through 15625 blocks multiple times each iteration, doing many checks, looking up values in arrays, and spawning and deleting blocks in the 3D scene each loop. We can optimize this a bit.
The first thing to optimize was the count_alive_neighbors function. Initially, I was looping through the entire grid and checking if it was both a neighbor of the current block and alive each time I wanted to count the neighbors. I changed this so that the code stored an array of each of the 26 directions. We can then just loop through each of the directions from the block’s position and check if each one is alive or not.
The next optimization is a big one. The draw grid function initially would loop through each value in the grid and depending on whether it needed to have a block spawned or not, it would spawn the block and append it to an array that had references to all the blocks in the scene. This was very slow as the program had to frequently check through the entire array of blocks to see if a block existed or not. To optimize this, I replaced the blocks array with a dictionary. So instead of iterating through the blocks array each time we wanted to check if a block exists, delete a block or create a block, we can just check the block dictionary to quickly check if a block exists or not. When creating a block we can just add the block and position to the dictionary, and when removing a block we can simply find it in the dictionary and remove it from the scene. This meant the time complexity of looking up a block went from O(n) to O(1). This single change alone increased the speed of drawing the grid from around 30-40 seconds to just 2-3 seconds.
Tweaking
Now I have a system for creating 3D cellular automata islands that are relatively efficient. I just need to tweak it to provide the results I want. Luckily, we can change a bunch of different values in my algorithm to get different results. For example, changing the spawn chance can alter how large the blobs of the island are. Changing the number of iterations alters how smooth each island is. Changing the number of neighbors required will change how fast each island erodes down.
Conclusion
I hope this blog post was helpful if you are wanting to implement your own 3D cellular automata system. If you want to see the full project files for my implementation, please see the following repository.
I have expanded on my 3D cellular automata system in my small game Campscape. In the game, you can generate islands and modify and decorate them as you like. The game is playable and can be downloaded from my itch page here.