I play a ton of randomized Zelda: A Link to the Past. I probably average one game per week, especially now that there’s a weekly community race Reddit where competitors share the same seed. I’m not the fastest at completing it, but the original game is one of the greatest games of all time, if not the greatest. The randomizer adds so much depth and replayability on top of it.
ALttPR Background
A little background if you’re not familiar with ALttP(R) – the vanilla game has 216 possible findable items that can be located in chests, overworld locations, and NPC/shop giveaways. Some items are incredibly useful, like the Flute, which lets you call a bird to fly you around the overworld, or the Sword (it’s dangerous to go alone). Other items are less useful, like Pieces of Heart. Collect enough and your maximum health increases, but… don’t get hit, and you don’t need it. Some are almost completely worthless, like the single arrow. In the original game, the goal is to rescue Princess Zelda, which ends up meaning you need to do almost everything the game offers: defeat all three Light World dungeons, use the pendants found within to pull the powerful Master Sword from the pedestal in the Lost Woods, enter the Dark World, defeat all seven Dark World dungeons, and finally use the crystals within to open Ganon’s Tower and ultimately defeat him.
The randomized version flips this on its head. It defines logical rulesets about where certain items can be located and within that framework randomizes all the items within the game. For instance, the first chest in Link’s House could have the Hammer instead of the Lamp. Or it might have bombs. Or Rupees. Or a single heart. The ruleset defines how the items are laid out – for instance the Hammer will never be a dungeon reward for Palace of Darkness (the first Dark World dungeon) since progression through that dungeon requires the Hammer and that would be a logical contradiction. At times there’s also some “loosey-goosey” rules. As an example, the Lamp will never be found in the dark rooms beneath Hyrule Castle. That’s because you can’t illuminate the dark rooms without the Lamp! Of course, there’s nothing actually restricting you from being able to progress through a dark room, since it’s not really that difficult to memorize the layouts and just navigate directly to the chest. It just won’t contain the Lamp.
Frankly, the randomization algorithm is fascinating. It’s essentially building a network of inventory states linked to item locations and the human player is solving for the shortest path between the initial empty inventory state and the inventory state at which the goal can be completed (which is usually “defeat Ganon” but doesn’t have to be, there are others). This topic warrants an entire blog post all its own, but here’s a teaser of a 3-item acquisition network where the 3rd item requires the two others first.
The point is, the randomizer can follow this acquisition network and randomize item locations such that the seed is completable under different rulesets, which could require you to perform complicated glitches, sequence breaks, and other tricks to reach some locations.
Generating a Game
Let’s talk a bit how playing ALttPR actually works in practice. There’s a web tool available at https://alttpr.com/. You upload a headerless JP v1.0 Zelda 3 ROM, and the tool will run the randomization algorithm and spit out a new ROM compatible with most emulators and hardware.
You have a ton of customization options like Basic vs. Advanced item placement, glitch requirements, goal states, enemizer (enemies randomized), entrance shuffle (randomizes which doors go to which locations, if you’re a masochist), and Keysanity (dungeon keys can drop anywhere). You can also generate a Race ROM versus a Normal ROM. For us, this is where things get a little interesting.
Both options take you to a hashed ROM link so you can re-download the ROM file if you ever need to. If you selected a Normal ROM, there’s also a spoiler log. This log will tell you where every item in the game is located, and even includes a playthrough listing, which will show you a path through the item acquisition network that I described above. I’m not actually sure whether this is truly the shortest path through the game since the randomizer actually doesn’t build the network directly, it uses rule callbacks to decide where to place certain items. It’s not using something like breadth-first search on the network. Obviously, you don’t get this if you selected a Race ROM since it makes the race trivial.
Inspecting the Game
Here’s where the reverse engineering portion comes in. Let’s say you lost your spoiler link and you got stuck in a game of ALttPR. I think there’s possibly a tool somewhere deep on the internet that can find the ROM permalink, which will let you look at the spoiler (such as https://alttpr.com/en/h/xvJode5kyJ for a ROM I just generated).
Really, that’s overkill though. The item tables have to live in the ROM somewhere, so why can’t we just inspect it? That’s exactly what I did. I started scripting in Python to examine the ROM layout, and it’s fairly straightforward. There’s a couple item location tables, primarily between 0xE96E - 0xEDA8 (chests) and 0x180000 - 0x180161 (boss rewards and overworld items), with a few one-offs outside those tables (primarily NPCs and specialty items). Querying an item at a location is simple – give it a location memory address, read the value, map it to the item description.
with open("alttpr.sfc", "rb") as f:
rom = f.read()
loc = 0xE9BC
print(hex(rom[loc]))
#=> 0xF - Bombos Medallion
This works great! I added on some quality-of-life features, like searching for items which just iterates over the location table and finds all the items. I also converted this to Golang with a little CLI and a web GUI to make things simpler to use. But, fundamentally it’s all just read ROM -> map results.
Building Mudora
I’ve released this tool as Mudora. Mudora is the book item in A Link to the Past, and canonically it contains all the lore of Hyrule. In the original game, Link uses it to decrypt previously incomprehensible Hylian text to English. I think this is funny because it turns out the ROMs are actually encrypted in some cases.
You can check out Mudora here: https://alttpr-mudora.github.io/mudora
Race ROMs are Encrypted?!
Imagine my surprise when I finished the weekly race last week (which, remember, has no spoiler) and I wanted to know if I went as fast as possible. Specifially, I missed the Silver Arrows upgrade, an item that is normally required in the base game but is optional in the randomizer, provided you can perform a much more difficult and significantly slower technique to defeat Ganon at the end of the game.
Mudora displayed garbage! Most mapped to the UNKNOWN fallback value, and even when items were successfully read, there were either too few or too many of each item. I was really surprised by this because there’s really not that much going on in terms of the item tables I described above.
After much consternation I figured out what is happening. Race ROMs set a “tournament” flag that restructures some of the item tables and actually encrypts the values using XXTEA. This is purely an obfuscation method because the key has to be embedded in the ROM – how else would you decrypt it? It actually does this in multiple ways. As I mentioned before, there are several location tables to consider, and the encryption is performed differently or even not at all depending on which one you’re looking at. Let’s dive in.
Detecting Encryption and Key Acquisition
I mentioned that the Race ROM has a “tournament” flag set. We can detect this by reading two bytes at 0x180087 and seeing if either are non-zero. If so, we know the ROM has encrypted location tables and we’ll need to grab the encryption key. We read this as the little-endian 16 bytes starting at 0x1800B0. The same key decrypts everything, so we’re good to go.
I’m not going to go super in-depth how XXTEA decryption was implemented, just that we have the key and a known encryption algorithm so it’s fairly trivial to decrypt.
Decrypting the Chest Table (0xE96E - 0xEB63)
I need to talk about the chest table for a minute. I mentioned that it exists between 0xE96E - 0xEB63 and that is true regardless of whether the table is encrypted or not. However, the normal table is stride-3 and we really only care about the first byte in the stride. I actually don’t know what the other two bytes are used for in this table as it doesn’t matter to Mudora. So for instance, 0xE96E is the first item in the Sewers (the dark room colloquially referred to as “Dark Cross”), the second is not at 0xE96F but instead 0xE971 and is the Secret Passage chest, the third item is 0xE974 which is a Hyrule Castle chest, and so on. The table also consists of 168 locations, and we can verify this simply:
0xEB63 - 0xE96E = 0x01F5 (501)
// Addresses inclusive
0x01F5 / 3 + 1 = 0xA8 (168)
The encrypted table partially occupies the table starting at 0xEABC but the data is 168 contiguous encrypted bytes, encoded stride-1.
Decryption is easy, we can just pass over the 168 location bytes and decrypt them. After that, we need a mapping layer that converts a stride-3 address to a stride-1 location.
decrypted = [0xF, ...] # a table of 168 decrypted item values
chest_base = 0xE96E # original table base
chest_stride = 3 # original stride
# Index into the stride-1 table using a stride-3 address
n = (addr - 0xE96E) / 3
# If you want the converted address, add the new table base:
encrypted_base = 0xEABC
address = encrypted_base + n
# Index into decrypted items
item = decrypted[n]
Decrypting In-Place Tables (0x180000+)
Some of the tables operate much more simply. These are encrypted in place, so we don’t have to do the fancy table indexing. These values correspond to some of the overworld items, Heart Pieces, and boss rewards.
0x180000 - 0x180006
0x180010 - 0x180017
0x180140 - 0x18014A
0x180150 - 0x180159
Skipping Decryption
Some items aren’t encrypted at all. These seem to come from items you obtain from NPCs or from special fetch quests. There’s no real pattern to where these are found in the ROM so I’m sure the fact that they aren’t encrypted is just an oversight.
0x289B0 Master Sword Pedestal
0x2DF45 Link's Uncle
0x2EB18 Bottle Merchant
0x2F1FC Sahasrahla
0x330C7 Stumpy
0x33D68 Purple Chest
0x33E7D Hobo
0x348FF Waterfall Bottle
0x3493B Pyramid Bottle
0xEE185 Catfish
0xF69FA Old Man
Putting Encryption All Together
This is a big diagram but given what we already know, it should be pretty straightforward.
- Detect if we are dealing with encrypted item values by reading the flags at
0x180087. If we are, read the 16-byte encryption key. - If we’re not encrypted, there’s no address translation or item decryption. Simply read the address and lookup the item value at that location, mapping it to an item description.
- If we are encrypted, do one of three things depending on what address we’re trying to read.
- If in the chest table, perform the stride-3-to-stride-1 address conversion, read the value at the new address, and decrypt it.
- If we’re in an in-place table, read the value at the original address and decrypt it.
- if neither of the above, read the value at the orignal address and do not decrypt it.
That’s it!
Acknowledgments
This work would have been impossible without the work of others. I stand on the shoulders of giants.
- sporchia’s https://github.com/sporchia/alttp_vt_randomizer
- PHP randomizer code and web UI
- KatDevsGames’ https://github.com/KatDevsGames/z3randomizer
- Original randomizer written in assembly, laying out the encryption scheme
Mudora would not exist (or even need to exist) without the individuals above.
What’s Next?
Right now, Mudora is simply a ROM inspection tool. As I mentioned above the randomizer is really creating a computation graph for the human players to try to find the shortest path through (albeit with limited information). I think Mudora could solve this automatically, but it needs context for all the different rulesets that exist. Creating the item acquisition graph isn’t that complex, but dealing with all the configuration the custom rulesets introduce is a lot of overhead. As it stands, I believe ALttPR isn’t computationally difficult to solve, and I’d love to take a stab at it in the future.
That’s all for now. Thanks for reading!