2
\$\begingroup\$

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. enter image description here

\$\endgroup\$
  • 2
    \$\begingroup\$ There are countless ways to do this, if you'd typed [procedural-generation] and maybe another term like rooms or dungeon into the search bar at top right you'd have found many, many questions on this topic just on this site... let alone googling same terms. Moreover, your question is underspecified, making it impossible to give one correct answer without making numerous assumptions, so I'm voting to close. \$\endgroup\$ – Engineer Aug 2 '17 at 10:16
  • \$\begingroup\$ I agree with @ArcaneEngineer - there's a lot of missing detail here. For example: Are the rooms all the same size? Are the hall ways the same size? Is the layout restricted to cardinal directions? Are there min / max # of room constraints? Do you need to limit the # or length of paths from start to finish? Perhaps most importantly: what have you tried so far? \$\endgroup\$ – Pikalek Aug 2 '17 at 14:31
  • \$\begingroup\$ @Pikalek Thanks you for the example. I updated the questions. \$\endgroup\$ – leloctai Aug 3 '17 at 6:29
  • \$\begingroup\$ Possible duplicate of Algorithm for procedureral 2D map with connected paths \$\endgroup\$ – Shashimee Aug 3 '17 at 9:47
  • 1
    \$\begingroup\$ From the back and forth discussion above, it sounds like you have additional constraints and preferences for the output that aren't stated concretely in the body of your question. (eg. how many is a "few" secret rooms? How many paths is "too many"? Where is the sweet spot between "relatively straight" and "natural paths (not just an L shape or a straight line)"?). To make sure your question is unambiguous, please edit it to make your algorithm criteria explicit and precise. \$\endgroup\$ – DMGregory Aug 3 '17 at 17:01
2
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.