Procedural generation of random gaming dungeons

In the post, the technique of generating random dungeons is considered in detail. The main generation algorithm, an example of which can be found here , is used by the developers of the game TinyKeep . The original post from the developer was posted on reddit .

The original description of the algorithm

1. First, I set the required number of rooms - for example, 150. Naturally, the number is arbitrary, and the larger it is, the more difficult the dungeon will be.
')
2. For each room, I create a rectangle with random widths and heights within a given radius. The radius does not matter much, although it is reasonable to assume that it should be proportional to the number of rooms.

Instead of evenly distributed random numbers (as generated by the Math.random generator in most languages), I use the normal Park-Miller distribution . As a result, the probability of small rooms exceeds the probability of large ones. Why this is necessary, I will explain later.

In addition, I check that the ratio of the length and width of the room is not too large. We do not need both perfectly square rooms and very elongated ones.

3. And here we have 150 random rooms located in a small space. Most of them run into each other. Now we carry out their separation according to the separation steering technology in order to separate the rectangles so that they do not overlap. As a result, they do not intersect, but are close enough to each other.

4. Fill the gaps with 1x1 cells. As a result, we get a square lattice from rooms of various sizes.

5. And here begins the main fun. We determine which of the lattice cells are rooms — these will be any cells with a width and height exceeding the given ones. Due to the distribution of the Park-Miller, we get a relatively small number of rooms, between which there is quite a lot of free space. But the remaining cells will also be useful to us.

6. The next step is to link the rooms together. To do this, we construct a graph containing the centers of all rooms using the Delaunay triangulation . Now all rooms are interconnected by non-intersecting lines.

7. Since we do not need all rooms to be connected to everyone, we build a minimum spanning tree . The result is a graph in which you can guaranteedly reach any room.

8. The tree turns out neat, but boring - no closed moves to you. Therefore, we randomly add back about 15% of the previously excluded edges of the graph. The result is a graph where all the rooms are guaranteed to be reachable, with several closed turns.

9. To turn it into corridors, for each edge, a series of straight lines (in the form of D) is built, running along the edges of the graph, connecting rooms. Here we come in handy those cells that remained unused (those that have not turned into rooms). All cells that overlap the L-shaped lines become corridors. And because of the variety of cell sizes, the walls of the corridors will be uneven, which is good for a dungeon.

And here is an example of the result !

Caution - under the cut many monsters of animated gifs!

In a post on Gamasutra, user A Adonaac took it upon himself to describe some details in more detail. In general, the operation of the algorithm is visually as follows:

Creating rooms

First, you need to create several rooms with a certain height and width, randomly located inside a given circle. The TKdev algorithm used the normal distribution for selecting room sizes, and it seems to me that this is a good idea - you have more parameters to play with. Different types of dungeons can be achieved by choosing different ratios of height to width and standard deviations.

One of the functions you might need is getRandomPointInCircle:

function getRandomPointInCircle(radius) local t = 2*math.pi*math.random() local u = math.random()+math.random() local r = nil if u > 1 then r = 2-u else r = u end return radius*r*math.cos(t), radius*r*math.sin(t) end 

Here her work is described in more detail . After that, you can get something like the following:



It is very important to note that since you are dealing with a grid of tiles, you will need to place all the rooms along one grid. In the above gif, tiles have a size of 4 pixels, so all positions and sizes of rooms should be a multiple of 4th. To do this, I wrapped the assignment of positions and heights with a width in the function, rounding the numbers to the size of the tile:

 function roundm(n, m) return math.floor(((n + m - 1)/m))*m end --      getRandomPointInCircle  : function getRandomPointInCircle(radius) ... return roundm(radius*r*math.cos(t), tile_size), roundm(radius*r*math.sin(t), tile_size) end 

We divide rooms

Let's move on to the separation. We got a lot of overlapping rooms that need to be divided. TKdev mentions the separation steering technology, but it seems to me more simple to use the physics engine. After creating a set of rooms, you just need to assign the physical bodies to each room, run the simulation, and wait until everything calms down. An example of a simulation is presented in the GIF.



