dungeon-mystery
crossroads floor be upon ye
overview
- Project Name: dungeon-mystery
- Project Length: 100+ hours
- Start Date: October 2022
- Technologies: TypeScript, Ghidra
links
in short
dungeon-mystery is a TypeScript implementation of Pokémon Mystery Dungeon: Explorers of Sky's dungeon algorithm. It is built to replicate the original algorithm as closely as possible, while also being much more readable and useful as a reference. Despite this project being several years ago, I believe it is still one of my favorites.
the (long) story
For my other projects, I often begin with giving the technical specifics about the project itself. However, for this one, I think it's best we start with telling how it came about.
A HUGE thank you to sgtmug, who created this project's logo.
speedrunning mystery dungeon
Pokémon Mystery Dungeon: Explorers of Sky, or as I'll abbreviate it, PMD EoS, released for the Nintendo DS in 2009, was a game in the side Mystery Dungeon series to the Pokémon games. It was the enhanced version of its two sister games Explorers of Time and Explorers of Darkness, which were released in 2007. The game featured roguelite dungeon-crawling gameplay through procedurally generated floors called mystery dungeons in which you battled, explored, and adventured to uncover grand mysteries.
Without putting it lightly, it is one of the most fundamental games I have ever played. It is a game I care about to no end, and despite speedrunning it, reverse engineering it, and randomizing it, there is nothing I do that can ever change that fact.
I began peeking into the speedrun in late 2018, though things really started in November 2021 as I picked up running a special randomizer category called Randomizer 10 Dungeon Blitz. I became involved in community races for this unique category, and I ran it in several of Pokémon Speedrunning Diversity's marathons, back when it was still an active organization.
PMD is a very random game. In each floor, you're looking for a special tile that has the stairs, which allow you to progress to the next floor, and so on and so on. This means sometimes the very first room you spawn in has the stairs, and other times you wander the entire floor before finding them.
The category I was running, Randomizer 10 Dungeon Blitz, essentially takes the random aspects and turns them up to 11. The Pokémon you encounter are random, the items are random, the dungeon names are random, but perhaps most importantly, the layouts themselves are more random.
Each dungeon floor has a set of generation parameters which determines characteristics of its general appearance. While the floors ultimately will look different each time, these characteristics would normally be preserved. The Randomizer essentially means this aspect is gone. Thus, to be fast, it is advantageous to be able to identify the kind of floor you're in, to maximize your odds of finding the stairs.
awesome games done quick 2023
October 22, 2022.
My run of Pokémon Mystery Dungeon: Explorers of Sky Randomizer 10 Dungeon Blitz was accepted into AGDQ 2023. A Pokémon Mystery Dungeon game had never been in a mainline GDQ event before. The submissions were always too long, most mystery dungeon categories are 5+ hours due to the amount of cutscenes throughout them, in addition to just being long games. Randomizer 10 Dungeon Blitz solves this problem by reducing it to just 10 dungeons, no cutscenes, all gameplay, and pure chaos with a nice and neat 1 hour estimate.
It is with this context that I became very fascinated and interested in deep diving into the generation system behind PMD. The best place to start was a video by TheZZAZZGlitch which overviews the dungeon generation algorithms in Red/Blue Rescue Team, the games prior to Explorers. The algorithms between Rescue Team and Explorers are very similar, so generally knowledge for one applies to the other (though of course, not always).
However, I wasn't satisfied with just this general knowledge. I'm a programmer after all, I wanted to know the subtleties, the specifics. I wanted to know exactly how the dungeon algorithm worked.
down the rabbit hole
October 25, 2022.
Digging deeper, there are several resources you'll come across:
- pmdsky-debug - Central resource for debugging information to reverse engineer Pokémon Mystery Dungeon: Explorers of Sky
- dungeon-eos - A Python implementation of the dungeon algorithm used as part of SkyTemple
- Map generation by End45 - A document detailing the map generation process
- Dungeon data by End45 - A document detailing how dungeon-related data is organized and structured
Of these, the first two would be the most essential in helping me answer my curiosities.
pmdsky-debug was (and absolutely still is) a fantastic resource for the developing reverse engineering knowledge for Explorers of Sky. With it, you can actually start to look at reverse engineered code, with symbols and comments contributed by the community, and approach the dreaded mess that is assembly and decompiled C code with some confidence.
However, you can thank dungeon-eos for helping to encourage me to go through with this. It's an implementation of the algorithm in Python, which in theory is the exact thing I need. There's just one problem. It's really hard to read!!!
Like, surprisingly hard. Look at this image, can you tell me, without looking at any other context, even with the assistance of the comments, what this function does, what it is doing with the properties? Sure, you might be able to piece something together with the comments, but they're completely load bearing without any field names. It is incredibly ironic, that there are times where reading the decompiled C code is easier than this Python implementation.
Now to be completely clear, dungeon-eos is and absolutely was an invaluable resource for this project and my criticisms of it are only as motivation to build something that can improve upon these faults. I greatly appreciate the work that had been done to make it, and especially the efforts that were put towards helping to make it more readable!
the depths
It is here at this point that I was set upon a path without return. The things I worked on up until now were typically video game mods, usually tools to assist speedrunners and glitch hunters like myself. For A Hat in Time, it was Console Commands Plus, for CrossCode, it was cc-speedrun-utilities.
Well, for Explorers of Sky, it was much larger. I wanted my own implementation, complete, readable, functional.
...so how in the world do you do that?
October 28, 2022. (how was this all in the span of like a week)
It was clear that I needed help. I reached out to UsernameFodder, whose name I saw across several repositories in the resources I had found. They turned out to be the most important individual who I absolutely cannot thank enough.
The answers I sought could be found with the help of pmdsky-debug and Ghidra, a suite of reverse engineering tools.
With these tools, I'd be able to look directly at the reverse engineered code that lies at the heart of Explorers of Sky's dungeon algorithm. Since most of it was traversed territory, it thankfully meant that much of the code I'd be looking at already had symbols, so there would be sections that were pretty readable. Many other parts would be unintuitive to read, simply due to the nature of the code being decompiled, so there are many oddities and optimizations that obfuscate what is really going on.
Thankfully, that's where dungeon-eos is a really helpful asset, it meant that I could cross-reference code across both, and generally be able to interpret it into something that I could actually write in TypeScript. I had lots of back and forths with UsernameFodder as I traversed thousands of lines of code (with no exaggeration) towards an eventual finish line. Honestly, I was surprised at how much my motivation remained throughout the entirety of it, which was about 2 months of very hyperfocused and intense work.
B99F
The outcome of all of this work is dungeon-mystery, a repository with the goals of being a readable source for information on the functionality of the dungeon algorithm in Pokémon Mystery Dungeon: Explorers of Sky. How about we try that function one more time?
FIELD NAMES! COMMENTS! ENUMS! Honestly all things I take for granted if not for doing this. You might still not fully grasp what's going on here, but you at least stand a fighting chance. Now imagine that across thousands of lines of code.
You may notice the todo comment at the bottom, which is perhaps the most fun marker of a project like this. The nature of reverse engineering means you have to stop at some level of depth because otherwise you'd simply never be done, there's always more to find. Which in some sense, is the very core of Pokémon Mystery Dungeon.
You never know what you'll discover.
how it works
Okay okay, so I told the long story of how this project came about. Now what is dungeon-mystery?
dungeon-mystery is a complex and ambitious project with nearly 5,000 lines of code in its main file, dungeon.ts. It aims to be extensive and configurable, providing an npm package with maximum customization to unravel all of the mysteries held within. It also aims to be a source of knowledge, designed specifically to be read and assist others in understanding how the algorithm functions.
control
The first principle is Control. As a package, whoever is using it should be able to mess with the algorithm in just about any way they see fit.
Endless Configuration: Everything in the algorithm can be controlled via the parameters you pass into the provided GenerateDungeon function. This ranges from the amount of rooms, the type of layout, items, to even non-vanilla options like raising the chance of rooms merging together or fixing a couple notable algorithm bugs.
Debugging Map Function: You can use the built in CreateMapString function to create a simplified ASCII representation of the output provided by GenerateDungeon. It's handy for testing until you have something more robust for your project.
View Generation Steps: The most powerful aspect of this implementation. At key points in the algorithm of varying importance that I've went and identified, you can provide a callback which receives all of the current data present in the dungeon algorithm. This allows you to essentially see everything that's happening in the algorithm at a given time, and make cool visuals like above to see what's really happening!
readability
The second principle is Readability. I want other people interested in this same topic to have better resources to start from, as well as a trail to verify my work.
Of course, this starts with the documentation for the project, which helps with terminology and specifics on using the algorithm itself.
This goes deeper though, it also extends to the code itself. I'm grateful that the reverse engineering efforts have resulted in descriptions for many of the functions, which I've either used or adapted as I've learned more about the algorithm to provide heading comments for every single function.
The address at the top of the reference image refers to where this function can be found in the NA ROM of EoS, thus allowing you to go directly to the reverse engineered code if you so choose.
This extends to within the functions as well, often with explanations especially for oddities like some of the bugs that exist within the algorithm.
If you're curious, the particular bug in the screenshot is related to the Outer Rooms layout, which was already prone to generation failures in Rescue Team. The bug, which impacts the connectivity of the layout, means that the algorithm has to "get lucky" when generating extra hallways otherwise it will not be strongly connected. You can actually see this in action in TheZZAZZGlitch's video. It seems this was partially fixed for Explorers, but some issues still persist for grids with an x size of 2.