In one of the last projects I’m doing for school, I’m working on a game wherein everything in the game is procedurally generated using a dungeon-building algorithm.
Fresh Content Each Time
One of the main draws of building a Roguelike game is figuring out how to procedurally generate dungeons. While it’s difficult to replicate the high-quality hand-crafted content of titles like Legend of Zelda: A Link to the Past, you can approximate a lot of the same experience while coming up with a new layout each time the game is loaded.
Achieving this is, as you may imagine, pretty difficult.
There are a lot of resources online, but most of them follow the same pattern - create a set of rooms, connect them, place items within them. There’s a significant amount of wiggle room within those, but that’s the basics.
Unity Set Up
The dungeon I built is based on a Unity Tilemap, which is effective a grid of 1x1 squares that you can place tiles within. For the game that I’m working on, I made each tile 16x16 pixels (you can set them to the density that you’re planning on making your tile sprites).
The unity objects involved:
- Two tilemaps (Created by Game Object > 2D Object > Tilemap). Spawning a tilemap will create a Grid object as its parent. I created two Tilemaps and connected them to the same parent. I attached my
Dungeon.csbuilding script as a component to this parent.
- Floor tilemap - This is what I use to tile the floor background, and this is the main data for the dungeon layout (since walls are just created using the floor layout).
- Walls (Collidable) tilemap - This one has a collider added to it, so the player can’t walk through them.
- Tile Palette - This contains all of the floor / wall tiles that I use to build the dungeon. It’s nice to have one of these so you can manually paint some on if you want.
Since dungeon generation algorithms can fall into a number of ways that they can end up in an infinite loop where they will never end up with a good dungeon layout, it’s best to program each step of this in the following way:
- While not at my limit of tries
- If failed, reset everything and increment how many tries I’ve done.
- Place a number of rooms in a grid.
- Derive a graph for the grid. The recommended way I found to do this was to create a Delauney Triangulation. This is somewhat complicated, so it’s recommended to find an algorithm or package that will do this for you.
- From that graph, derive a minimum spanning tree. I found that this was easy enough to do using Prim’s Algorithm, which is greedy and runs quickly.
- Verify that the graph meets your desired gameplay goals. For me, I wanted to make sure that I had at least two non-overlapping subtrees that comprised >25% of the nodes in the tree, so that I could use these as specific gameplay areas.
- Connect all the parent/child relationships in the tree with corridors.
- Once that’s done, add some optional corridors for the nodes within the same subtree, so that you can remove the perfect “tree”-ness of the layout and add some variety to it.
- Choose a boss room. For mine, I simply chose a leaf node in the larger subtree with a higher-than-average floor area.
- Choose rooms to place keys in that will open locked doors.
- Lock the doors.
- Place items and enemies within those rooms according to some sort of sliding difficulty scale. You can easily derive this difficulty on a number of simple heuristics (i.e. bigger room = more enemies, further depth in tree = harder enemies, etc).
First, a key, so you can understand what you’re looking at:
- Green / White = starting room / starting area
- Red = boss room
- Light blue = harder-than-starter area, Dark Blue = advanced area
- Yellow = room with a key
- White - Parent/child relationship in tree
- Yellow - Optional corridor added between two rooms in the same subtree.
The key to the light blue area spawns in the green / white area, the key to the dark blue area spawns in the light blue area. The key to the boss room is placed within the dark blue area.
As you can see in this one, sometimes the room with a key in it spawns directly next to the boss (in the first example above), but sometimes it’s located fairly far away in a different corner (in this example, on the bottom left).
In this example, I’ve included the minimum spanning tree generated during the dungeon building process. If you note the yellow corridors between rooms, those are randomly added between rooms within the same subtree.
TileMap.SetTile function can then be used to programmatically fill out which tiles are supposed to go where. Once you’ve got the room data figured out, it’s pretty easy to determine where to set tiles (floor tiles set within any room or corridor, wall tiles set in any empty space that borders a corridor or room).
From here, you can generate the items and enemies how you see fit.