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:


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


……… 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.


Then if we just

  1. delete the locked door L, and
  2. 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.


Manga Translation Draft: Posiko Maemuki’s Misunderstanding, Ch. 1

I said a couple posts ago that I’d start posting drafts here, but the posts I’ve put up since then have been more or less finished pieces. So I guess this is my first genuinely unfinished post. Hoo-ray!

So this is my translation-in-progress of Posiko Maemuki’s Misunderstanding (まえむきポジ子のかんちがい), chapter 1. As you will probably notice, it switches from English to Japanese in the middle. That’s where I left off. The formatting of the text is also a little rough around the edges.

As for the manga itself, what I find charming about this one is its simplicity, from the art style to the premise to the naming of the characters. The story is that one day the male lead, Negaji Kurasugi, runs into the female lead, Posiko Maemuki, before going home from high school. It’s raining and Posiko doesn’t seem to have an umbrella, so to avoid being considered a cad he gives her his umbrella and goes home in the middle of the rain. But Posiko misinterprets this as meaning that he has a crush on her, and hilarity ensues.

The characters all have blatantly obvious punny names. Negaji’s name is literally just the “nega-” of “negative” (which the Japanese use as a loanword to mean “pessimistic”), plus “-ji,” a masculine name suffix. Likewise, Posiko’s name is the “posi-“of “positive” (which in Japanese means “optimistic”), plus “-ko,” a feminine name suffix. Negaji’s last name, Kurasugi, is made up of individual elements that commonly appear in Japanese last names. But they never appear in this combination, which happens to mean “too dark,” where “dark” can be applied to people to mean “having a depressing personality.” Posiko’s last name, Maemuki, is actually just the native Japanese word for “optimistic” (literally, “forward-facing”).

So with that, here’s the actual manga-in-progress:


Wiki Walking

Today, I started here:


and ended up here:


The steps being:

  1. I wanted to download all the images in that manga automatically using JavaScript (or at least open all of them in separate tabs so I can use the “Save image as” context menu easily. As it is, if you right click on the images there, the browser doesn’t register them as images, so you have to use the inspect element thing and hunt for the URL’s manually.)
  2. My first attempt didn’t work because of CORS restrictions
  3. I searched for a workaround on Stack Overflow
  4. There was a trending question about physics in the sidebar
  5. One of the answers mentioned this concept

I think Stack Overflow’s trending questions are getting to be my single biggest cause of distraction lately. Which is only natural I guess, now that I’m programming every day for an internship.

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.

Most Secure Credit Card

LOS ANGELES, CA—As of 20 July 2017, First City Credit Union has begun issuing a new credit card which, they claim, is more secure than any yet seen.

“I think we can confidently say that this new card is not only more secure than any other bank’s, but also more secure than any that will be invented in the foreseeable future,” said spokesman David Smith.

“The key insight that led to this new technology is that the number one cause of credit card fraud is the fact that it allows access to the owner’s money. Therefore, the most efficient way to prevent credit-card-related fraud is to prevent all access to the card owner’s account from the outset.”

The new card is set up so that any use of it is immediately flagged as suspicious activity, and the payment it was used for is immediately refused.

First City Credit Union members are elated at this new level of security. “I’m getting one of those new cards as soon as I get time to go to the bank!” said local resident Raphael “Raff” Jones. “It used to be whenever I lost my card, I would have to call the bank, sit on hold for half an hour, answer a bunch of questions, and request a new card to be sent in a week. Now, even if I lose my card, I don’t have to do anything. So convenient!”

Smith added that to encourage card owners to be cautious with their money, reward points will be granted for every month the card owner does not use his card. The reward points in turn are protected by a system whereby every time the account holder uses said points, his points are dropped to zero, the reward request is refused, and his account is placed on lock down. ■

Actual Blogging

I just got a crazy idea.

I think I’ll use this blog for actual blogging.

Up till now, I’ve been using this site as basically a place to publish essays. So I would think of a topic (generally something that annoys me), write an essay on it, and upload it once I had written out the whole thing, read over it many times, and decided that it was completely finished. But then of course, so many of the things I wrote would just rot in my draft box as I either A) got bored of editing it, B) got scared that people would think it was stupid or not worth writing, or C) moved on to the next idea.

So then I got an idea: How about I publish drafts of essays? As in, I’ll write an essay and, even if I think it could be better, publish it with “draft 1” or something in the title, with the understanding that I might re-publish it later as “draft 2” (or 3 or 4 etc.) with heavy modifications. If I actually get something to the point where I think it’s “finished,” then I’ll publish it without “draft” in the title, and maybe link to it on a separate page in the site header. (Or maybe not, because I’m lazy.)

So instead of this site just being a place for finished essays, it’ll be like a log of my writing as it progresses. You know, like an actual web log.

