I have recently been making games in Godot. All kinds of different game genres. I want to play around and see what I like most. Developing games in Godot deserves an entire post or multiple to itself, but this post is about dungeons...

Everyone and their brother has a dungeon generator and there are already fancy algorithms which generate them for you.

But I wanted to learn how they work and wanted something custom. So I made one.

The dungeons for this particular game are quite simple. There are no complex mazes or paths in between rooms.

If you just want to play with the generator, just scroll to the bottom.

The Algorithm

The general algorithm for this is as follows:

• Generate a number of overlapping rectangles of different sizes (rooms)
• While a room overlaps another
  • Move that room one unit in a random direction
  • If moving the room causes an "island" to exist, reverse that movement

But what is an island?

For this algorithm, an island is simply a room which does not intersect another room. But there is an edge case...

If you count a corner to corner overlap as an intersection, that may cause issues in your game. So I added a check for a minimum overlap area.

Let's do better.

With the algorithm above, I was able to generate small 3-5 room dungeons in around 50-100 iterations of the algorithm. But when I tried big dungeons, like 16-24 rooms, it took over a 1000 iterations and multiple seconds to solve!

In order to make this more efficient, I thought about using a set room velocity instead of always picking a random direction. This worked wonders. I had similar results and much fewer iterations. I was able to crank out a 32 room dungeon in less than a second.

Enjoy some generated dungeons.

Reset makes a bunch of overlapping rooms

Generate generates the dungeon all at once

Tick generates the dungeon one step at a time