Procedural generation of random game dungeons

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

Original description of the algorithm

1. First I ask the right 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 that are 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 (which are generated by the Math.random generator in most languages), I use the normal Park-Miller distribution . As a result, the probability of small rooms exceeding 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 now we have 150 random rooms located in a small space. Most of them run into each other. Now we are separating them using separation steering technology to separate the rectangles so that they do not intersect. As a result, they do not intersect, but are close enough to each other.

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

5. And then the main fun begins. We determine which of the cells of the lattice are rooms — these will be any cells with a width and height exceeding the given ones. Due to the distribution of 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 tie the rooms together. To do this, we construct a graph containing the centers of all rooms using the Delaunay triangulation . Now all the rooms are interconnected by disjoint lines.

7. Since we do not need all the rooms to be connected to all, we build a minimal spanning tree . The result is a graph in which it is guaranteed to reach any room.

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

9. To turn it into corridors, for each edge, a series of straight lines (in the form of G) are built, going along the edges of the graph connecting the rooms. Here we need those cells that were left unused (those that did not turn into rooms). All cells superimposed on the L-shaped lines become corridors. And due to the variety of cell sizes, the walls of the corridors will be uneven, which is just good for the dungeon.

And here is an example of the result !

Caution - there are a lot of monsters under the cutanimated gifs!

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

Room Creation

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

One of the features 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 tile grid, you will need to place all the rooms along one grid. In the above gif, the tiles have a size of 4 pixels, so all the positions and sizes of the rooms must be a multiple of 4. To do this, I wrapped the assignment of positions and height with width in functions that round 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

Sharing rooms

Let's move on to the separation. We got a lot of overlapping rooms that need to be divided. TKdev mentions separation steering technology, but it seems easier to use a physical engine. After creating a set of rooms, you just need to assign the physical bodies to each room, start the simulation, and wait until everything calms down. The gif presents an example of a simulation.



Physical bodies are not tied to our lattice, but by assigning positions to the rooms, we wrap them in roundm calls, resulting in rooms that do not overlap and are located on the lattice. The GIF presents this process. Blue outlines indicate physical bodies. There is a slight discrepancy between them and the actual positions of the rooms due to constant rounding.



One of the problems that may arise in this case may occur to you if you are specifically trying to extend the rooms mainly along one of the axes. Consider, for example, the game I'm working on:



Since battles take place horizontally, I need the rooms to be elongated in width rather than in height. The problem is how the physics engine will resolve collisions between two rooms.



In the picture we get the dungeon, elongated vertically, which is not very convenient. To correct 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 ratio of the height and width of the dungeon we need.



For random distribution of rooms in a strip, we change the getRandomPointInCircle function so that it places points in an ellipse rather than 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

Main rooms

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

Delaunay Triangulation and Count

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



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

Minimum spanning tree

After that we create the minimum spanning tree based on the graph. It ensures that all rooms are achievable in principle, while each room is not immediately connected to all the others.



After all, we don’t need both too many corridors and rooms that cannot be reached. But it will also be boring and the dungeon, in which there is only one right way - so we will return a few edges from the Count of Delaunay.



This will add more paths and give rise to a bit of enclosure. TKdev recommends returning 15% of the edges, but personally it seemed to me more convenient to return 8-10%.

Corridors

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

I performed this 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 level, I draw one line. If not, two, from a room to a point, and from a point to another room.



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

After that, we check which of the non-main rooms intersect with the constructed lines. These rooms are added to our structure and become the basis 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 lines, replacing the missing parts. It is here that the additional lines added earlier can be useful so that the corridors do not turn out to be too narrow.



That's it guys!



As a result, I get a data structure that has:

• 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 points to the id of the room, and the edges contain the distances between rooms in the cells
• 2D grid, in which each cell can be empty, point to the main room, point to a room belonging to the corridor system, or to a cell of a narrow corridor

These three structures can be used by you to represent any data set you need. On their basis, it is already possible to work with the location of doors, enemies, things, etc.