Creating a Roguelike with C++ And BearLibTerminal Part 2: Procedural Dungeon Generation

mgcadmin 05-01-2022

Where we left off...

When we last left off we had the basics of our game engine in and character classes in place. In this section we will be covering basic Procedural Dungeon Generation.

In part one we laid the foundation for our Map class, but now its time to actually do something with it. After all, walking around a rectangle with no features wouldn't exactly make for an entertaining time. Seeing as Roguelike cames are traditionally Dungeon crawls, we will be implementing a simple dungeon generating algorithm.

If you haven't completed part one yet, go back and do that, as the foundational code for the map class was covered there.

Procedural Dungeon Generation

There are many different algorithms for creating many different styles of dungeons. Roguebasin is a great resources for a general over view of many of them. The algorithm i'm going to cover here will create a "basic" dungeon in the spirit of Nethack. That is, it will create randomly sized, randomly placed "rooms" and then connect them tunnels.

The map, tile, and rectangle class's are the same as we used in part one, but we will be adding some methods to the map class, Here is the constructors for those types:

The algorithm used to generate the rooms looks something like this:

Starting with a grid(2D Array) of blocking tiles the size of our Dungeon:

1)Generate an rectangle of between min room size and max room size.

• If this is the first rectangle generated, save it in an array of rectangles.
• If it is not the first Rectangle, iterate over the array of rectangles and see if it overlaps any of the previously generated rectangles, if it collides with any of them, throw this rectangle out and generate a new one, If it does not collide, save this rectangle in the array.
• repeat this step untill we have generated the number of non-overlapping rectangles we want, these rectangles will be the rooms of our dungeon.

2) Iterate over the array of rectangles, and set the tiles within this rectangle to non blocking.

At this point we have generated the Rooms of the dungeon, and the next step will be to connect them via tunnels.

Without being connected by tunnels, our map with rooms looks like this:

The code for generating rooms, clearing rectangular areas of tiles, and checking if two rectangles overlap is as follows:

The next step is to connect the rooms.

Heres the plan:

Iterate through the array of rectangles from 0 to N - 1; 

Room A is 'i', Room B is 'i' + 1,

For each pair of rooms: Determine if room A is higher or lower on the Y axis than Room B and determine where on the X axis Room B is in Relation to Room A. We need to do this so we know which direction to start drawing the tunnels from.

Find an intersecting point where tunnels will meet by having one going horizontally and one going vertically. starting from the mid point of each room, draw these tunnels until they intersect.

Once we've done this for each pair of rooms, we will have a fully connected dungeon like this:

If you want you can tweak the parameters for the tunnels to change the branching factor/direction, Or you could run it twice to create even more interconnection, I'm just using this as a starting point for you if you choose to use this style of dungeon generation.

The tunneling code:

And thats about it for Procedurally Generated Dungeons for now. In the next Section, We'll start creating Goblins to fight our player!

The full working code for the project up to this point is available on my github at:

https://github.com/bottomupmergesort/RogueLikeTutorial/tree/main/Part2-ProcecuralDungeons

---