And now I would like to tell you about that thing!
Long Version (shorter one at the end):
About 2 months ago, I was accepted into AGDQ 2023 (which I'm still amazed by even now) to run Pokémon Mystery Dungeon: Explorers of Sky with a cool category called Randomizer 10 Dungeon Blitz. If you're seeing this around when it was posted, the run is on January 8th, so consider checking it out!
Accepted into AGDQ 2023 woo!! See the schedule here.
One thing I really wanted to do to prepare was learn more about the game as a whole, so I planned to go investigate a bunch of things I was unfamiliar with so that I'd have some better well-rounded knowledge for the event. Even though I've run PMD and Pokémon a decent bit, I still don't really know all that much about the games beyond general knowledge things that are easy to pick up. (I'm sorry Hop I don't know my type matchups!!)
The first thing I looked into was how dungeons are generated in Pokémon Mystery Dungeon (well, at least for Rescue Team and Explorers, the later games are different from this and don't even get me started on Gates to Infinity, I watched a couple runs of that and then formulated a whole document describing how it uses a sort of puzzle piece pre-generated elements generation pattern but anyway this is besides the point). This ended up actually being the ONLY thing I looked into, because while I didn't realize it at the time (should've seen it coming tbh), the dungeon algorithm is an entire rabbithole of its own.
Investigating
If you've looked into PMD dungeon generation or ever been curious yourself, you've probably come across this video by TheZZAZZGlitch, who does a fantastic job breaking down the core elements of the algorithm and how it works. As cool as this is though, I wanted to know more about the subtleties, so I had to look further.
Digging deeper, there are some key resources you'll find:
-
pmdsky-debug - The central resource for debugging information to reverse engineer Explorers of Sky
-
dungeon-eos - A python implementation of the dungeon algorithm used as part of SkyTemple
-
Map generation - A document by End45 detailing the map generation process
-
Dungeon data - Another document by End45 detailing how dungeon-related data is organized and structured
and well, I guess if you look now, hopefully you'd find my own implementation too. I'm hoping all the work I've done will help make this information more accessible to anyone else who is interested in all this!
An image from SkyTemple, which includes a dungeon preview feature using the dungeon-eos implementation. This layout was produced with Beach Cave's generation settings.
The most integral things were by far pmdsky-debug and dungeon-eos. pmdsky-debug gave me the ability to see the great progress in reverse engineering work that people have done over the years, and dungeon-eos was a useful cross-reference so I could bounce back and forth as I figured algorithm details out. I'd also like to give an enormous thank you to UsernameFodder, who I contacted early on and who helped me learn so much as I went through this project.
Why was I even making the thing to begin with
You might be wondering why I'd want to go through all this work and effort to learn more about this. Well, first I was really hyperfocused and interested in it so of course I did, but I also definitely do this sort of thing a lot! I love making tools that helps people out, it's why I started programming to begin with.
My favorite part of speedrunning is glitch hunting and the exploration of mechanics, I think it's really fun to dive into all of the components that make a game be that game. I enjoy pushing those limits and obsessing over learning intricate details that not many people may look into otherwise. I believe that practice, learning, and discovery should be as easy as possible, and that if something is hard to do now, tools should be built to make it easier.
When I ran A Hat in Time, I felt the tools and overall control we had over the game was limited, so I learned to make a mod to empower runners to be able to use a bunch of commands to manipulate basically whatever they wanted. When I started running CrossCode, I found that it was difficult to efficiently practice things, so I learned to build mods there to make the process way better. I love doing this sort of thing, the process of learning how something works is thrilling to me (this applies to both speedrunning and programming).
The icon for one of my main A Hat in Time mods, Console Commands Plus.
So if you ask why I'd be willing to sift through about four thousand lines of python code, read a bunch of confusing decompiled code, while also learning a lot of web development stuff I've never done before, I'd probably just say "because it's awesome."
Making the thing
Making the tool, which I named Pokémon Dungeoneer (definitely in no similar naming scheme to any other Pokémon related tool whose name ends with Ranger and starts with Pokémon and whose developer helped a bunch in developing the web part of this), took about 2 months and is by far the largest project I've done so far!
The largest part of development was of course the dungeon algorithm itself, with the main file being about ~5500 lines. I wanted to make sure that every function was documented and could be matched up with prior reverse engineering work so that someone else could retrace my steps, so the actual code length is definitely a lot shorter.
Getting a real grasp on the algorithm code took a long while, as there are a whole bunch of components at work making everything happen. Grid Cells, Tiles, Floor Generation Status, various structs holding properties, arrays of directional offsets with confusing names, enums galore, and plenty more. dungeon-eos is also a bit hard to read, as all of the property names are obscured into array indices (mapping onto how the memory is actually laid out), so I had to bounce back and forth between it and the decompiled source to figure a lot of things out.
There were so many things I had to get right and understand before I would even have anything testable, which was quite menacing when you're talking about thousands of lines of code. Once I did though, it was very exciting and motivating to keep going all the way to the end. I put together an ASCII text map generator, that I used all throughout development and left in the release build so there would be an easy way to have meaningful map output to start from. (Oh yeah, I released the algorithm as an npm package as well, hoping it'll be handy if anyone else ever wants to use it!)
An ASCII representation of a dungeon layout produced by dungeon-mystery, using the Crossroads generator.
Once the algorithm was all set, making the website was where I got to enjoy a whole lot of short bursts of development for big results, as all of the pieces fell into place (no not like the Gates to Infinity dungeons!!!!).
A dungeon output produced in Pokémon Dungeoneer, using the Beach Cave generation settings.
One of my favorite features to add was the ability to move through generation steps. This allows you to walk through all of the key points in generation to see in what order things occurred, how things changed, and just how that final dungeon layout came to be!
This is a version of the previous image's dungeon output but earlier in generation. Generation steps allow you to walk through the whole process!
And that's the story! Well, minus any actual explaining of the dungeon algorithm, but I think that would deserve its own post...
I'm really proud of what I've been able to make, and I really appreciate all of the people who've helped me get there to make this a reality. I'm excited to continue making more ridiculously elaborate things like this in the future as well.
Short Version/Conclusion:
Ultimately, I went on a long, very fun journey and in the end I made a cool dungeon generation tool! If you like Pokémon Mystery Dungeon, you'll probably enjoy messing around with it.
You can find the tool here (sorry if you're a mobile person it's not really built for use there right now!): https://pokemon-dungeoneer.vercel.app/
If you're more interested in code stuff, the website repository is here: https://github.com/EpicYoshiMaster/pokemon-dungeoneer
Arguably the cooler part though is the actual dungeon algorithm implementation here: https://github.com/EpicYoshiMaster/dungeon-mystery