Hopefully, this will also have the psychological effect of helping me see that my writing isn’t something the world revolves around, and it’s perfectly OK for me to put something unfinished on the web.

And for that matter, I could also use this for things other than writing. Like programming or music-writing or whatever.

So I guess I’ll start doing that in the next few days or so. I already have some writing and programming and music related stuff I’m working on, so I guess I’ll put up one of those in the next few days.

And just to make sure I don’t get cold feet, I’m going to publish this the day I wrote it rather than sleep on it.

Random Thoughts

I’m long overdue for a post and I feel like if I try to write something serious then it’ll end up in my draft box for eternity, so I’ll just write some random thoughts. I’m a bit short on sleep at the moment, so sorry if there are spelling or grammar errors.

“Nexus” by ClariS makes me happy. I don’t care if it’s girly or otaku-y or whatever, it’s just fun to listen to. The melody is so catchy, and the rhythmic contrast from the percussion is on point. I would link to a YouTube video, but I couldn’t find one of the original song, just remixes.

The name of my blog is embarrassing. I’m going to change it as soon as I think of something better. Why is it that the first name I think of is always stupid? It’s like this with everything. Even the name of my first Neopet back in grade school was stupid.

Recently, I stumbled across an old post on Yard Sale of the Mind (which is a great blog name, by the way. Why couldn’t I have thought of something like that?) that reads, in part:

“The so-called ‘contemporary’ masses around here are mostly run by and for elderly hippies and wannabe musicians who couldn’t get a gig playing for free at a coffee shop.”


So friggin’ true.

The proof is in the genre of the music at these “young adult” Masses. Genre is like the cultural DNA of music.

What genre even is “Pan de Vida”? “We Come to the Feast”? “Christ Is Our Light”? “Here I Am, Lord”? “Our God Is an Awesome God”? “And He Will Raise You Up on Eagle’s Wings” (or whatever the title of that one is)? I can’t even place them—which just goes to show how culturally out of touch these songs are. The only thing I can think of that remotely resembles these songs is ballad.

By contrast, what are the genres we hear most often nowadays? Personally, I mostly hear alternative rock, pop, and rap, with the occasional 70’s/80’s throwback disco or rock.

Now, does modern Catholic church music sound anything like any of these genres? Of course not. Because it’s not aimed at the people who listen to that kind of music, a.k.a. young adults.

I think probably the biggest lesson I’ve ever learned in life is, “Yes, it really is that simple.” Or rather, the biggest lesson I’ve still only partially learned in life, because I have to re-learn it all the time.

When it comes to composing music, if you can come up with melodies, rhythms, and chord progressions mentally without needing an instrument to hear them on, then yes, composing is just a matter of deciding that the melody will sound like this right here and the accompaniment will sound like this right here.

When it comes to drawing, if your eyes are functional, you can make lines and shading, and you have a sufficient understanding of light, then yes, it’s just a matter of deciding that this line looks like the model so it’s fine, but that line doesn’t look like the model so it needs to be redone, or likewise with shading and color.

When it comes to coding, if you know about variables, scoping, data types, functions, closures, vectors, hash tables, structs, conditional branching, looping, and error handling, then yes, programming is just a matter of deciding that “Yes, the output of this program is what I want it to be” or “No, I want it to output this instead.”

And yet I’m always worrying about whether this or that design choice is “right” or “wrong” in areas where that kind of thinking doesn’t apply.

This is one of several reasons why I think that maybe I should have majored in math rather than comp sci.

I have some on-and-off trouble with scruples, which is a problem recognized in Catholic culture where you keep on feeling like you must have sinned when you haven’t, or like the sins you have committed are mortal when they really aren’t. One of the trains of thought that I always come back to whenever I’m dealing with this is that I’m probably just telling myself that what I did isn’t a mortal sin because I just want to take the easy way out. But then recently it occurred to me…

The right decision is always going to be easier than the scrupulous decision because the scrupulous decision is harsher than it needs to be by definition. So as long as I’m scrupulous, whenever I make the right decision I’m always going to feel like I’m taking the easy way out!!

So I guess that gives me a good diagnostic for when I’m acting scrupulous. If I start worrying about whether I’m taking the easy way out, then I can assume I’m just being scrupulous.

After watching 8-bit Music Theory’s video on nonfunctional harmony in Chrono Trigger, I feel like I finally understand the role of dissonance in composition for the first time.

I went through a pretty long phase where I refused to listen to anything but classical music, so my dad was surprised when I started listening to punk rock and such. But if you look at some of my favorite music from when I was a kid, it’s a pretty natural progression. Here are some of the first songs I remember liking when l was little:

As you can see, I’ve always been fond of fast beats and minor keys. Heck, even my favorite classical pieces are like that:

The horizontal line in this post editor doesn’t always look the same even though the HTML is the same, and it bothers me.