A Dungeon Generator based on Physics and Minimum Spanning Trees

When we think of procedural content generators (PCG) for levels, we usually think of mathematics, random numbers, and computations. They are the main ingredients to build variations within our games. One other approach that we use less often is physics-based simulation.

In this tutorial, we’re going to create a dungeon using Godot’s physics engine that’s more refined than what we made in the first chapter.

Here is how our final product looks.

Unlike in the first chapter, rooms can clump together with this algorithm, creating large open spaces. We keep the rooms that overlap with the corridors to create this thick look.

We use the cream color (#ffffeb) from the Pear36 palette as our background because our tileset uses a dark purple that doesn’t go well with the default gray. You can change this color by going to the menu Project > Project Settings > Rendering > Environment.

In this chapter, you will learn advanced concepts such as:

• Manipulating RigidBody2D and controlling its rest state.
• Calculating a graph of required connections between rooms.
• Understanding and using AStar2D.
• Animating in real-time using TileMap so you can visualize the algorithm at work.
• Using signals to coordinate the game execution.

Get the demo project

This chapter’s associated directory, in our Procedural Generation demos project, is MSTDungeon. The implementation from the final demo project is slightly different from the one you will code here. It provides visual feedback for the Minimum Spanning Tree graph and the final room graph as well.

All classes related to this algorithm have a class_name that starts with MSTDungeon to prevent conflicts in class name registrations by Godot.

Preparing the project

Open a new project in Godot if you haven’t done so yet and copy the Common folder from our Procedural Generation demos project. Likewise, you can copy the MSTDungeon folder in case you want to compare your work and the final implementation easily.

Brief overview of the algorithm

The steps to generating the dungeon are:

1. Create the RigidBody2D rooms by modifying how the physics object works for our needs.
2. Randomly place the rooms in a circular pattern, clustered together.
3. Start the physics simulation and wait to stabilize, that is to say until there are no collision detections and rooms are non-overlapping.
4. Select the main rooms for the next step, based on the average room size.
5. Compute the minimum spanning tree (MST) graph for main rooms. We’ll use Prim’s algorithm for this.
6. Read a few more edges to the MST graph so that the player doesn’t have to backtrack too much between dead ends.
7. Connect rooms with corridors and complete the level.

References

This tutorial is based on work from:

• Procedural Dungeon Generation Algorithm. This is a Unity tutorial that explores this concept in an overview format.
• Procedural Generation in Godot. This playlist contains a mini-tutorial series exploring the same concept by KidsCanCode.