Procedurally generating dungeons using predefined rooms

Question

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):

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:

Answer 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?

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.