2D Procedural Cave Generation

In late 2023, in the midst of a roguelike obsession, I decided to try and make a roguelike-style room generator. Inspired by the mines in Stardew Valley, I wanted to create a procedural cave system that a player could explore endlessly. This blog will describe the algorithm I came up with to achieve this goal.

The Algorithm

The Algorithm generates two components to construct a cave system: a list of Caves, and a list of Corridors. The steps of The Algorithm are as follows:

1. Generate caves
2. Offset caves (separation algorithm)
3. Generate corridors between caves

Generating Caves

To generate unique cave shapes, I used Godot's FastNoiseLite class to generate Value noise. To generate cave-like shapes in the noise, I set a threshold of 0.75 which splits the noise into two areas. If a point on the noise map is above the threshold, then it is considered a cave.

A random point is then found in a cave area. Using the Flood-Fill algorithm every point in this cave area can be found and added to a list. The coordinates are then centred around (0, 0) and any coordinate that protrudes from the shape is removed to help with drawing the cells on a TileMap. If these coordinates are within the allowed size limits set in the generator, they are then stored in a Cave object.

Offsetting Caves

After all the cave rooms are generated, they need to be offsetted in relation to each over. To do this, I adapted a method called 'separation steering', which is commonly used in flocking algorithms to keep flocks of agents separated. It works by repeatedly getting the vector direction between each pair of caves and moving them along these vectors in opposite directions until they are all separated by a given distance. This evenly spreads the caves out so they don't overlap and can connected by corridors in the next step.

Generating Corridors

To create the connections between caves, I first created an adjacency matrix to represent the possible corridors. Then, using Kruskall's algorithm, I generated a minimum-spanning tree between the graphs so they are all connected to each other by at least one path. Finally, to add variation to this graph, a few of the next smallest edges are added to the graph. Each corridor can then be generated using the edges of the graph. To get the coordinates for each corridor, straight lines are drawn from the centre of the caves to be connected until they meet.

Once all the coordinates of the system have been generated, they can be drawn to a TileMap for the player to explore!