This ended up being way more verbose than I intended. If you just want to read the "what" of the procgen used, scroll down to the TL;DR at the bottom.

Background:

I've had a lot of people (2) ask me recently if I could talk about the algorithm used for the procedural generation of the caves in my game. I've also had a few people commend me for using procedural generation for a 2 week jam game, which at first I thought a little odd, because I didn't think I was doing anything particularly noteworthy, just trying to get as much content out of my game as I could.

I've always found the hand crafting of game levels/worlds to be a much more challenging and creatively taxing process, requiring a lot of thought, effort and knowledge of game design principles. I turn to procedural generation as a way to automate that process, as a kind of programmers hack to avoid actually creative design, and so I've done a lot of self-driven study on the subject (read: binged youtube). I am by no means an expert in any field, let alone procedural generation, but I suppose by now I do have a little experience and perhaps I've forgotten that not everyone has the same experiences that I have.

Before this jam started, I had been working on a shmup game with procedurally generated waves of enemies, and I had probably gone deeper down the rabbit hole than I ever had, reading a lot of game development blogs, design documents, listening to GDC conferences, etc. about the topic. I may not have internalised it quite yet, but I have learned that procedural generation isn't some shortcut hack to make a game develop itself for you.

To have content of a game procedurally generated well, you need to have a deep understanding of the game design aspects of what you're trying to generate, and turn them into algorithmic instructions, a set of rules that define the content. To use shmups as an example, you have to understand what makes good combat in those kinds of games, how many enemies there should be, how they should move, how they should interact with each other and the player, when they should spawn in and how, when they should leave and more. Every little component that ultimately defines the gameplay, usually a sequence of events defined by the game designer(s), have to be categorized and conditions for their use have to be defined.

Defining a game this way will usually reveal many variables that can be used as "switches and dials" to fine tune the output, and I find this way of designing a game very appealing. It's about creating a system, a machine that takes an input, transforms it, and spits out an output, and you can change the settings from the outside by playing around with the settings, and there's something very intuitive about this approach for me, it's how I interreact with most technology.

None of this is anything new. Really I'm just regurgitating the words of much more clever, productive people than I, but it does set the scene for the approach I took to this game. The idea being that you boil a game design down to a set of basic rules, and the way these rules interreact with each other produced increasingly more complex behaviour as they are layered on top of each other.  This is a really longwinded introduction for what is, in my opinion, the fairly simple process I used to generate the caves in Caves of Goo.

Step 1: What do I want? 

I spent over a day thinking about what I was going to do with the theme of "It's Spreading", and when I decided on a goo that spreads that has to be cleaned up, I then needed an environment for that goo to spread throughout. In my never ending search for as much bang for my buck, I settled on caves. I figured they'd be pretty easy to generate in top down, 2D game. It occurs to me now as I write this that I was heavily inspired by a recent week long playthrough of Necesse, which has a bunch of top down, 2D caves.

 I was going for twin-stick shooter, I wanted arenas for shootin' at bad guys in. Somewhat open spaces for freedom of movement, with bits and pieces of cover. I wanted the edges of the cave to be irregular and jagged, to fit the theme of being a cave, but also to give it a little bit of that "It's Spreading" look.  I wanted there to be several of these caverns (I called them rooms in the code) as kind of hubs for the combat that come in different sizes. I wanted them spread apart so the player had a sense of moving cavern to cavern, to add some ebb and flow to the gameplay, but also to make sure there were no isolated, inaccessible areas. These tunnels (paths in code) should also fit the visual theme of a cave, not just go in straight lines but meander. 

Step 2: Building a room.

I had a couple of different attempts at this, but they were scrapped early, unfit for purpose. What I came up with suited my needs enough, though in future I would definitely like to revisit this. 

A room is defined as an array of vector positions and is to be filled with positions up to a certain predefined size. It starts with a 3x3 grid of vectors, (0,0) at the centre and the 8 surrounding points being relative to it, (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0, -1), (1,-1). I used no clever mathematical way of doing this, just a hardcoded array. The order of each position is irrelevant, I just went counterclockwise, starting to the right for conventions sake. The 8 outside positions are also added in another array, one for tracking the borders of the room.

A random vector from the border array is randomly selected, and it's neighbours in the four cardinal directions are checked to see if they are not already part of the room. One of these valid neighbour positions is randomly selected and added to the room array. If there was only one valid neighbour, then that would mean that the currently selected position will no longer be a border position, and is removed from the border array. The newly added child is also checked to see if it has at least one free neighbouring position, and if so, it is added to the array of border positions. Rather than using all 8 directions around a position, the cardinal directions are used in this process to make sure positions are not added to the room in a diagonal, which could leave unconnected spaces in a room.

This step is repeated until the desired amount of positions have been added to the room array. The results are rooms that initially tend to cluster around the centre, but as the borders expand the shape gets more erratic. Due to the random nature and statistics of the the selection process, it also allows for the slight tendril patterns to emerge around the room, and also creates pillars and walls within the room. This works well enough for my purposes, but it does start to become too noisy at larger sizes, and in future I think messing around with the distribution of random selection might help produce more cohesive shapes, but still keep some irregularity.

Step 3: Placing the room.

Now we have an array of positions it can be placed in the larger world that is a level. To do this, a random angle and a random distance are chosen and trigonometry is used to define a random point within a circle. The size of the circle can be limited by limiting the maximum distance that can be chosen. This random point is added to all the positions in the room array and we have now placed a room. At this point, we repeat Step 2 and Step 3 until we have the desired amount of rooms.