Physical bodies are not attached to our lattice, but by assigning positions to rooms, we wrap them in roundm calls, resulting in rooms that do not overlap each other and are located on the lattice. This process is represented on the gif. Blue contours denote physical bodies. There is a slight discrepancy between them and the real positions of the rooms due to constant rounding.



You may encounter one of the problems that may arise if you specifically try to extend the rooms mainly along one of the axes. Consider, for example, the game I'm working on:



Since the battles take place horizontally, I need the rooms to be elongated in width, not height. The problem is how the physics engine will allow two rooms to collide with each other.



In the picture we have a dungeon, stretched vertically, which is not very convenient. To remedy the situation, you can initially set the location of the rooms so that they do not appear inside the circle, but inside a thin strip. As a result, we get the desired ratio of the height and width of the dungeon.



To randomly allocate rooms in the strip, let's change the getRandomPointInCircle function so that it places points in an ellipse, not a circle (in the presented gif I use the values ​​ellipse_width = 400 and ellipse_height = 20):

 function getRandomPointInEllipse(ellipse_width, ellipse_height) local t = 2*math.pi*math.random() local u = math.random()+math.random() local r = nil if u > 1 then r = 2-u else r = u end return roundm(ellipse_width*r*math.cos(t)/2, tile_size), roundm(ellipse_height*r*math.sin(t)/2, tile_size) end 

Basic rooms

In the next step, we define the rooms that will be the main ones. In the TKdev algorithm, everything is simple - select those rooms whose height and width exceed the specified values. On the next gif, I used the 1.25 * mean restriction - that is, if width_mean and height_mean are 24, then the main rooms will be rooms with a height and width greater than 30.

Delaunay triangulation and graph

Now we take the centers of the selected rooms and feed the data into the processing procedure. You can write it yourself or take it ready - I was lucky, and I found it ready, by Yonaba . It takes points and produces triangles.



Having obtained triangles, one can construct a graph. Hint: it is convenient to assign unique id to rooms, and work with them, rather than copying the room objects themselves.

Minimum spanning tree

After that we create a minimum spanning tree based on the graph. It ensures that all rooms are attainable in principle, and at the same time each room is not connected immediately to all the others.



After all, we don’t need both too many corridors and rooms that cannot be reached. But at the same time it will be boring and a dungeon, in which there is only one correct way - therefore we will return a few edges from the Delone graph.



This will add more paths and generate a bit of a closed circuit. TKdev recommends returning 15% of the ribs, but personally it seemed to me more convenient to return 8-10%.

Corridors

To add corridors, we go around all the nodes of the graph and create lines connecting it with all neighboring nodes. If the node is located approximately the same horizontally, create a horizontal line. If vertical - vertical. If the nodes are not located on the same horizontal or vertical, we create two lines that form an L-shaped form.

I carried out such a check, finding the midpoint between the positions of the two nodes, and checking whether the coordinates of this point are at room level (horizontal or vertical). If they are on a level, I draw one line. If not, two, from room to point, and from point to another room.



In this picture you can see examples of all cases. Nodes 62 and 47 are connected by a horizontal line, nodes 60 and 125 are vertical, nodes 118 and 119 are L-shaped. I note that in addition to the lines depicted in the picture, I create 2 additional lines drawn on each side, at a distance of tile_size, because I need corridors at least 3 cells wide.

After this, we check which of the non-main rooms intersect with the constructed lines. These rooms are added to our structure and become the backbone of the corridor system.



Depending on the uniformity and maximum size of the rooms, you can get very different dungeons as a result. If you want to get more uniform corridors, you need to limit the standard deviation and introduce more checks on the size of the rooms and the ratio of their height and width.

Finally, we add 1x1 cells to the cell lines, replacing the missing parts. It is here that the additional lines added earlier may be useful so that the corridors are not too narrow.



That's it guys!



As a result, I get a data structure in which there is:

• list of rooms (each of which is a structure with a unique id, x / y position, and height / width)
• a graph in which each node indicates the id of the room, and the edges contain the distances between the rooms in the cells
• A 2d grid in which each cell can be empty, indicate the main room, point to a room belonging to the corridor system, or a narrow corridor cell

You can use these three structures to represent any required data set. On their basis, it is already possible to work with the location of doors, enemies, things, etc.