itch.io

So, for the layout of the dungeon I wanted to have some walls between the rooms, but not for it to be a full maze, which would make it too hard to navigate around. Every technique I've found seemed to be focused on mazes... But then I remember some article about an old Atari game where each screen was a small maze itself. So at first I basically did this, except for the walls between rooms, instead of inside a screen:

But after I while the penny dropped: this technique on the original game ensures each "exit" is reachable from one another... But it doesn't stop from making closed rooms in the middle.

So, the real interesting tech is in the second step (in hindsight this means the first step could replaced with just flipping a coin to decide if the path between two rooms is closed or not): I use a Union-Find Forest (https://en.wikipedia.org/wiki/Disjoint-set_data_structure). First I put each room in its own set, then for each pair of directly connected rooms I do a union of their sets. After that I check for each room if a neighbor is in a different set; if they do, I remove the wall between them and do a union of their sets. This ensures every room is reachable.

Just to be clear, on my game the dungeon layout is procedural, but the content of each room is randomly picked from some handmade templates; except there are 5 specific room templates (for the intended bosses) which are placed in not-so-random places as well. (e.g. the Terracotta Titan's room is placed in a random place near the bottom of the dungeon).