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:
- 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
1x1rooms 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?
- 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?
- 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):
Step 2. Slice the entire level into areas that have exactly the sizes of your predefined rooms:
Step 3. Assign each room a random weighting/distance which is depicted with colors in this example:
Step 4. Find a shortest path to get a nonlinear path from start to end:
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:
Step 6. Finally, add some branching rooms: