I just watched Mark Brown’s new video on the dungeons in Link Between Worlds yesterday, and the three dungeon archetypes he mentions seem pretty interesting to me, not just from a game design point of view, but from a mathematical perspective as well.
So Mark Brown names these three dungeon archetypes “lock and key,” “puzzle box,” and “gauntlet” dungeons, respectively. Lock and key dungeons are the type where you have a path to follow (or several), but that path is full of locked doors, and to make progress through each door, you have to find the right key in some other room off the path. This is basically the type of gameplay that Metroidvanias are known for, but on the dungeon scale rather than the entire-game-world scale. Puzzle box dungeons are those where the dungeon itself changes shape, making the very act of getting around the dungeon a puzzle. And gauntlet dungeons are basically straight paths, where the focus is more on the individual puzzles in each room than on navigating the dungeon as a whole.
So let’s look at the elements that make up these dungeons. Since the dungeon is basically a maze the player has to navigate, the first thing the game can’t live without is the ability to navigate. For this, the game needs to be aware of
- the player’s position
- the rooms in the dungeon
- which rooms are reachable from which other rooms
Once the game has all three of these pieces of information, we have an abstract model of player movement, which can be illustrated using Zelda’s dungeon map screen:
And of course, we can represent this even more abstractly by representing rooms as points and connections between rooms as lines:
Now, a maze, by definition, implies a beginning and an end point. And a beginning and an end mean nothing unless they are distinct. But at the same time, they also mean nothing unless the player can reach the end point from the beginning, which means they have to be connected. So this leads us to our first minimal dungeon structure—a beginning and end separated by some arbitrary number of intermediate rooms. In other words, basically a straight line. And this corresponds to what Mark calls “gauntlet” dungeons. Of course, the trouble with this type of dungeon is that it’s not particularly interesting from a navigation perspective.
The model for the next level of dungeon is the lock and key, though of course, the terms “lock” and “key” can easily be replaced by anything else; for example, if one of the doors is blocked by a bear and the only way to get the bear out of the way is to feed it cheese (let’s say it’s a bear that likes cheese), then on the surface what we seem to have is a bear and cheese dungeon, but functionally it’s still equivalent to a lock and key. The important thing is that there’s a link we want to pass through, but we can’t pass through it without visiting another room first.
The thing about lock and key dungeons is that we can easily transform them into an equivalent gauntlet. Suppose we have a dungeon with a locked door L, which leads from room A to room B, and whose key is in room R.
Then if we just
- delete the locked door L, and
- create a new link going from room R to room B,
then we’re left with a simple gauntlet dungeon where the shortest solution has the player visit all the same rooms in the same order as the original lock and key dungeon, disregarding backtracking. So any lock and key dungeon can be algorithmically reduced to a room-order-equivalent gauntlet dungeon.
Creating multiple locks that can be opened in variable order doesn’t change much, assuming it isn’t possible to cut off the path to a key depending on the order of rooms visited. All this does is increase the number of possible equivalent gauntlets, where the number of equivalent gauntlets would be n! if n is the number of locked doors. And of course, increasing the number of paths is nice in its own way, but it still means you’re on your way from start straight to finish and there’s never really any point where you can’t proceed without thinking. This is probably why games often try to limit which keys unlock which doors and make a puzzle out of matching the keys and doors.
If the path taken blocks off other paths, then maybe things would be very different. But I don’t want to get into too much complicated stuff right now, so we’ll just assume that all paths are reachable, since that’s the way Zelda dungeons are typically made.
And this leads us to Mark’s favorite dungeon archetype, the puzzle box. The interesting thing about these is that the number and/or positions of the links between rooms vary in time. This means it isn’t possible to create an equivalent gauntlet, which is why these dungeons are so fun to pl…
No, wait. Actually, it is possible. But we’ll have to use a little trick that doesn’t really work in stateful programming.
That trick is to increase the number of rooms. We have to take each room that changes state and create a separate room for each state that that room can take, where the “state” of the room is defined in terms of what other rooms are reachable from the room in question. So, taking a simplified version of the Ancient Cistern from Skyward Sword, where there’s a central “tower” that moves up and down, allowing the player to enter a different room depending on its current height, we have to represent the dungeon map like this:
where the room containing the central tower appears three times because it takes three different states, one where you can reach the top room, one where you can reach the middle room, and one where you can reach the bottom room.
Of course, the trouble is that we then have to triple all the other rooms in the dungeon as well. After all, our only way of keeping track of state is the player’s position, so if we had the other rooms appear only once, then that would mean that the state behaves funny somehow; for example, if we do this:
then that means that you won’t be able to leave the room except when the highest room on the tower is accessible, and whenever the player is outside of the central room, the tower must always be in that position. This creates the impression that the room itself is moving, not the central tower. So we have to do this:
with a separate copy of the rest of the dungeon for each state, so that it’s possible for the player to leave at any time, and when he comes back, he finds the room as he left it.
So yes, it is possible to reduce even a complex puzzle box dungeon to a gauntlet. And this makes sense intuitively, because if you’ve ever looked at a walkthrough, you know that it always provides the way through the dungeon as a linear path.
However, puzzle box dungeons don’t feel linear, which of course is why Mark likes them so much. Why is that?
Probably because the process of reducing the dungeon to an equivalent gauntlet is not algorithmic. At least, I don’t think it is. It’s not at all obvious how any given stateful dungeon maps to a stateless graph. In fact, I didn’t think of mapping each state to a room until well after I’d started writing this post; I actually thought I’d be arguing that puzzle box dungeons can’t be reduced to gauntlets.
Then after the idea occurred to me, I tried to see if I could reduce this little puzzle in the Sword and Shield dungeon in Oracle of Seasons to a gauntlet.
That big circle in the middle rotates 90 degrees each time the player steps on it, alternating directions each time. So if you step on it from the east side, then it’ll rotate you down to the south, but if you step on it again from the south side then it’ll just take you back to the east. But then if you were to, say, step on it from the east, leave the room to the south, and then circle around and get back on the wheel from the north, then it would take you to the west.
To accommodate both the alternating directions and the fact that you can only reach one quarter of the wheel at any given time, I had to replace this one room with eight. So not only is the mapping to a simple graph non-trivial, the number of rooms needed also increases quickly with the number of states, which means that with a well-made puzzle box dungeon, you can’t just use the process of elimination to find the right path.
These two factors together mean that to solve this type of dungeon, you have to have some kind of insight that allows you to see which path is right without testing each one individually. And this is exactly what is so satisfying about these types of dungeons.