Welcome to my personal blog

This article is translated and reproduced with permission from @a327ex. Link 1: GitHub, link 2: GameDeveloper

This article explains a technique for generating random dungeons, first described here by TinyKeepDev. I’ll cover it in more detail than the steps in the original post. The implementation process of this algorithm is as follows:

Generate the room

First, you need to generate a random number of rooms with a certain width and height within a circle. TKdev’s algorithm controls the size of the room through positive distribution, which I think is a good idea because it can be controlled with more parameters. Different looking dungeons can be generated by controlling aspect ratios and standard variances.

One method you might need is getRandomPointInCircle

function getRandomPointInCircle(radius)
  local t = 2*math.pi*math.random(a)local u = math.random() +math.random(a)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
Copy the code

You can find information about how this code works here. This way you can do the following:

One thing you need to consider is that since you are (at least in your mind) dealing with a grid, you need to align everything on the grid. In the GIF above, the block size is 4 pixels, which means that all the rooms are in positions and sizes that are multiples of 4. To do this, we handle the width/height allocation through a passing function that handles the fact that the size of the graph block has reached the unity of the whole:

function roundm(n, m)
  return math.floor(((n + m - 1)/m))*m
end

-- Now we can change the returned value from getRandomPointInCircle to:
function getRandomPointInCircle(radius).return roundm(radius*r*math.cos(t), tile_size), roundm(radius*r*math.sin(t), tile_size)
end
Copy the code

Separate room

Now we are going to move into the separate rooms, many of which should not be overlapping and mixed together in one place as they are. TKdev uses the separation steering Behavior to do this, but I find it much easier to just use the physics engine. After adding all the rooms, add the physics engine to each room, and then run the simulation and all rooms go back to sleep. In the GIF, we run and simulate normally, but when you do this between your levels, you can use faster and easier methods.

We didn’t bind the physics to the grid, but when setting up room locations, you can wrap them around roundm so that you get rooms that don’t overlap each other and also have a video grid. This is shown in the GIF below, where the blue outline is the position that the physics engine got because they rounded the position so that there was always a mismatch between them and the house.

One problem that can occur if your room is mostly horizontal or vertical, as IN the game I’m developing:

Since the battle is horizontal, I expect most of the rooms to be wider than they are tall. The question then becomes how does the physics engine solve collisions when long rooms overlap:

As you can see, the dungeon gets very tall, which is not ideal. To solve this problem, we initially generated rooms in an ellipse instead of a circle. This will ensure that the dungeon has a proper aspect ratio locally:

To generate randomly within this region, we can change the getRandomPointInCircle function so that it can be generated within an ellipse (in the GIF above, we used Ellipse_width = 400 and Ellipse_height = 20).

function getRandomPointInEllipse(ellipse_width, ellipse_height)
  local t = 2*math.pi*math.random(a)local u = math.random() +math.random(a)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
Copy the code

The main room

The next step is to determine which rooms are the main/central rooms and which are not. The approach TKdev uses is very reliable: you only need rooms that are above a certain threshold in width and height. In the GIF below, I used 1.25*mean, which means that if width_mean and height_mean are 24, then rooms greater than 30 in width and height will be selected.

Delaunay trigonometric segmentation + graph

Now we will select the power in all rooms and put it into the Delaunay process. You can do this yourself, or find code that someone else has done and shared. I was lucky Yonaba finished it. As you can see from this page, it accepts points and outputs triangles:

Once you have the triangle, you can generate the shape. If you have a structure/library of graphical data at hand, this process should be simple. If you haven’t already done so, can you make your Room object/structure have unique ids so you can add those ids to the graph instead of copying them around?

Minimum spanning tree

After that, we generate a minimum spanning tree from the graph. Again, either implement it yourself, or find someone else to do it.

The minimum spanning tree ensures that all the main rooms in the dungeon are reachable, but it also makes them less connected than before. This is useful because by default we don’t want all dungeons connected to each other, and we also don’t want islands that are unreachable. However, a dungeon with only one route is not what we want either, so what we need to do is add a few edges from the Delaunay.

Add more paths and loops here to make the dungeon more interesting. TKdev adds back 15% of the path, and I find that greater than 8-10% is a better value. Of course, this value will vary depending on how connected your dungeon is.

The corridor

For the last part, we’ll add corridors for the dungeon. To do this we need to traverse each node in the graph and then connect it directly to the other nodes. If the nodes are close enough horizontally (their Y positions are similar), we create a horizontal line. If the nodes are close enough vertically, we create a vertical line. If the nodes are not close together horizontally or vertically, then we create two lines to form an L shape.

The tests I use are close enough, which means that calculating the position of the two nodes should check whether the x or Y property of the midpoint is within the boundary of the node. If so, we create the line from the midpoint position. If not, create two lines, from the midpoint of the source to the midpoint of the target, but only on one axis.

In the figure above, you can see examples of all the cases. There is a horizontal line between nodes 62 and 47 and a vertical line between nodes 60 and 125. Nodes 118 and 119 are l-shaped. It is also important to note that these are not the only lines I have created, it is the only line I have drawn, but I have also created 2 additional lines on the sides of each line first, tile_size as spacing, because I want my corridor to be at least 3 units wide in width or height.

Anyway, after that we need to check which rooms are not the main/center and are in direct conflict with the lines. Then add the collision rooms to the structure you now contain this information, which will serve as the skeleton of the corridor:

Depending on the uniformity and size of the room you initially set up, you’ll see different dungeon looks here. If you want your hallway to be more uniform and look less strange, then you should aim to reduce deviations and you should do some checks to prevent the room from being too thin in a certain way.

For the last step, we need to add a standard size grid to fill in the missing parts. Note that you don’t really need the grid’s data structure or anything too fancy, you just need to traverse each row according to the size of the block and add the grid’s rounded corner position (which corresponds to 1 size cell) to some list. This is in 3(or more) rows instead of just one.

And now we’re done! 🌀

The last

The data structures I return from the entire process are: a list of rooms (each room has a unique ID, x/ Y position and height/width results); Graph, where each node points to a room ID, with the edge having the smallest unit of room distance; Then there is an actual 2D grid where each cell can be empty (meaning it is empty), can point to the main/central room, can point to the corridor room or corridor unit. With these three results, I think you can activate any kind of data you want from the data, and then you can identify where to place doors, enemies, items, which rooms have bosses, etc.