Dungeon Generator (Part 1) – Graph-Based Approach

on

In this blog post, I’ll describe an algorithm for procedural generation of 2D dungeon levels with a predefined structure. I won’t go into implementation details today as I plan to make this into a (mini) series and cover it in the next post.

All posts in the Dungeon generator series:

Background

The algorithm was written as a part of my bachelor thesis and is based on the previous work from Ma et al (2014). The goal of the thesis was to improve the speed of the algorithm and enhance it with new features. I’m quite satisfied with the result as we were able to make the algorithm fast enough to be used during game runtime. After finishing the thesis, we decided to transform it into a paper and submit it to the Game-ON 2018 conference.

Algorithm

To produce a game level, the algorithm takes a set of polygonal building blocks and a level connectivity graph (the level topology) as an input. Nodes in the graph represent rooms, and edges define connectivities between them. The goal of the algorithm is to assign a room shape and a position to each node in the graph in a way that no two room shapes intersect and every pair of neighbouring room shapes can be connected by doors.

(a)
(b)
(c)
(d)

(c) and (d) demonstrate layouts generated from the input graph in (a) and building blocks in (b).

Through the connectivity graph, a game designer can easily affect the flow of gameplay. Do you want a single main path to a boss room with some optional side paths? Simply start with a path graph and then pick some nodes where the player can choose to either follow the main path or explore a side path with possible treasures and/or monsters waiting for him. Do you want a shortcut? Simply choose two nodes in the graph and add a shorter path that connects them. The possibilities are endless.

Examples of input graphs. Main path is shown in red, optional paths are blue and a shortcut is orange.

Not only does the algorithm allow game designers to control the high-level structure of generated layouts, it also provides ways to control the look of individual rooms and how they are connected to each other.

Different room shapes for different rooms

I mentioned having a boos room at the end of the dungeon. But we do not want our boss room to look like every other room, right? The algorithm supports defining room shapes on a per-room basis. For example, we may have a spawn room and a boss room that should have their own sets of room shapes and then one generic set for other rooms.

Two layouts generated from an input graph that has a special room shape assigned to the room number 8.

Explicit door positions

Imagine having a really nice script for our boss encounter and that we need the player to enter the boss room from a specified tile. Or we may have a room template with some tiles reserved for walls or other obstacles. The algorithm allows game designers to explicitly specify possible door positions of individual room shapes.

But sometimes our goal may be the opposite. We may design our room templates in a way that they can have doors virtually anywhere. By doing that, we put less constraints on the algorithm and it therefore often runs faster and generated layouts may feel less repetitive and more organic. For such situations, there is a possibility to simply specify length of the doors and how far from corners they should be. The distance from corners is kind of a compromise between manually specifying all doors and having doors anywhere.

(a)
(b)

(a) illustrates different types of door positions – the square room has 8 explicitly defined door positions, whilst the rectangular room uses lenght and distance from corners. (b) shows a simple generated layout with room shapes from (a).

Corridors between rooms

When we talk about dungeon levels, we often imagine rooms connected by narrow corridors. It would be tempting to think that connections in the input graph represent corridors. However, these connections aren’t corridors – they just ensure that all neighbouring nodes can be connected directly by doors. If we want to have rooms connected by corridors, we have to insert a new node between all pairs of neighbouring rooms and pretend they are corridor rooms (with specific room shapes and door positions assigned).

(a)
(b)

Illustration of how we can modify the input graph to add corridors between rooms. (a) shows an input graph before adding corridor rooms. (b) shows an input graph created from (a) by adding a new room between all neigbouring rooms in the original graph.

Unfortunately, by doing so we make the task a lot harder for the algorithm as we often end up with twice as many nodes. Therefore, I implemented a version of the algorithm that is aware of corridors and can reduce the performance loss of laying out corridor rooms. The algorithm currently supports either having corridors between all rooms or not having corridors at all, but I plan to make this more customizable in the future.

Examples

Several layouts generated with different sets of building blocks and corridors enabled.

Several layouts generated with different sets of building blocks and corridors both enabled and disabled.

Download

You can find a .NET implementation of the algorithm on my github. The repository contains a .NET DLL and a WinForms GUI application which is controlled by YAML configuration files.

What’s next

In the next post I’ll describe how the algorithm works under the hood.

