How do I Generate a random dungeon layout?

I remember watching a simple youtube tutorial (not specific to Construct), explaining how to randomly generate dungeons like this, where there is a guaranteed route through all rooms from start to finish.

Basically, the algorithm determined how many passages/doors will be in each room and where they will be located.

Unfortunately, I lost that video.

Does anyone have a link to that tutorial or know the algorithm to generate such levels?

I don't know the video or specific algorithm you might be referring to, but the first approach I would try would be with a random walker algorithm, where the walkers are not allowed to move into existing tiles (or out of the bounds of the map). If the walker "traps" itself or reaches the exit, then start over, following the same previous path until there is a valid tile to branch into, and continue from there. You can add the constraint of not allowing 4 way rooms, but if you don't allow 3 way rooms either that would be difficult to always arrive at a specific end tile, and it may not be solvable at if there is a requirement for every tile to be filled in. Repeat until all possible tiles are filled or unreachable.

This should result in a map where all tiles are reachable from both the entrance and exit. By keeping track of the number of existing exits from each room, additional constraints can be added, like only one exit for the entrance and exit rooms.

So at each step, generate a list of valid tiles/exits to walk to, and pick one randomly, until there are no more valid exits. Then start over from the beginning until a valid exit is found to make a branch.

The blue x on the second iteration represents the constraint where the first room can only have 1 exit, so a branch cannot be made there. The red x on the third iteration is the constraint that a room cannot have 4 exits, so it can't branch there and continues until it finds a valid tile to branch into.

R0J0hound Thanks, your example is what I need! Although I have a feeling they used the Wave Function Collapse in that video... Maybe I'm wrong.

oosyrag Interesting method, but a bit over complicated. And as I understand, it may create impossible configurations, which means it will need to be repeated until a good solution is found.

XHXIAIEIN These links are amazing, thank you! Yeah, that video tutorial definitely explained one of these algorithms, it doesn't matter which one now :)

My addiction 'for' loop drives me to create recursive room generator to be tested:

dropbox.com/s/bdwbztvqalda546/recursive_dungeon_room.capx

The pattern recursion based on 4^n_division that generates multiplication by 1, 4, 16 and so on. I called this quad division. 3/4 passage generated for each cross section and shifted randomly during division to fit middle wall.

I found the following maze tutorial on Youtube which explains a recursive maze creation method:

https://www.youtube.com/watch?v=Y37-gB83HKE

enjoy