0
\$\begingroup\$

An upcoming goal of mine is to write a procedural generation algorithm for daggerfall-esque dungeons. However, I plan on including doors locked with specific keys and I would rather they be able to be accessed by the player, at least at some point. (Perhaps in a hypothetical situation. one or two keys are accessible at first and the rest are locked behind those doors)

How would I go about approaching this?

\$\endgroup\$
4
  • 2
    \$\begingroup\$ What have you tried? What are you having trouble with? \$\endgroup\$
    – user35344
    Jan 24, 2021 at 14:34
  • \$\begingroup\$ Havent tried anything yet. I'm just not sure what theory I will follow for ensuring that each key is at least accessible at some point \$\endgroup\$ Jan 24, 2021 at 14:36
  • \$\begingroup\$ I have a previous answer here that might give you some possible leads. Take a look there, and if you need help applying it to your case, try editing your question to diagram out the kind of dungeons and lock-key placements you want to generate. \$\endgroup\$
    – DMGregory
    Jan 24, 2021 at 15:06
  • \$\begingroup\$ I have taken a glance and it seems helpful. I'll take a closer look when I have more time today. Thanks! \$\endgroup\$ Jan 24, 2021 at 15:28

1 Answer 1

2
\$\begingroup\$

Doors and keys (or switches, or puzzles, or whatever is used to open them), have a very simple rule: The player must be able to reach the key without crossing the door.

Ergo, if you decide, at random, that at some point there will be a door. There must be a path from the start position to the position of they that does not crosses the door.

Furthermore, a locked door is - rarely - of much use for the design if you can simply bypass it. Thus, we expect that the door restrict access to some part of the graph (dungeon or maze). So, you know, don't put the key there.


However, I will suggest to generate the dungeon by expanding from the starting area. And I'm going to suggest to place the keys first. That way you know that the key will be reachable before the door. I'll also suggest to expand breath first, to increase the chance a key will be on a different path than the door it opens.

You may also want to avoid interconnecting path that require different sets of keys. A simple way to do that (assuming a single threaded generation) is marking every area with the number of keys you have placed, and only connect between existing areas that have the same number (or if you can make one way paths, make them from higher to lower number, so they are shortcuts for backtracking but not for sequence breaking - or if you want to support sequence breaking those paths need to be hidden or hard to execute). Or don't connect at all, that is even easier. In which case the dungeon will be a tree.

Thus, it is possible to generate the order of keys and doors, as long as the key for a door is before it. And then you place it in that order.


By the way, I said area, because they don't have to be rooms. You may generate areas, and then subdivide them into rooms and corridors with a secondary dungeon generation algorithm. If you do that at all, and what kind of algorithm, depends on what you are going for.


Going further:

For a zelda-like design, you want the dungeon to have states. There will be something that open some paths in exchange of closing others. We are not talking of a switch that opens a door. That would be a key. We are talking of a switch that opens some doors and closes others. Or on a Metroidvania fashion, there will a second version of the map, and instead of a switch we have a room that allows to travel between them.

To do that, when you generate a new area, add a new node for each state of the node. Do the interconnections of the area based on the state. The node for the area 1 in state A, connects to the node for the are 2 also in state A. On a switch area, all the states gets connected. To account for the operation of the switch, some paths will be blocked on one graph, but not on the other.

For example, let us say our map in state A looks like this:

    8   5 - 4
    |    
    1 - 2 - 3 
        
        6 - 7

And in state B looks like this:

    8   5 - 4
        |   |
    1 - 2   3
        |
        6 - 7

Where area 3 is a switch area.

If we made our graph as follows:

    8   5 - 4
    |   |   |
    1 - 2 - 3
        |
        6 - 7

It would appear that I can put a key in 5 that opens the path from 2 to 3. But that won't work, because we need to go from 2 to 3 to activate the switch before we can reach 5.

Instead the graph must be like this:

    8   5 - 4
    |       
    1 - 2 - 3-+
              |
        6 - 7 |
              |
              |
    8   5 - 4 |
        |   | |
    1 - 2   3-+
        |
        6 - 7

And that is why a node per area per state is created. In this case with two states, each area has two nodes.

We also see, for example, it is valid to put a key in 5 that opens 8, but using it requires to switch back.


By the way, a door does not have to be a literal door. It can be some kind of obstacle that can only be removed if you a certain something which we call a key. For example, you could have rocks blocking a path, and you need a bomb to open it. The rocks are the door, the bombs are the key. You put that in your dungeon generation system, et voilà.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks! This should be very helpful. I'll get to writing the algorithm when I'm free. \$\endgroup\$ Jan 24, 2021 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .