Most attempts at procedurally generating dungeons I have stumbled upon do space out areas that will be rooms and connect them will corridors and hallways but what about instances where you have a collection of possible rooms in various dimensions and want to generate a dungeon that uses some of these specific rooms without those corridors and connections? To answer this question I found this particular video on the topic of generating levels in Path of Exile (~5:20 - ~7:20 about the dungeon part I am referring to) which left questions open on how to technically implement the algorithm described.

In general I understand the idea but I am struggling to figure out how this would be translated into code (most efficiently) and therefore here are a few questions:

  1. When he shows how the entire level is sliced up I could not come up with a graph that would allow to represent this structure. My naive approach would be to have the entire level consist of 1x1 rooms and arbitrarily merge nodes in the graph to form rooms of valid dimensions (valid = there is a predefined room that can be inserted there later on). What would be a suggested approach to this?
  2. Coloring the rooms should be just assigning random distances (in a given interval) to edges of connected nodes and just applying Dijkstra to find the sequence of rooms from start to finish I presume?
  3. When he adds branching rooms I noticed that they do not allow another alternative path to the exit (which could be random of course) but how would one implement the branching? Just a recursive traversal with diminishing chances of continuing deeper into the graph?

Description of the algorithm in the video

Step 1. Place a start and end room arbitrarily into the level (presumably with a given minimum distance to prevent degenerate layouts):

enter image description here

Step 2. Slice the entire level into areas that have exactly the sizes of your predefined rooms:

enter image description here

Step 3. Assign each room a random weighting/distance which is depicted with colors in this example:

enter image description here

Step 4. Find a shortest path to get a nonlinear path from start to end:

enter image description here

Step 5. You have your basic layout with a single successful path in which you can place random rooms of corresponding sizes that have to be connected with appropriate doors:

enter image description here

Step 6. Finally, add some branching rooms:

enter image description here

  • Can you describe the algorithm in the question? A video link is unwieldy and is susceptible to link rot. – congusbongus Sep 15 '17 at 6:23
  • @congusbongus Thanks for reminding me - I did edit the post. – Christian Ivicevic Sep 15 '17 at 10:14
up vote 2 down vote accepted

When he shows how the entire level is sliced up I could not come up with a graph that would allow to represent this structure. My naive approach would be to have the entire level consist of 1x1 rooms and arbitrarily merge nodes in the graph to form rooms of valid dimensions (valid = there is a predefined room that can be inserted there later on). What would be a suggested approach to this?

I would say it's valid approach, but doesn't give much opportunities to apply biases or complex structures: if you want more bigger rooms, you have to create smaller firsts, in a recursive manner. That by itself may hinder medium room sizes or non-rectangle rooms.

Alternatively create a map of nxm squares, mark entrance and exit as taken. Then try to create rooms in it with random positions. This way, you can try to create more rooms with 2x2, 1x3 or L-shaped than 4x4, simply by randomly but biased selecting, what room should be created next.

Coloring the rooms should be just assigning random distances (in a given interval) to edges of connected nodes and just applying Dijkstra to find the sequence of rooms from start to finish I presume?

If you already have rooms to those room slots assign, I wouldn't do that. If you have two pits of death one after another with low weight, this will be extremely hard. These two rooms should have higher weights, but maybe with a little difference of +/- k. But that's more game design, so yeah, Dijkstra to get the way.

On top of that, you can create side ways or alternative routes by applying new start and end rooms and leaving the already taken rooms out of the new sequence of rooms.

When he adds branching rooms I noticed that they do not allow another alternative path to the exit (which could be random of course) but how would one implement the branching? Just a recursive traversal with diminishing chances of continuing deeper into the graph?

Basically yes. Nothing to say here.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.