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). Or is it better to work with a two-dimensional array and fitting rooms of specific dimensions and then building a graph out of it? - 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?
Remark
Please notice that the collection exceeds the number of slices in the level and that it is not intended to define the number of rooms in the level beforehand. The number of slices should be arbitrary and the rooms randomly placed into the slices.
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 an arbitrary number of areas that have exactly the sizes of your predefined rooms from the collection:
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 dimensions that have to be connected with appropriate doors:
Step 6. Finally, add some branching rooms:
