As we all know, you can’t spell ‘roguelike’ without ‘procedural generation’ (try it). And what could be more iconic in procedurally generated content than dungeon layouts? In this article I want to share the current dungeon generation algorithm I use in Tombs of Telleran, a Godot C# implementation of Binary Space Partitioning (BSP). I will walk you through the algorithm in steps and explain how it works, but if you’re in a hurry to play with it, you can grab the Godot project from my GitHub. Ready for some trees, graph structures and beautiful recursion? Lets go!

Binary Space Partitioning

Before we get coding, let’s briefly talk about the BSP algorithm. BSP is a recursive tree based algorithm that lets us create rooms and corridors on a grid space in a way that guarantees that all parts are connected. This very useful property and its relative simplicity makes it a great choice for a base algorithm when generating dungeons for roguelike games. So how does it work? It builds a binary tree that divides the space into sub spaces by following these steps:

1. Start with the entire space as a single section

2. Recursively divide each section into two smaller sections by:

   1. Randomly choosing a horizontal or vertical direction
   2. Randomly choosing a position to split along that axis within valid bounds
   3. Creating two new child sections from the split
   4. Recurse into child sections until section size is below a threshold

3. Sample rooms within the leaf section

4. Create corridors to connect child nodes

5. Bonus: Create corridors to create loops to reduce player backtracking

Here is an example of running BSP where we reach the desired leaf section size in two splits.

You might suspect that the bulk of the work is constructing the tree based on the the description, but it turns out sampling corridors is the trickiest part, which we shall see later on.

Building the Tree

Let’s get coding and grow some trees! We will implement our tree as a recursive type called Bsp which we define as follows

public class Bsp(Area area)
{
    public readonly Area Area = area;
    private Room _room;
    private ICorridor _corridor;
    public Bsp Left;
    public Bsp Right;

	// rest of the class omitted for readability
}

Each Bsp has an Area, which is the part of the 2D world it covers, and two child Bsps (unless it is a leaf). It can also have a Room (if it is a leaf) and an ICorridor (if it is not a leaf, connecting its children). So how is a tree constructed? Let us look at the business end of the tree generation code. There will be calls to some helper functions which will be explained in comments to keep things concise. Remember that you can head over to the source code to dig deeper if you want more details.

Since C# is not a functional language is might be more natural to construct the tree using a stack instead of explicit recursion, so that is what we do here. I am a big fan of functional programming though, so the code does use the FunctionalExtenstions package to get access to the Maybe type. It basically lets us type check values that can be null by using the Maybe type instead of nullable values.

private Bsp BuildBsp(Area floorArea, int minPartitionSize, float splitNoise)
{
	var root = floorArea;
	var tree = new Bsp(root);
	var queue = new Stack<Bsp>();
	queue.Push(tree);
	
	while (queue.Count > 0)
	{
		var node = queue.Pop();
		
		// split the area into two sub areas returning a Maybe object
		// Execute only runs if the return value is not None
		// (a bit of weird formatting to fit comments)
		node.Area.Split(
			_randomService, // _randomService wraps a Random object in a Godot node
			minPartitionSize, // the smallest a partition/tree area can be
			splitNoise // controls how much the split can vary from a 50/50 split
			).Execute(split =>
		{
			node.Left = new Bsp(split.Item1);
			node.Right = new Bsp(split.Item2);

			// process children in random order
			if (_randomService.Next(1) == 0)
			{
				queue.Push(node.Left);
				queue.Push(node.Right);
			}
			else
			{
				queue.Push(node.Right);
				queue.Push(node.Left);
			}
		});
	}

	return tree;
}

The BuildBsp function will continue to add subtrees until the Area.Split starts returning None (because the minPartitionSize is reached), and then return the completed tree. Once we have the tree, we can move on to the next step: sampling rooms.

Sampling Rooms

To place rooms we traverse the tree to the leaf nodes (those without children, e.g. the final areas) and generate a single room inside each. In Tombs of Telleran I am using BSP to generate tombs (duh!) which I want to look human made. This means we want the rooms to be quadratic, which has the benefit of making our computations simple.

// Samples a random quadratic room inside `area`.
public Room Sample(Area area)
{
	var maxSizeX = area.Size.X - 2 * MinMargin;
	var maxSizeY = area.Size.Y - 2 * MinMargin;
	if (maxSizeX < MinSize || maxSizeY < MinSize)
	{
		GD.PrintErr("Could not create room!");
		return null;
	}

	var sizeX = _randomService.Next(MinSize, maxSizeX);
	var sizeY = _randomService.Next(MinSize, maxSizeY);
	var size = new Vector2I(sizeX, sizeY);

	var minX = area.XMin + MinMargin;
	var minY = area.YMin + MinMargin;
	var maxX = area.XMax - sizeX;
	var maxY = area.YMax - sizeY;

	var coord = new Vector2I(
		_randomService.Next(minX, maxX),
		_randomService.Next(minY, maxY)
	);
	
	var room  = new Room(coord, size);
	return room;
} 

That was easy! With that in place we can look into sampling corridors.

Placing Corridors

Corridor placement is arguably the trickiest part of the algorithm, which is probably why it is omitted in so many other tutorials. This is how we are going to go about it on a high level:

To place the corridors we traverse the tree starting from the smallest subtrees and work our way upwards. For each subtree we find the closest pair of rooms and connect those with a corridor. This is the part of the construction that guarantees that all rooms are reachable from all other rooms. This is a great property, but we pay the price of a time complexity of O(n²) when constructing it, as we will do pairwise comparisons. Since the dungeons I intend to create for Tombs of Telleran will be modestly sized this is fine, but if you are going to create dungeons with hundreds or thousands of rooms, this approach will not be ideal for you.

private static NodePair ClosestNodes(Bsp left, Bsp right)
{
	var initialSolution = new NodePair(left, right);
	return ClosestRoomsWorker(left, right, initialSolution);
}
    
private static NodePair ClosestRoomsWorker(Bsp left, Bsp right, NodePair bestSoFar)
{
	var newBestSoFar = MinDistance(bestSoFar, new NodePair(left, right));
	return (left.IsLeaf, right.IsLeaf) switch
	{
		(true, true) => newBestSoFar,

		(true, false) => MinDistance(
			ClosestRoomsWorker(left, right.Left, newBestSoFar),
			ClosestRoomsWorker(left, right.Right, newBestSoFar)
		),

		(false, true) => MinDistance(
			ClosestRoomsWorker(left.Left, right, newBestSoFar),
			ClosestRoomsWorker(left.Right, right, newBestSoFar)
		),

		(false, false) => new[]
		{
			ClosestRoomsWorker(left.Left, right.Left, newBestSoFar),
			ClosestRoomsWorker(left.Left, right.Right, newBestSoFar),
			ClosestRoomsWorker(left.Right, right.Left, newBestSoFar),
			ClosestRoomsWorker(left.Right, right.Right, newBestSoFar)
		}.Aggregate(bestSoFar, MinDistance)
	};
}

So, that part was computationally complex but not too bad conceptually. For this final bit we are going to get into the corridor placement weeds. First off, lets describe the strategy. The idea is to, given two rooms, try to connect them using a straight corridor (which will only be possible if they are overlapping horizontally or vertically), and if that fails connect them with a bent corridor.

public ICorridor New(Area fromArea, Area toArea, OverlapCounter overlapCounter) =>
    TryNewStraightCorridor(fromArea, toArea)
        .GetValueOrDefault(() =>
          CreateBentCorridor(fromArea, toArea, overlapCounter));

private Maybe<ICorridor> TryNewStraightCorridor(Area from, Area to)
{
    var overlaps = from.CardinalDirectionsOverlappingAreas(to);
    if (overlaps.IsEmpty) return Maybe<ICorridor>.None;

    // corridor construction omitted for brevity
    // var corridor = ...
    return corridor;
}

private ICorridor CreateBentCorridor(
		Area fromArea, Area toArea, OverlapCounter overlapCounter)
{
    var yThenXBendCorridor = NewCorridorWithBend(
				fromArea, toArea, CorridorBend.YThenX);
    var yThenXOverlaps = overlapCounter.CountOverlaps(yThenXBendCorridor);

    var xThenYBendCorridor = NewCorridorWithBend(
				fromArea, toArea, CorridorBend.XThenY);
    var xThenYOverlaps = overlapCounter.CountOverlaps(xThenYBendCorridor);

    // return the corridor with the bend with fewest overlaps
    return (yThenXOverlaps, xThenYOverlaps) switch
    {
        var (yThenX, xThenY) when yThenX < xThenY => yThenXBendCorridor,
        var (yThenX, xThenY) when yThenX > xThenY => xThenYBendCorridor,
        _ => _randomService.Next(1) == 0 ? yThenXBendCorridor : xThenYBendCorridor
    };
}

A bent corridor will always be able to connect any two points in a 2D worlds so this can never fail, but when placing it we need to choose “horizontal-then-vertical” orientation or a “vertical-then-horizontal” orientation.

Placing Loops

At this point our dungeon will look great. It will have a bunch of rooms and good looking corridors to connect them. But it probably requires quite a lot of backtracking for the player. This is a common problem, and indeed I am not the first to write about it. One way I’ve chosen to address this is to add loops to the map by identifying rooms that are close by in Manhattan distance but far away if you were to travel through corridors. This is one heuristic I found working alright, but I’m sure there are smarter ways to do it. Perhaps you know one you could share with me?

Wrap Up

And with that, the dungeon algorithm is complete! I hope you enjoyed the explanations and that the source code will help you with procedural generation, Godot and C#. Questions or comments? I’d love to discuss dungeon generation with you! So reach out on bluesky or shoot me an email at contact at stonesigil.com. If you want to receive more articles on traditional roguelikes, games programming in Godot, or my work on Tombs of Telleran, consider signing up to my mailing list below. Until next time!