How I reverse engineered the Super Metroid map with brute force.
Super Metroid is an adventure game where you are tasked with exploring a giant, interconnected world. The game helps you out by mapping your progress automatically as you explore.
The areas you have visited are stored in the game's save file. This section of the save is about 1kb in size, and each individual bit tracks one cell of the map. If Samus has visited 10 screens in the game, 10 bits will get flipped to 1.
I am building a Super Metroid website where you load your save file, and it will show you where you have been, and offer hints for things you have missed. So, I needed to know which part of the map each of these bits corresponds to.
The BizHawk emulator
BizHawk is an emulator that is targeted at creating tool-assisted speedruns, commonly called a "TAS". A TAS is a script that enters in game inputs as if a human was playing the game, with the goal of beating the game as fast as possible. Since each input is precisely crafted, a TAS can often do amazing things.
BizHawk has a Lua scripting engine embedded in it to aid in TAS creation. By writing a Lua script, you can control every aspect of the emulator. I used this scripting capability to brute force dump the entire map of the game.
Dumping the map, bit by bit ...
I wrote a Lua script that sets a single map bit to 1, starts the game, presses the start button until the map is displayed, takes a screenshot, then moves onto the next bit.
Here is one of the screenshots
The pink area is the bit of the map that was discovered, and the white box is Samus's current location, which will be one of the 20 save rooms in the game. BizHawk allows me to alter the emulator's memory, so I use this to set up the save file exactly how I need it. Since I know Samus's location, I can then figure out the global location of that cell of the map.
The save rooms and the in-game map
Super Metroid's world is divided into different areas, such as Crateria (where you first start the game) or Tourian (where you find the final boss). When you look at the in-game map, it will only show you parts of the map that are in the area you are currently in. So in other words, if you are currently in Crateria, then the in-game map won't show you Tourian or any other regions of the world.
There are 20 save rooms in the game, and it's simple to place Samus at one room by altering the save file. So when I do a dump run, I can only get the bits that correspond to whatever region I have placed Samus in.
This takes a while
There are 1,284 bytes in the map section of the save file, meaning there are 10,272 bits that could each mean one cell of the map. Each run of the Lua script takes about 11 seconds on my laptop. So a single dump takes about 31 hours to complete.
But, this really isn't as bad as it sounds. I let the dump do its thing while I work on other parts of the website in parallel. I also don't need to do a dump from all 20 save rooms, I can strategically pick rooms based on how much of the map they can reveal. Also, once I know a bit, I can skip examining that bit in future runs. And finally, I can run three dumps at once, since my laptop has four cores. Thankfully I have another computer as well so the laptop just sits in the corner chugging along.
After a few days of dumping, I have determined this much of the map
The bright areas are the parts I have successfully mapped. The faded back areas are the parts of the map that still need to be determined.
Dump update (Sept 26, 2021)
I figured I'd show where I'm at after doing one more dump run (31 hours in total, 3 dumps running in parallel)
Really happy with the progress. Sadly though I think this approach is starting to reach its limit (see "Limitations" just below). I will need to resort to more intricate approaches to get those last areas of the map.
This approach takes "snapshots" of the map from save rooms. There are parts of the map that have no save rooms nearby, most notable the right side of Crateria.
I think the way to address this is to start the emulator, and manually walk Samus over to the correct spot. Once she is situated ideally, grab a save state of the emulator. Then my script can restore the save state before each dump. This will instantly place Samus at the correct spot for each dump, saving a lot of time and hassle.
Other nerdy game stuff
Thanks for reading. If you found this interesting, here are some other articles I wrote that you might like
- Extracting Neo Geo emulator graphics data to create animated gifs
- The Sega Saturn and transparency
- Squeezing the Arduboy for every byte