This week I started working on a new topic: the generation of dungeons and caves. I used space partitioning to generate rooms, labyrinth generation algorithms to generate corridors, and cellular automata to give the caves a more natural look.

Space splitting

There are many ways to generate dungeon rooms ( random placement , agent-based generation , using separation steering behavior or a physical engine , etc.). But my favorite method is to split the space, because it is easily controlled and expanded.

There are a lot of ways of dividing space: division into grids, binary dividing of space, dividing space by a tree of quadrants, Voronoi diagrams, etc. I decided to use a binary partition of space, because it is well suited for generating rectangular rooms. This method has gained popularity thanks to an article on RogueBasin.
')
The only complexity of this algorithm is the choice of separation position. If we do not impose a restriction on the separation position, we will get strange partitions of space:


There are several ways to avoid this behavior. One of them is to limit the separation position to two aspect ratios, for example, in the range from 30% to 70% or from 40% to 60%. Another way is to use normal or binomial instead of the uniform distribution, which will increase the likelihood of separation in the center of the side, and not along the edges. These methods fix the problem, but it is difficult to understand how exactly the parameters affect the final result.

Therefore, I used another method, the advantage of which is that it has one parameter and is easily understood: the maximum allowable ratio between the length and width of the cells. When sampling a new division, I first calculate the minimum and maximum values ​​that it can have so that the ratio for two new cells is less than the limit, and then I perform uniform sampling between these two boundaries. Here is the result when varying the maximum allowable ratio:


Good results are obtained with a maximum ratio of 2.0 to 3.0:

Room Generation

The next stage is the generation in each cell of the room. There are no particular problems here, I just set limits so that the rooms are not too small and are not too close to the cell walls.

Here are the results:

Rib selection

In binary dividing dungeon generators, the binary tree used in the dividing step is typically reused to generate corridors. I did not do this, because such an approach seems limiting to me.

Instead, at the stage of dividing the space, I build the structure of a doubly connected list of edges , which allows us to know which cells are located next to each other. This way I get the following graphs:


There are three advantages to this approach. First: if in the future I want to change the way of dividing the space, the rest of the generator will remain valid, because it receives only a half-edge data structure at the input. Second: now to select the edges that will become corridors, I can use any algorithm for generating mazes . Third: if I want to add loops to the dungeon, I can easily implement this.

For now, I just use the Kruskal algorithm and the distance of the city blocks to select the edges. Here are the results:

Corridor Generation

The next step is to generate the corridors from the selected edges. This is probably the trickiest part of the generator, because I need to be careful so that no corridor intersects with another.

Here are the results:

Cave Generation

The previous results were suitable for creating dungeons, crypts and other man-made structures, but I wanted to give the caves and mines a more natural look. The classic way to generate caves is to use a cellular automaton, as described in this RogueBasin article . The big problem with cellular automata is that their results are not completely controlled.

I decided to use cellular automata to create a natural appearance anyway, but to impose restrictions on them to get a controlled result. Instead of just two states: dead and living, I use four: absolutely dead, dead, alive, definitely alive. “Perfectly accurate” states cannot change in the process; they are used to limit the results.

The rooms and corridors generated in the previous steps are filled with “exactly alive” cells. That is, we still have supporting rooms and we guarantee that they will be connected to each other. The edges that have not been selected are filled with “exactly dead” cells so that no new paths appear between the rooms. Finally, around the rooms and corridors, we randomly make some cells alive. Here is the initial configuration:


Then we start the cellular automaton:



Here are some more sample results:


Later I will add a fill to remove unreachable parts.

This is the first step on a long journey to create an interesting dungeon generator. I am pleased with the results. I am especially proud of the constrained cellular automata method of creating controlled and natural caves. I also like the fact that each generation stage is separate from the rest and can be modified individually.

Delete isolated cells

Then I implemented a fill to remove inaccessible cells:

Multiple corridors between rooms

Experimenting with the parameters of the generator, I found that if you add a little noise between the connecting rooms, you get interesting results.

Here is the difference in results before applying noise to connecting rooms and immediately after, the parameter changes by only one unit:



If you make the rooms a little larger, the result will be even more interesting:


It's great that we have an accident and beautiful structures arise, but at the same time, the structure of the graph and the designations of the rooms are preserved, which will be useful:

Tile Generation for Caves

I spent almost all of my time generating tiles. It is not very difficult, but for the correct implementation it takes a little tricks.

Here are sample results:


The great thing is that you can very easily switch from a stone cave to a sand or ice:


The next steps in generating the dungeon will be the addition of scenery and monsters.