Roguelikes are defined by two key things: perma death and procgen. Permadeath is super simple to implement, but that’s not the case with procgen. There are thousands of ways, how you can implement it, and today we are going to look underhood of the Burning Knight engine (it’s called Lens, btw), and see what type of monsters live there.
Popular methods of generating a dungeon layout
Cellular automate
Source was not found, but the gif is too good
Cellular automate algorithms allow you to generate cave-like worlds with really little code.
You create a grid of "cells" (that are usually just booleans, because they have can be only dead or alive), and randomize it.
Then you do a few passes over the whole grid, applying some simple rules over it. In most cases, its all about calculating how many alive neighbor cells does a cell have, and deciding based on that should it live or die.
To be or not to be…
If you want to learn more about this method, I recommend reading this article.
BSP tree-based
The link above does a really great job on explaining, how this method works, but here is a small TL;DR:
- Start with one big node.
- Split it into two.
- Repeat step 2 with each of those nodes and the resulting nodes, until the resulting nodes are small enough.
- In each node, you create a room, that might be the same size as the node or a bit smaller.
- Connect all nodes together.
Isaac like
This type of layout is really popular between roguelikes these days, because of how simple it is to implement, and it kind of became standard at this point?
- Create a 2D grid.
- Select a random one to be the starting point and mark it with something on the grid.
- Select a random cell from the grid.
- If the cell has a room next to it, mark it as a room! Otherwise, repeat 3.
- Repeat 3. until you have enough rooms.
If you want a bit more details on this generator type, I would recommend reading this article.
Nuclear throne like
I thought I should include this method, even tho, it’s not used as much, but I just love what you can achieve with such a simple algorithm. The developers of Nuclear Throne once wrote an article on this topic, but sadly, now it’s gone 🙁
But… Thanks to the wayback machine, you still can read it! (and should!)
It uses a bunch of random walkers, that can spawn other random walkers as well as just empty spaces on the map. The only hard thing is to keep the walker count from jumping to infinite, but it’s pretty easy to figure out 😉
I even implemented it for java version of Burning Knight, here is a gist (it’s not bad, trust me).
How BK does it
So all those methods are cool and stuff, but they do not provide enough flexability. I’ve been playing a lot of Shattered Pixel Dungeon (and vanila Pixel Dungeon) lately, and I’ve been blown away by the dungeons this game is capable of generating. Both games are open source, so I dug up how the dungeon is built and used a lot of the concepts from SPD dungeon generator.
All starts with a list of rooms, that might vary depending on the area or the depth you are on right now.
A simple alg throws together a few regular rooms, sometimes a special room, maybe a shop, etc.
Then all that goes to a builder. Builders also vary depending on circustantium, but the most common one, is the ring builder.
Builders task is to place all rooms together on the map in such a way, so that they all are near each other, but do not collide.
Each room can tell the builder the min and max size, that it can be (just so the rooms fit on screen by the most part), what rooms it can connect to, how many doors it can have, where, etc, etc, etc.
The loop builder places them in this loop formation, with a few random branches:
Don’t mind the quality, the game is pixel perfect and zoom doesnt look good…
Also don’t mind the completely broken lighting and other fbos xD
Also, checkout those ImGui tools!
Popular methods of filling out the rooms
- Just empty. I think the name speaks for it self.
- Just place a few things with RNG. Usually with not too much detail.
- Handmade templates. A really common approach, dungeons start to feel same-y really fast, tho.
How BK does it
Now it’s painter turn. Again, the painter might vary on the area/depth, but the main tasks, that any painter performs, are:
- Place doors
- Paint every room
- Paint doors
By painting I mean the process of taking any data and
paintingdrawing it on the level
Doors are what connects everything together. It might seem like a strange idea to separate door placement and door painting, but a lot of
room algs use the door information for painting, but more on that in a minute.
So, the painter runs through all the rooms, look at the rooms that have doors and creates a tmp data structure, that holds
info about the future door, like its position and type.
Then it runs through all the rooms again, and that’s where cool stuff happens!
First, it paints the rooms floor. This doesn’t do anything for the gameplay, but comon, it looks pretty!
Each room might have its own alg for painting floors, but in most cases, it just picks a random one from a pool.
Here is an example of a floor painter alg:
public override void Paint(Level level, RoomDef room, Rect inside) {
if (Random.Chance()) {
Painter.Fill(level, inside, Tiles.RandomFloor());
inside = inside.Shrink(Random.Int(1, 3));
}
var a = Tiles.RandomFloor();
var b = Tiles.RandomNewFloor();
var start = Random.Float();
// Casted to float for division later on
var size = (float) Random.Int(1, 4);
for (int y = inside.Top; y < inside.Bottom; y++) {
for (int x = inside.Left; x < inside.Right; x++) {
Painter.Set(level, x, y, (int) ((int) (x / size)
+ (int) (y / size) + start) % 2 == 0 ? a : b);
}
}
}And here is what the result looks like:
It might not seem like too much variation, but it’s a rather simple one (I did not want to make a complex example), but don’t forget, that we have tons of floor algs!
Pretty much the same things happen with room walls after this. The only big difference is that the algs are more complex, and they actually generate unpassable objects.
Here is a simple wall painter:
public override void Paint(Level level, RoomDef room, Rect inside) {
inside = inside.Shrink(Math.Min(inside.GetWidth() / 2 - 1,
inside.GetWidth() / 4 + Random.Int(0, inside.GetWidth() / 2)));
Painter.Fill(level, inside, Tiles.Pick(Tile.Chasm, Tiles.RandomFillWall()));
if (Random.Chance()) {
var tile = Tiles.Pick(Tile.Chasm, Tiles.RandomNewWall(), Tile.Lava);
inside.Shrink(Random.Int(1, 3));
if (tile == Tile.Lava) {
Painter.Fill(level, inside, Tiles.RandomFloor());
}
Painter.Fill(level, inside, tile);
}
if (Random.Chance()) {
room.PaintTunnel(level, Tiles.RandomNewFloor(), room.GetCenterRect());
}
}And if we combine both things together, we get this:
Most of the cool ones were not ported yet, procgen wasn’t my main focus, but they will return soon!
After all of that, the painter generates some grass, water, dirt and cobweb everywhere, places flies and other decorative things.
Popular methods of spawning mobs
- Place a few mobs on free spots with RNG. Pretty easy to do, but feels not handmade.
- Place the mobs in the room layout. Looks nice, but the rooms become even more repeating.
How BK does it
For each room, painter generates a weight value. It might depend on the room type, but generally, it’s just room area divided by a constant plus a small random number.
Then I generate a pool for enemies, each room might have a different enemy pool or modify it on the go. Each mob has a certain spawn rate modifier, as well as a set of biomes in which it spawns.
Then from that big pool, painter selects a few, it might be even just one type in some rare cases. It does this so that the enemy layout doesn’t seem so chaotic.
Then it starts a loop, that continues until the weight value becomes 0:
- Select a mob type that’s weight value is under the weight value. Most mobs have it set to 1, harder ones have a larger one, etc.
- Depending on its placement type, place the mob near a wall, on a free spot, in a chasm, etc. The alg also makes sure not to spawn mobs too close to the door.
- Subtract the mob’s weight value from the total weight value.
But why use all those complex algs?
It is tempting to use simple algs for dungeon generation. They are fast, easy to understand, easy to implement and produce pretty cool looking results.
But, but, but. All those simple algs are pretty repetitive. After 5-10 runs, you will start noticing sameness, and after a few more the dungeon won’t hold any mysteries for you.
For me, this was a big problem with most of the modern roguelikes. So I took this hard path with Burning Knight, but I’m glad I did, because the results make me want to just go and explore the dungeons, and they keep generating all sorts of cool shapes and secrets, and I love them!
You might also find interesting
Join the discussion!
