Hello everyone.

In one of my previous devblogs, where I talked about the new demo version, I mentioned that I had reworked the dungeon map generation. Now I want to take a closer look at this particular change: how a new sector is created, from a few connected nodes to an actual playable map. Procedural map generation seems like a very simple task until you actually sit down, start generating maps, and get a few terrible results. You can simply create a rectangle and fill it with rooms and walls, place enemies, passages, and chests. In principle, that is already the simplest kind of procedural level. Technically, the map will always be new and random.

The problems start a little later. When you realize that you have almost no control over how such a map is created, and that a random map is not necessarily a good map.

That is exactly what I ran into when I wrote the first version of the map generator. The biggest problem was that I ended up with a rectangle made of rooms, with passages to areas above and below, but there was never any real route through it. The player was simply placed inside these rooms and wandered through the available tiles. Sometimes, after clearing 80% of the labyrinth, the player would reach the last room and then have to walk all the way back toward the starting point through the entire labyrinth just to find the correct passage. And in IRSEN, where every extra step increases the character’s Corruption and brings more Mutations, this became very annoying.

I needed my dungeon to always have a beginning and an end. And between these two points there had to be a main route leading from start to finish. Besides the main path, I also wanted additional random areas that the player could explore if they wanted to. This solved the main problems: the player never has to return all the way to the starting point, while still always having the option to leave the main route and explore additional areas.

Graphs and Nodes

So I decided to turn to graph theory and start generating the map without actually starting with the map at all. I split the generation process into several stages.

First, I defined several node types that could be used to build the logical structure of a sector. Then, once this logical structure existed, I could describe the physical structure of the map on top of it. Each logical node eventually represents a physical room. As a result, instead of just getting a random rectangle with walls, I now had a set of rooms where each room had its own purpose.

I created four types of nodes in the graph:

• START - the beginning of the sector.

• MAIN - rooms along the main route.

• BRANCH - optional side branches.

• FINISH - the final point.

The simplest version could look like this:

START - MAIN - MAIN - MAIN - FINISH

This is the main route that the player can always follow from the beginning of the sector to its end. Additional branches are then attached to it. For example, one MAIN node can lead to a separate BRANCH room, while another branch may consist of two or more consecutive nodes.

At this stage, there are no actual rooms yet. The generator knows only one thing: which parts of the level must be connected to each other. For debugging, I print the final graphs directly into the log. For example, one generated graph looks like this:

Here you can immediately see the main route: START - M01 - M02 - M03 - FINISH
And two additional branches: M01 - B07 and M03 - B05 - B06

This is still not a map. It only answers the questions of which area can be reached from which other area, and where the beginning and the end of the player’s route are located. This separation turned out to be the most important part for me. Previously, the route logic and the physical implementation were too tightly connected. Now the generator first defines the traversal logic, and only after that tries to turn it into physical space.

Placing the Graph on the Map

The next stage is a layer of slots. Now every generated node needs to find a physical location. For the same generation, the debug output looks like this:

In this case, the graph was placed on a 3 × 5 grid. START ended up at the top center. The next MAIN room is down and to the left. The main route then shifts right again, returns to the left, and finally ends at FINISH. Meanwhile, the BRANCH nodes occupy free positions next to the rooms they are connected to.

From a Scheme to a Dungeon

Once the structure and placement are defined, the abstract nodes can be turned into actual areas of the game world.

Rooms, passages, and connections between them appear. The generator already knows which areas must be connected, so the geometry is built around a predefined route rather than the other way around. This is a pretty important difference. If MAIN[01] is connected to MAIN[02], then the final level must preserve that connection regardless of which slots those rooms ended up occupying.

As a result, I can work with different parts of the generator separately. I can change the number of MAIN nodes or the rules for creating BRANCH paths without changing the basic principle of placing the graph on the map. Or change the rules for creating BRANCH paths without changing the way objects are placed. I can experiment with layers and slots without affecting the rules used to build the main route.

In one of the next devblogs, I will talk separately about the next part of generation: how rooms and branches are filled with enemies, chests, and other objects - and why their placement also depends on the structure of the graph.