Digging digital dungeons

Simple roguelike levels via BSP trees

If there's one thing that defines roguelikes to everyone, it's procedural generation of levels. No, it doesn't make for a different game every time; in fact they're all kind of same-y. It does mean one can't rely on memorizing moves to play: even a roguelike's creator can't speedrun through their own game.

It also means levels in a roguelike need to be programmed, not just designed in a map editor.

All right, that's not all true. There are roguelikes that pick from a list of premade levels, only placing enemies and items at random. Even with levels generated at runtime, there are many ways to do it, from piecing together prefabs and all the way to simulating geological processes. There's no shame in picking a method that works well for you.

Note, procedural isn't the same as random! Rolling dice plays a role, but you try plopping down walls wherever on an empty map and see if you like the result. (Carving rooms at random out of a map covered in wall tiles works a little better. Still not enough.)

This article documents a simplified use of BSP trees to make roguelike levels. BSP stands for Binary Space Partitioning: a way to divide the level in two, then divide each piece again, and so on until they're neither too big nor too small.

Figure 1: repeatedly subdividing a map to form rooms.

It may seem plain, but with a few tweaks BSP can yield a variety of layouts, even within the same game. And in this form, they all look like buildings that were modified again and again until their turned into mazes: a little bit of much-needed verisimilitude in a game genre that's often surreal and abstract.

Building the partitions

Sorry for the long introduction. This tutorial exists because the similar one on RogueBasin doesn't explain how to actually do it, instead pointing at a couple of video tutorials. So let's jump straight into the code. Hope you don't mind Python:


#!/usr/bin/env python3

import random

map_width = 30
map_height = 20

min_width = 4
stop_width = min_width * 2 + 1

random.seed(42) # Traditional value for fixed layouts.

# Levels are stored by line: y is always the first index.
level = [['.' for x in range(map_width)] for y in range(map_height)]
# Add walls all around the level to begin with.
for y in range(map_height):
	level[y][0] = '#'
	level[y][map_width - 1] = '#'
	for x in range(map_width):
		level[0][x] = '#'
		level[map_height - 1][x] = '#'

def subdivide(x1, y1, x2, y2):
	w = x2 - x1 + 1
	h = y2 - y1 + 1
	
	if w >= h and w >= stop_width:
		subdivide_width(x1, y1, x2, y2)
	elif h >= stop_width:
		subdivide_height(x1, y1, x2, y2)

def subdivide_width(x1, y1, x2, y2):
	x = random.randint(x1 + min_width, x2 - min_width)

	for y in range(y1, y2 + 1):
		level[y][x] = '#'

	subdivide(x1, y1, x - 1, y2)
	subdivide(x + 1, y1, x2, y2)

def subdivide_height(x1, y1, x2, y2):
	y = random.randint(y1 + min_width, y2 - min_width)

	for x in range(x1, x2 + 1):
		level[y][x] = '#'

	subdivide(x1, y1, x2, y - 1)
	subdivide(x1, y + 1, x2, y2)

# Subdivide the space *inside* the exterior wall, leaving it out.
subdivide(1, 1, map_width - 2, map_height - 2)

for i in level:
	print("".join(i))

Oops, sorry about that, it's a whole page's worth of code. It would be hard to make it much shorter. But look what a beauty it makes:

Figure 2: BSP trees generate plausible floor plans.

(Okay, so the generator outputs ASCII art. It has to be filtered through another script to get the actual images.)

Rather than explain how the generator works step by step, let's look at some important design decisions:

But first, you must let the player move between rooms. And that means...

Adding doorways

As suggested above, breaking walls is a lot easier than building them in the first place. Sure enough, this is the simplest part. In fact you could probably go over the map and remove one in ten wall pieces at random. It might even work well for a ruined structure.

There's a better method however: after you finish subdividing, simply poke a hole in each partition. How? Add this code to subdivide_width:


	doory = random.randint(y1 + 1, y2 - 1)
	level[doory][x] = '.'
	# Account for walls placed deeper into recursion.
	level[doory][x - 1] = '.'
	level[doory][x + 1] = '.'

and this to subdivide_height:


	doorx = random.randint(x1 + 1, x2 - 1)
	level[y][doorx] = '.'
	# Account for walls placed deeper into recursion.
	level[y - 1][doorx] = '.'
	level[y + 1][doorx] = '.'

Ready? Let's give the modified script a try.

Figure 3: There's a guaranteed path between all rooms.

Glorious! Only now there are even more details to discuss:

(As an aside, note the offsets ensuring that doors have at least a support beam on either side, if not a good stretch of wall. This of course assumes a minimum width of at least 3.)

At this point, many roguelikes add monsters and items and let you play, not bothering with other details. Makes for boring levels to look at, and limits tactical options. To spice things up, let's add a thing or two.

Furnishing the dungeon

So what goes into a dungeon, other than walls? Why, columns for one. They're easy to draw, and an obvious choice. Pools of water are also easy to draw, and can have a gameplay purpose as well. Other options include statues, braziers, and the ever-popular altars. Question is how to arrange all that stuff. Let's try a few variations:

Figure 4: Different ways to furnish a 7x7 room.

These can be stored as data and copy-pasted in the right places, while to lay down columns along a corridor you'll need specialized code. Either way, it involves changing the subdivide function as follows:


def subdivide(x1, y1, x2, y2):
	w = x2 - x1 + 1
	h = y2 - y1 + 1
	
	if w >= h and w >= stop_width:
		subdivide_width(x1, y1, x2, y2)
	elif h >= stop_width:
		subdivide_height(x1, y1, x2, y2)
	else:
		furnish_room(x1, y1, x2, y2)

and of course adding the definition of furnish_room:


def furnish_room(x1, y1, x2, y2):
	w = x2 - x1 + 1
	h = y2 - y1 + 1
	
	if w == 4 or h == 4:
		for y in range(y1 + 1, y2):
			for x in range(x1 + 1, x2):
				level[y][x] = '*'
	elif w % 2 == 1:
		for x in range(x1 + 1, x2, 2):
			level[y1 + 1][x] = '+'
			level[y2 - 1][x] = '+'
		if h >= 8:
			furnish_room(x1, y1 + 2, x2, y2 - 2)
	elif h % 2 == 1:
		for y in range(y1 + 1, y2, 2):
			level[y][x1 + 1] = '+'
			level[y][x2 - 1] = '+'
		if w >= 8:
			furnish_room(x1 + 2, y1, x2 - 2, y2)

It's a bit simplistic, to keep an already long script from growing longer, but the results aren't bad:

Figure 5: A few simple rules can cover all cases.

Note the recursive calls, that create rooms within rooms in a way, allowing for combinations not explicitly anticipated. In fact the code wasn't even supposed to furnish every single room! You might want to leave a few empty for contrast.

Refinements like this are best left as an exercise for the reader, however.

Conclusion

Roguelikes are notoriously repetitive. It would help if it took multiple playthroughs to see all the content, but they're also often long. And it's hard to keep coming up with variations on the same theme when they're all there as filler from the start. Multiple environments make a difference, but when each of them has to be coded anew, it becomes a burden.

This form of BSP tree generator alleviates the problem. Levels with noticeably different moods can be generated from the same code simply by tweaking a few parameters. There's room for set-piece encounters, too. And as it happens, the resulting levels are always fully playable, offering all kinds of tactical situations. Use with confidence, and thank you for reading.