Due to the random nature of placing rooms, there will be times when rooms overlap. I wanted to allow this, so that it would create larger "super rooms", adding greater variability in the size of the rooms, whilst clearing out more open space, avoiding the noisiness that would occur if we just generated larger rooms in the first place. However, if a lot of rooms overlapped, this would reduce the total size of the map in terms of how many tiles there are. To overcome this, as the rooms are placed in the world, each tile is checked to see if it's already part of a room and if not, it is counted towards a total. A desired total of tiles in a map is defined as the desired amount of rooms multiplied by the predefined size of the rooms. 

The process of building rooms repeats until enough unique tiles are placed to reach that desired total. When the amount of tiles left until the total is reached is less than the predefined size of the rooms, then the next room built will only be of a size large enough to reach that total, but no less than the initial 9 tiles. This allows for even more variability in the size of the rooms, but may exceed the original total desired map size by 8 tiles, which was not a problem for me. 

Step 4: Minimum Spanning Tree

Now that I have the rooms scattered about I need to make sure the player can reach all of them. I turned to google here to see if something like this has been done before, and of course it has. I found this article here this article here at gamedeveloper.com, which itself is referencing this reddit post by the developer of Tiny Keep. It details the process they used to generate their dungeons, and within that process I found exactly what I needed, something called a minimum spanning tree (mst). This is a concept from graph theory, defined (in my words) as the shortest route that passes though each node of a graph. 

To find the mst I would have to compile the rooms as the nodes in a graph data structure all connected together by edges. Godot doesn't have a built in graph data structure so I would have to define my own, using something called Delaunay triangulation (I'll come back to this) to connect the nodes. At least I would have if I didn't find this tutorial here by kidscancode.org. It turns out, there is an A* object in Godot that can function as a graph data structure suitable for our purposes.

Very little modification to the tutorial was needed to implement it into the map generation so far. One by one each node (room centre) is added to the A* object, and connected to the closest point to it already there, using something called Primm's Algorithm. Once all the rooms have been joined I return the connections as an array of vector pairs, basically defining which nodes are connected together (edges), and with the array of room centres (nodes) I had my own basic graph data structure. 

I'm very grateful to both the dev of Tiny Keep, and Kids Can Code, for saving me hours, even weeks of research.

Step 5: Culled Delaunay Triangulation

If I simply joined the rooms together just using the mst, it would be fit for purpose, however, the dev of Tiny Keep also used a technique to introduce some non-linearity. When they were building their graph structure they used Delaunay triangulation, which connects all nodes in a graph with non-overlapping triangles. They would then use this graph to find their mst, and then reintroduce some of the original edges, creating alternative routes throughout the graph, without being overwhelming.

After a few minutes of research about Delaunay triangulation I found that Godot has a built in method for this, making things very easy for me. The method takes an array of nodes as inputs and outputs an array of vectors, every three vectors defining a triangle. It didn't take much to convert this array into a series of vector pairs, to match the format I was already using for my mst edges, then randomly culling edges to create the desired effect.

The Tiny Keep dev mentions they kept about 15% of the edges from the triangulation in their map generation. For my map generation I kept two thirds, allowing for more looping pathways, however I did not consolidate the mst and the triangulation before this culling, as I didn't want to accidentally cull the edges in such a way as to create inaccessible rooms. What I could have done was remove any edges in the triangulation that match the mst first, and then cull random edges more aggressively. I would have to experiment with the difference, but as it stands I quite like the results of how I'm doing it currently.

Step 6: Weighted Random Walker

Now that we've determined which rooms will be connected together, all that's left to do now is to actually connect them. To do this I used something similar to a random walker. Normally a random walker is something used in procedural generation in which you pick a random direction, move a step in that direction and repeat. This can create random, wriggling, looping paths, but it could take quite a long time, or possible forever, to reach a desired point.

The solution I came up with was to start at the centre of a room, go through each cardinal neighbour of that point and assign it a weight based on how close it would be towards the end point. This allows the direction the walker moves to be chosen with weighted random distribution. 

The result is a meandering path that tends towards the goal, but not completely limited to it. The four cardinals are again used here to avoid diagonals making inaccessible paths. The actual paths are a clearing out of a 2x2 section of tiles around the walker (0,0), (1,0), (1,1), (0,1), to make the paths wider and more navigable. 

All of this together creates and array of positions that is easily plugged into Godot's tilemap node. Godot 4.1 has horrible autotiling however, so I used the Better Terrain plugin and with some set up of tilesets, collision and navigation masks, I had an endless amount of caves for goo to spread throughout.

Conclusion:

The animations on this page are from the debug mode of the generation, which I used to visualise changes and chase down any bugs. The actual generation is very fast, near instant. Applying it to the tilemap is where the majority of the time is spent. It's not bulletproof though, if there simply isn't enough space within the defined radius of spawning for the amount of rooms desired then it will hang.

Overall, I am very happy with the result, and enjoyed myself immensely researching and building it, and I look forward to further refining and building upon it. However, I'm not sure if it saved me any time whatsoever. In the same time I suppose I could have constructed 10 or so varied, interesting levels for the player to go through, with perhaps some more variety in the enemies encountered. While technically you could play through endless caves, it now becomes a question of why would you want to? This is a very important question when it comes to procedural generation.

TL;DR

Step 1: Build random, irregular shaped room.

Step 2: Place room, repeat step 1 and 2 as necessary.

Step 3: Connect rooms with a minimum spanning tree.

Step 4: Add extra edges using Delaunay triangulation.

Step 5: Combine mst and edges

Step 6: Use weighted distribution + random walker to connect rooms with irregular tunnels