RNG Algorithm
Introduction
Zelda 2 uses a single RNG algorithm for most "random" elements in the game. Anything requiring random behavior is chosen using different bits of this sequence to determine what action is performed. Examples include which overworld pattern to spawn, when a Bot jumps at or away from Link, or where on the screen Carrock will teleport to during each hop.
The RNG sequence is 9 bytes long in RAM, from address $051A through $0522.
Algorithm
Computation
Think of the RNG sequence as a giant string of 1's and 0's, 72 digits long.
- Take bit 6 from $051A (7th bit in the string of numbers)
- Take bit 6 from $051B (15th bit in the string of numbers)
- Perform XOR operation on these two numbers - if both are 0 or both are 1, result is 0; if one of each, result is 1
- Prepend this result value to the beginning of the string of numbers and shift everything else over to the right
- Next frame, do this again with the new values
This sequence is recomputed every frame (except lag frames).
Re-seeding
To further randomize the sequence, the entire sequence is re-seeded periodically throughout the game. These re-seeds happen just as Link transitions to a new side-scrolling screen. Moving about on the overworld or exiting a cave/town/palace does not prompt a re-seed, but entering a cave/town/palace or any screen transition within these areas do cause a re-seed to occur.
The re-seed replaces whatever is in $051A (the first 8 numbers in the string) with hex digits 0xA5, or the binary digits "10100101". Presumably this is because this value consists of a random mix of 1's and 0's. Regardless of the reasoning, it effectively decapitates the normal sequence and re-randomizes it each time the screen transitions.
Implications
- Any manipulation based on RNG algorithm requires frame perfect play from game start, since the re-seed mechanism is destructive in nature.
- There are actually only 128 total RNG sequences in the entire game.
- Since the algorithm only evaluates the 7th and 15th bits in the full string, the entire string will be deterministic based only on the values of the first 15 bits.
- Furthermore, we know that the re-seed sets the first 8 bits to "10100101" and are therefore always the same at the beginning of each screen transition.
- Hence, we can classify every RNG sequence possible based on this starting value and the next 7 digits being random, in other words 128 total possibilities.
Resources
- riiyak's Video Explanation (timestamp 1:06) - https://www.youtube.com/watch?v=Hbe3JqWdVd4&t=66s
- riiyak's RNG sequence database - File:Zelda2 rng sequences.zip
- CF207 RNG and Overworld Spawns - https://www.twitch.tv/videos/370452496
