What algorithm should I use to laid out pre-made rooms into a level?

Question

I want to have a semi-procedural level, where rooms are pre-made but the way they're connected are proc-gen. The connections need to really exist - you can walk between rooms in hallways - not just teleported between rooms like in old games.

Each map will have a set number of rooms. Rooms should be laid into a grid(not necessary fill it) - all rooms and hallways will have the same size. Every room must lead to the exit(no dead end), except for 0 to 2 "secret room"

There can be 1 to 3 paths from start to finish; these paths may intersect. They should be relatively straight(no 180 turn or more).

There can a few rare "secret room" that are dead-end, but can only be one room depth:

              +-----+                                +-----+
              |     |                                |     |
              | End |                                | End |
              +-----+                                +-----+
                | |                                    | |
   +------+   +-----+          +------+   +------+   +-----+
   |      +---+     |          |      +---+      +---+     |
   | This +---+     |          | Not  +---+ This +---+     |
   +------+   +-----+          +------+   +------+   +-----+
                | |                                    | |
              +-----+                                +-----+
              |     |                                |     |
              |Start|                                |Start|
              +-----+                                +-----+

---

Is there a popular algorithm can I use to accomplish this?

One that was recommended by some people here is BSP Tree. It doesn't fit my requirement since the path it creates is too spiral, and depend on the number of corridors, it either creates too much path or too many dead-end.

The only thing I can come up with is to just add rooms one after another in random directions. There are 2 problems I can see and don't know how to solve:

• How to create multiple natural paths(not just an L shape or straight line) that end up at the same location.

• How to make sure the path doesn't become a spiral and block it self from advance further

Edit: I found this that that kinda resembles the structure I need, but with diagonal hallway.

Answer 1

Begin with a straight path from start to finish

[S] - [1] - [2] - [3] - [E]

Pick a hallway at random. Imagine we choose the hallway 3-E (between room three and the end). Since the hallway runs left/right, we will look at choosing either up or down. There is nothing above or below either 3 or E, so either works. If neither worked, we would have to choose a different hallway. We randomly choose down.

[S] - [1] - [2] - [3]   [E]
                   |     |
                  [X] - [X]

This is a new possible path. We made this by replacing the hallway 3-E with a long path through two new rooms. Let's renumber our rooms.

[S] - [1] - [2] - [3]   [E]
                   |     |
                  [4] - [5]

Now repeat. We randomly choose hallway 2-3 next. There is a room below room 3, so we can only choose up. We add two rooms again and renumber our rooms:

            [3] - [4]
             |     |
[S] - [1] - [2]   [5]   [E]
                   |     |
                  [6] - [7]

So far so good. Since we are trying to get to a destination on the right, most new rooms will be added to the top and bottom, since adding left or right would mean a path that backtracks, but after enough iterations, it could still happen, like this:

            [3] - [4]
             |     |
[S] - [1] - [2]   [5]   [E]
                   |     |
                  [6]   [9]
                   |     |
                  [7] - [8]

Followed by:

            [3] - [4]
             |     |
[S] - [1] - [2]   [5]   [E]
                   |     |
            [7] - [6]   [11]
             |           |
            [8] - [9] - [10]

At every iteration, it meets the base requirement: a single random path with no dead ends that reaches a fixed destination. Once you have your path a sufficient length, you can stop. Now to add the secret room. First, get a list of all the possible branches. You can do this by looking one by one at each room (probably excluding S and E), and adding something to the list for each open spot. Our list might look like this:

1-up, 1-down,
3-up, 3-left,
4-up, 4-right,
7-left,
8-left, 8-down,
9-down,
10-down, 10-right,
11-right

We randomly choose one from this list. Let's say we choose 7-left. Our final path looks like this:

            [3] - [4]
             |     |
[S] - [1] - [2]   [5]   [E]
                   |     |
      [S] - [7] - [6]   [11]
             |           |
            [8] - [9] - [10]

If you want to add more secret rooms, remove 7-left and 1-down from the list, since they both would lead to the now-occupied space. Then pick another at random.

A few modifications you might want:

• Just disable adding to the path left or right if you want your paths more straight.
• Do the first part of the algorithm multiple times, then lay them one on top of another before adding the secret rooms. This way you could have multiple intersecting paths.

Alternatively, you could displace an entire section of a random width each iteration. For example, if we choose a length of two and there is enough space for it, you would remove the room between the two hallways and then add three new rooms, like this:

[1] - [2] - [3]    ->    [1]         [3]
                          |           |
                         [X] - [X] - [X]