Random Number Generator

From ALttP Speedrunning Wiki
Jump to: navigation, search

The Random Number Generator or RNG in A Link to the Past is a weak algorithm used to generate numbers for events.

Source and explanation

0DBA71    LDA.w $2137    ; This is a software latch that causes address $213C to update with the horizontal dot position of the scanning beam
0DBA74    LDA.w $213C    ; This loads the horizontal dot position of the scanning beam into the A register
0DBA77    ADC.b $1A      ; Add in the current frame counter
0DBA79    ADC.w $0FA1    ; Add in the previously generated RNG value
0DBA7C    STA.w $0FA1    ; Save the generated value to the RNG cache
0DBA7F    RTL            ; exit

The carry flag is never cleared before or during the routine, so an additional +1 may occur if the sum exceeds 255 at any point.

After a reset, the RNG cache ($0FA1) is always 0x00. The RNG cache is also reset to 0x00 after a save and quit, because it is near the sprite arrays, which are all cleared.

Analysis

From a mathematical standpoint, this function is not a strong function, even if the fact that it can only generate 256 values is ignored. It is, however, unpredictable enough in real-time that it will seem random enough. Even in a TAS environment, the nature of the horizontal pixel counter makes generating a specific value difficult; however, an understanding of how the number is generated makes creating a different value or generation time trivial without losing even a single frame.

In essence, the use of the horizontal pixel counter means that, in general, more work for the CPU means the function is called later, and the RNG values generated are different. The use of the frame counter means that waiting 1 or more frames may generate a different value, even without intermediate RNG calls.

All these conditions present a problem with multiple values per frame. As a simple example, imagine there is an enemy that moves in a random direction when it's spawned, either up or down. If the sprite generates an even number, it will move up; for odd, it will move down. Let's say that Link enters an area walking by holding <, and the RNG generates the values $13, $F7, and $5A. In this instance, enemies A and B move down, while enemy C moves up. Now imagine that Link enters the same area walking by holding <v. This provides the CPU slightly more work on that frame. Let's imagine it doesn't add a lag frame, but it does delay the first RNG call. Let's say it took 3 extra horizontal pixels for the first call. Nothing else changed this frame, so the work between each call is the same. Now the values are $16, $FA, and $5D. Now enemies A and B move up, while enemy C moves down. If we continue this example but imagine a change of only one variable (e.g. the RNG value is different, but the movement was the same), we'll notice that enemies A and B always move in the same direction, and enemy C always moves in the opposite direction of those 2. For a more random generation, the expected result is that every value is independent. From our understanding of the function, though, such a set of results is impossible.

tl;dr

The RNG routine is hard for a human to predict, but it's still not very good. The values are absolutely impossible to manipulate in real time.