Difference between revisions of "Random Number Generator"
| Line 1: | Line 1: | ||
{{Technical}} | {{Technical}} | ||
| + | |||
The '''Random Number Generator''' or '''RNG''' in ''A Link to the Past'' is a weak algorithm used to generate numbers for events. | The '''Random Number Generator''' or '''RNG''' in ''A Link to the Past'' is a weak algorithm used to generate numbers for events. | ||
| − | == Source == | + | == Source and explanation == |
| − | + | ||
<pre> | <pre> | ||
| − | + | 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 | ||
</pre> | </pre> | ||
| − | + | 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 ({{HEXA|0FA1}}) is always {{HEX|00}}. The RNG cache is also reset to {{HEX|00}} 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. | 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. | 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 | + | 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 {{B|<}}, and the RNG generates the values {{HEX2|13}}, {{HEX2|F7}}, and {{HEX2|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 {{B|<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 {{HEX2|16}}, {{HEX2|FA}}, and {{HEX2|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. | ||
[[Category:Tech]] | [[Category:Tech]] | ||
Latest revision as of 16:23, 23 July 2021
 | This article goes into very technical detail. The information is presented with the assumption that the reader has at least basic knowledge of hexadecimal, bitwise operations, SNES memory, and/or SNES assembly. |
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 . 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.
