Hi, I'm trying to implement a random level generator from premade rooms, something very similar to Rogue Legacy,

As you may know this is not a procedurally generated level so doors can be in some predefined locations of rooms.

There is no open ground between rooms, there is no corridors that connects rooms, rooms only connected to each other by their doors.

The generation algorithm should be fast and generate levels without dead locks.

All rooms are accessible from each other, some rooms may make a loop.

Should I use a trial and error algorithm like Depth First Search?

I have some experience in procedural generation, and I think the most important question is: "How would you go about generating one of these levels if I had to do it by hand?". After this exercise in introspection, you go and try to implement it.

Most of the time, the problem of designing something can be broken down into smaller problems, which organizes the design process in a top-down manner (first subdividing a city into neighborhoods and avenues that separate them, then a neighborhood into sections and important streets, then sections into blocks and streets, blocks into buildings...).

The level in your example doesn't seem to have any overarching design, just some local rules of each room matching the adjacent rooms. This is probably a missed opportunity to give some coherence to the whole (wouldn't it be nice to have a section where a main hall gives access to several rooms, acting as a hub? How about having some section with symmetry?). The architect Christopher Alexander wrote a lot about the types of patterns that show up in buildings, and using some of his philosophy makes procedural designs much more believable.

But, if you don't want any overarching design, a randomized depth-first search will probably work just fine.

Thanx Álvaro,

I was wondering about expanding rooms according to their doors in a DFS like manner but I didn't know how depth should I go into or should I expand rooms in Breadth.

For this case I'm trying to build a random BSP tree and putting the rooms at the leaf of the tree and match the doors, this will reduce the number of trial and errors.

The search doesn't need to be depth limited. You keep going until you either succeed (meaning "no unmatched doors remain" and perhaps something like "at least 80% of the area is covered by rooms"), or until you can prove that the current attempt doesn't have a solution (I am not sure what conditions you would put here, but "a door faces the edge of the map" might be one). If your search takes too long, you can probably help the situation by supplying a more complete set of rooms.