Lock + Key, Puzzle Box, and Gauntlet Dungeons

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:

dungeon-map

And of course, we can represent this even more abstractly by representing rooms as points and connections between rooms as lines:

abstract-dungeon-map

……… Don’t laugh.

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.

lock-and-key

Then if we just

  1. delete the locked door L, and
  2. create a new link going from room R to room B,

lock-and-key-to-gauntlet

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:

ancient-cistern

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:

ancient-cistern-invalid

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:

ancient-cistern-better

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.

sword-and-shield-dungeon

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.

Probably.

Aristotle, Definitions, and Math, Pt. 1

I’ve been thinking of rebooting my Aristotelian metaphysics series, and I thought I might put this as the preamble or something, so you might also consider this a draft of that.

This stuff is mostly just observations of analogies; I’m not sure if I would consider any of it strictly “proven.”

EDIT: Realized I forgot to add tags.


Aristotelian thought distinguishes two ways in which a given attribute can exist in multiple things: formally and analogically. An attribute exists in two things formally if it is in both of them in exactly the same way; so two red objects both have redness formally, since there are no two ways that something can be red (if we’re specific about what hue we mean by “red”). On the other hand, an attribute exists in two things analogically if it exists in both of them in different ways. For example, both humans and octopuses can be considered to have “hands” in a sense, but obviously a human’s hands are very different from an octopus’s tentacles.

Aristotelian thought also gives us an archetypal form of definition. This form works by considering a genus of things that are assumed to be known to the listener, and delimiting a species from within that genus by means of a specific difference that is common to everything in that species. So for example, a mammal can be defined as a species of animal whose females bear live young and feed their newborns with milk. (Of course, this isn’t technically accurate because platypuses and echidnas lay eggs.) This definition takes a category, animals, that is assumed to be known to the listener, and then delimits the category of mammals by means of their common characteristic of bearing live young and nursing their newborns. Here, the genus is animals, the species is mammals, and the specific difference is bearing live young and nursing their newborns.

Notice that “genus” and “species” are relative terms, since a category can be a genus relative to another, narrower category and a species relative to another, broader category. Further, genera are recursive, since a species within a genus is itself (potentially) a genus; the genus is made up of genera.

Now, math makes a lot of use of things called “sets,” which are rather vaguely defined collections of objects. As you work with them, you gain an intuitive grasp of them, but they’re never really rigorously defined. All you can really say about a set is, as the Wikipedia page says, that it’s a collection of well-defined objects (ironic, considering that the set itself is vaguely defined). Thus a set can contain anything. You can define a set consisting of the numbers 7, 12, 13, 19, and 20, just because you like those numbers. Or you can define a set consisting of red, green, and blue. Or you can refer to the set of all even numbers, or the set of all rational numbers, etc. Or the set of all people who wear their hair in a topknot.

A set can also be broken down into subsets, where every member of the subset is also in the original set (referred to as a superset). So the set containing 2, 4, and 6 is a subset of the even numbers, while the even numbers are a superset of the set containing 2, 4, and 6.

Incidentally, it’s also perfectly acceptable to have a set of sets. In fact, the set of all subsets of a given set is called the power set of that set.

This brings up an interesting question: Is it possible to form a set of all sets? As it turns out, the answer is no, because it results in Russell’s paradox. Every set is either a member of itself or not; for convenience, we can refer to these as self-inclusive sets and self-exclusive sets. The set of all self-exclusive sets would then have to be a subset of the set of all sets. But is the set of all self-exclusive sets a self-exclusive set, or a self-inclusive set? If it’s self-exclusive, then it would have to be a member of itself—which then implies that it must be self-inclusive. By the same token, if it’s self-inclusive, then that means that it’s not a member of itself, which means that it must be self-exclusive. Either way, we get a contradiction. Therefore, the set of all self-exclusive sets can’t possibly exist, and therefore the set of all sets, which must be a superset of the former, also can’t exist.

This leads us to the concept of classes, which is even more vaguely defined than sets. Basically, a class is a group of objects that all have something in common somehow, but that we can’t necessarily represent as a set. “All sets” would then be a class, but not a set.

Now, one interesting point that’s often glossed over in math textbooks is that there’s a very obvious difference between sets like “7, 12, 13, 19, and 20” and sets like “the even numbers.” Formal math doesn’t have a term for distinguishing these two types of sets as far as I know, but for convenience, let’s call the former type of set a scoop (from the action of arbitrarily scooping random things out of a jar) and the latter a proper set. We can then say that a scoop only exists because somebody decided it does, while a proper set actually has a kind of inner coherence. Why is this?

Well, thinking back to Aristotle gives us a clue. The members of a scoop don’t necessarily have anything in common. But the members of a proper set have some common characteristic that they all share formally. And we can take this as a kind of “definition” of proper sets: A proper set is a grouping of objects that all share some common characteristic formally (but see below—I don’t think it’s actually possible to give a rigorous definition of proper sets).

And recalling the Aristotelian contrast of formal vs. analogical and the mathematical contrast of set vs. class immediately brings another connection to mind: A class would just be a grouping of objects that all share some common characteristic analogically.

And now that we’ve gotten ourselves into a math-and-Aristotle-y sort of mood, we might as well go a bit further. Recall how genera and species behave recursively—any species within a genus can potentially be a genus itself, and any genus can potentially be a species of another genus. Well, notice that the relation of supersets and subsets behaves in exactly the same way—any subset can potentially be a superset of another set, and any superset can potentially be a subset of another set. And further notice that a species is delimited by some characteristic that all its members share formally. In other words, a species is a proper set. So a definition is nothing other than a delimitation of one proper set from within another.

And this shows why it’s not possible to define proper sets—we would have to delimit the proper set of all proper sets from some other proper set, which is impossible because, as shown above, there is no proper set of proper sets. But the collection of all sets is a class, which tells us that proper sets are an analogical concept.