I’m also working on a Unity plugin for procedural dungeon generation that will incorporate this algorithm. The reason for that is that even though this algorithm can be directly used in Unity (as it is written in C#), the user experience is far from ideal. It is quite time-consuming to design room templates without a GUI and there is also quite a lot of programming needed to transform the output of the algorithm to a representation that is usable in a game.

As I’m not a game developer myself, the goal is to make the plugin good enough for someone else to use it. If everything goes well, I’ll try to post updates when I have something interesting to present. I’ve also got quite a few ideas regarding the generator itself and testing its possibilities.

Screenshots from the Unity plugin (WIP)

If you have any questions or suggestions, please let me know in the comments! Also this is my very first blog post so any feedback is appreciated.

18 thoughts on “Dungeon Generator (Part 1) – Graph-Based Approach

  1. Excellent resource.
    I had always wanted to re-make an old Dos game by Microprose called Sword Of the Samurai.

    This will help tons ( you could probably use it as an example too )

    Cheers,
    b

  2. Hello again, I have been trying to port this to java but without any success, I think this method is absolutely perfect for the game I’m working on.

    You can see the game here https://twitter.com/OkaeriStudio

    Can you port it to java or make a small example? I don’t need the corridors so, maybe is not too hard to do.

    I’m open to give you credit or pay a commission for it, thank you 🙂

    1. Hi Alpha,
      I think it very much depends on what portion of the library you want to port. The whole library’s written so that it’s extensible, which makes some parts of the code more complex that they need to be (and therefore harder to port). However, if you focus only on some part of the library and know that you’ll never need some additional features, I think it’s possible to port a simplified version to Java.

      As I said in the blog post, I plan to write another post that’ll cover the implementation of the algorithm and provide some tips & tricks regarding what to be aware of, etc..

      The problem is that I’m currently preparing for my final exams so the amount of free time I have is very limited and it’ll be like that for 3 more weeks.

  3. Hi! I was searching for a graph based solution for my game, ran in to the paper you used, and then found your work, great stuff!

    In my survival horror rogue-lite, I’m generating a house. I was wondering if you’ve implemented any way to pack the rooms together or limit how much they are spread. If not, how easily could I implement this? It wouldn’t need to eliminate all empty space, but the whole should somewhat conform to a rectangular area.

    Thanks!

      1. Ah, that’s understandable.

        Thanks. I noticed those papers as well, but I’m not really looking for a clean cut floor plan. It would be perfect for a realistic house, but I’m looking for ways to generate interesting layouts with plenty of variety (foregoing realism). Generating a rectangular floor plan seems to put more restrictions on graph complexity as well.

        Anyways, I might solve this by just squeezing and stretching the generated rooms where I can and adding filler rooms in the empty space left around. Using mostly rectangular rooms seems to produce compact layouts as well.

        Thanks for the fast reply!

  4. That’s pretty neat, and your post illustrates things well! Though for a practical tool, I think an important thing to consider is the ability to yield symmetrical and close-to-symmetrical maps through reflection and rotation. (And to take it further, symmetries applied to subgraphs, so you can have a long twisty cave that leads to a grandiose subterranean temple to the earth spirits or something of that nature).

    1. What would be the goal of yielding symmetrical maps? Would you generate a map and then apply reflection/rotation to create a different version of that map? Or would you generate a smaller part of a map and then compose its reflections/rotations together to make a single bigger map?

      1. > What would be the goal of yielding symmetrical maps?

        Symmetrical maps would lend themselves well to “built for purpose” style maps such as a building where a more specific design is desired… As an example, if it were a skyscraper, you might imagine that every floor was pretty similar from a top level (elevators in the middle, stairs on the sides, bathrooms in a very specific line, etc.). If it were a fortress or castle, you might have a similar set of rules for the types of rooms and the layout of those rooms in comparison to each other. Extending beyond rooms to “areas”, you could imagine that symmetry might be desired for something like a set of farm steads where the fields are all very similar in topological shape/design but the population of those fields are not (i.e. different animals or features).

        > Would you generate a map and then apply reflection/rotation to create a different version of that map?

        I think you might need to be more clever – especially if the two (or more) sides needed to be connecting. However, this design would lend itself really well to something like a classic castle where there’s a middle courtyard and four turrets.

        > Or would you generate a smaller part of a map and then compose its reflections/rotations together to make a single bigger map?

        I think this would work better at a less granular level of a region where there are “similar” but different. For example, if you were to model a township, you might want very similar buildings that are rotated in different areas or specifically follow a roadway or waterway.

  5. Hi! Another question.

    Is there any kind of timeout feature for this version? Or should I just update to using your unity plugin? I don’t really need the tools or editors, so I haven’t started using it yet.

    Thanks!

      1. Thanks! Got it working. That’s exactly what I was looking for.

        Another thing comes to mind; is it possible to run the generator in the background, while the player is completing a level? This would add stability to loading times.

        1. Yes, that’s absolutely possible. In fact, it’s very similar to what you already do with the “timeout feature”. When you do something like “Task.Run(() => layout = generator.GetLayouts(mapDescription, 1)[0]);”, it’s actually a non-blocking call which immediately returns a task which you can save to a variable, the computation will run in a different thread, and you check the result later when you need it. So this is more like a question about how to work with tasks (and multithreading) in C#/.NET.

Leave a Reply

Your email address will not be published. Required fields are marked *