RNG: Difference between revisions
mNo edit summary |
|||
(11 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
'''RNG''' or '''Random Number Generator''' is the game's [https://en.wikipedia.org/wiki/Pseudorandom_number_generator pseudorandom number generator]. It allows the game can make things like dust movement seem random<ref>https://www.youtube.com/watch?v=MiuLeTE2MeQ</ref>. | |||
'''RNG''' or '''Random Number | |||
==Technical description== | ==Technical description== | ||
The RNG | The RNG consists of two parts: the evolution function (also known as the RNG function), and the seed. Whenever something (usually an [[object]]) wants to use the RNG, it calls the evolution function. The evolution function will read the seed, perform a series of mathematical operations on it, and return the new value of the seed. This means that the seed always reflects the last value that the RNG function returned. Because each object can load, unload, and use RNG multiple times per frame, the RNG function is often called an unpredictable number of times every frame. This makes the game's randomness often unpredictable even if you know the RNG function. | ||
===The RNG function=== | ===The RNG function=== | ||
Here is pseudocode of the RNG function. Note that it relies heavily on bitwise/binary operations, specifically the XOR operation. | |||
<nowiki> | <nowiki> | ||
set RNGSeed to 0 | |||
if ( | |||
function RNG: | |||
if RNGSeed is 22026: | |||
set RNGSeed to 0 | |||
set value A to (the last byte of RNGSeed) shifted to the left by 1 byte | |||
if | set value A to (value A) XOR (RNGSeed) | ||
if | |||
else | set RNGSeed to value A | ||
swap the bytes of RNGSeed | |||
return ( | set value A to (the last byte of value A) shifted to the left by 1 bit | ||
set value A to (value A) XOR (RNGSeed) | |||
set value B to (value A) shifted to the right by 1 bit | |||
set value B to (value B) XOR 1111111110000000 (binary) | |||
if the last bit of value A is 0: | |||
if value B is 43605: | |||
set RNGSeed to 0 | |||
else: | |||
set RNGSeed to (value B) XOR 0001111111110100 (binary) | |||
else: | |||
set RNGSeed to (value B) XOR 1000000110000000 (binary) | |||
return RNGSeed | |||
</nowiki> | |||
Here is a walkthrough. | |||
We begin with the seed set to, say, 64917. This is 1111110110010101 in binary.<br> | |||
First, this seed is not equal to 22026, so we don't set it to 0.<br> | |||
Each byte is 8 bits (1s or 0s), so the first byte of the seed is 11111101 and the last byte is 10010101. We set value A to the last byte 1001010, shifted to the left 1 byte. This means 1 byte of 0s are added onto the end. Value A now has the value 1001010100000000 in binary.<br> | |||
Now we XOR value A with the seed. XOR, or Exclusive Or, is a bitwise operation that acts on each bit in the numbers. It takes the corresponding pairs of bits in each number, and checks if they are the same or not. If they are the same, a 0 is put into a new number at the location the pair of bits both had in their original numbers; if they are not the same, a 1 is put. | |||
<nowiki> | |||
11111101 10010101 - seed | |||
XOR 10010101 00000000 - value A | |||
--------------------- | |||
01101000 10010101 - new number | |||
^ ^ 1 and 0 are different, so the new number has a 1 in this place. | |||
1 and 1 are the same, so the new number has a 0 in this place. | |||
</nowiki> | </nowiki> | ||
Value A is set to this new number. Then the bytes of value A are swapped and the seed is set to that, so the seed becomes 1001010101101000. | |||
The current state is:<br> | |||
- Seed: 1001010101101000<br> | |||
- Value A: 0110100010010101 | |||
The last byte of value A is 10010101, and shifting this to the left by 1 bit gives 100101010. Value A is set to that, so it becomes 0000000100101010. It's XORed with the seed again, and value A is set to the new value: | |||
<nowiki> | |||
10010101 01101000 - seed | |||
XOR 00000001 00101010 - value A | |||
--------------------- | |||
10010100 01000010 - new value A | |||
</nowiki> | |||
Now we declare value B, and set it to value A but shifted to the right one bit. Value A is 1001010001000010, so value B becomes 0100101000100001.<br> | |||
Value B is now XORed with the number 1111111110000000, which is a so-called "magic number": its purpose is not clear in the code. | |||
<nowiki> | |||
01001010 00100001 - value B | |||
XOR 11111111 10000000 - magic number | |||
--------------------- | |||
10110101 10100001 - new value B | |||
</nowiki> | |||
The current state is:<br> | |||
- Seed: 1001010101101000<br> | |||
- Value A: 1001010001000010<br> | |||
- Value B: 1011010110100001 | |||
The last bit of value A is 0, so we look at value B. In decimal, it is 46497, not 43605, so the seed will be set to value B XOR 0001111111110100. This is another magic number. | |||
<nowiki> | |||
10110101 10100001 - value B | |||
XOR 00011111 11110100 - magic number | |||
--------------------- | |||
10101010 01010101 - new seed | |||
</nowiki> | |||
Now we return the seed. 1010101001010101 in decimal is 43605, which is the expected result. | |||
===Description=== | ===Description=== | ||
[[File:RNG Graph.png|500px|right|A graph showing notable RNG values and | [[File:RNG Graph.png|500px|right|A graph showing notable RNG values and indices in SM64.]] | ||
The function has 65536 possible inputs and 65536 possible outputs. It is a bijection, meaning that every input maps to exactly one output and none repeat or are left out. The function forms two loops, one of length 65534 and one of length 2, but one of the if statements causes the cycle of 2 to lead back to the cycle of 65534. Oddly, the RNG value of 21674 at index 65113 loops back to index 0. This may be because this index's S1 value is equal to the previous RNG value for the first time, but that is no reason to prematurely end the loop | The function has 65536 possible inputs and 65536 possible outputs. It is a bijection, meaning that every input maps to exactly one output and none repeat or are left out. The function forms two loops, one of length 65534 and one of length 2, but one of the if statements causes the cycle of 2 to lead back to the cycle of 65534. Oddly, the RNG value of 21674 at index 65113 loops back to index 0. This may be because this index's S1 value is equal to the previous RNG value for the first time, but that is no reason to prematurely end the loop. The RNG index and value of 0 is set when the game powers on. | ||
=== Impossible RNG === | |||
Impossible RNG values are values that are theoretically legal within the game, but cannot be reached due to how the RNG values cycle. 1 set of these is a 2 value RNG loop (values 22026 and 58704) that has no lead-in's from the main loop. If you entered this loop somehow, it would send you back to the main loop almost immediately. The other set (indices 65114-65533) is caused by there being a manual check that resets the primary loop early. This leaves the latter part of the loop, after the reset, unreachable. Any other RNG is considered possible. | |||
==Cycling RNG== | |||
Because RNG indices loop from 0 to 65113 and back to 0 again, by looping through every RNG index Mario can reach any reachable RNG value. By making [[dust]], Mario can advance RNG 4 times per frame, which takes 9 minutes to loop. If objects are calling RNG, this time will be much faster. | |||
==Objects that call RNG== | ==Objects that call RNG== | ||
* | The following objects always call RNG under the given circumstances. | ||
* Dust calls RNG to determine its resultant [[angle]] and [[horizontal speed]]. Note that the dust itself calls RNG, not the [[dust spawner]]. | |||
* [[Goomba]]s call RNG to determine which direction to move when they do not see Mario. | * [[Goomba]]s call RNG to determine which direction to move when they do not see Mario. | ||
* [[Bob-omb]]s call RNG almost every frame to determine whether to [[blink]]. | * [[Bob-omb]]s call RNG almost every frame to determine whether to [[blink]]. If the value that they receive is less than 656, they blink. Otherwise, they don't. Taking into account impossible RNG, the chance of a Bob-omb blinking on a given frame is 0.0099785. | ||
* Although not an object, [[snow]] also calls RNG. | * Although not an object, [[snow]] also calls RNG. | ||
* [[Coin]]s from Bob-ombs, Goombas, [[Big Cork Box]]es, [[Cork Box]]es, [[Piranha Plant]]s, [[Bully|Bullies]], [[Chuckya]]s, [[Fly Guy]]s, [[Snowman|Snowmen]], etc... you name it, it calls RNG to determine angle, horizontal speed, and [[vertical speed]]. | * [[Coin]]s from Bob-ombs, Goombas, [[Big Cork Box]]es, [[Cork Box]]es, [[Piranha Plant]]s, [[Bully|Bullies]], [[Chuckya]]s, [[Fly Guy]]s, [[Snowman|Snowmen]], etc... you name it, it calls RNG 3 times to determine angle, horizontal speed, and [[vertical speed]]. Since angles are shorts just like RNG, the RNG value is used directly for the angle. Horizontal speed is set to (RNG / 65536) * 20, and vertical speed is set to (RNG / 65536) * 40 + 17. Since these RNG calls must be contiguous, there are still only 65114 possible coin trajectories. | ||
* [[Bowser]] calls RNG to determine which attack to do next. | * [[Bowser]] calls RNG to determine which attack to do next. | ||
* And many, many, many, | * And many, many, many more. | ||
===[[Tick Tock Clock]] Random Setting Only=== | |||
The following objects call RNG under the given circumstances when the clock was entered at 6 (the random setting). Click on the link for more details. | |||
* [[Spinner#Random Setting|Spinners]] | |||
* [[Cogs]] call RNG twice when they reach their target [[angular velocity]] (TAV)<ref>https://www.youtube.com/watch?v=S0q3_toE3b4</ref>. The cog approaches its TAV with an angular acceleration of ±50AU/frame². The first call determines the cog's next TAV. Because of the way the formula is structured, there is a possibility that the TAV is 0. If this occurs multiple times, the cog can stand still. The TAV is calculated by the following formula: | |||
<nowiki>Target Angular Velocity = (RNG % 7) * 200</nowiki> | |||
The second RNG call determines the sign of the TAV. If the result is less than 32768, the sign is -1, and 1 otherwise. | |||
The following table summarizes this information: | |||
{| class="wikitable" | |||
|- | |||
! RNG1 % 7 !! 0 (14.313358%) !! 1 (14.265749%) !! 2 (14.278035%) !! 3 (14.281107%) !! 4 (14.282643%) !! 5 (14.284179%) !! 6 (14.284929%) | |||
|- | |||
| '''RNG2 < 32768 (50.016893%)''' || 0 (7.1551433%) || -200 (7.1274995%) || -400 (7.1413214%) || -600 (7.1490002%) || -800 (7.1443929%) || -1000 (7.1505360%) || -1200 (7.1490002%) | |||
|- | |||
| '''RNG2 ≥ 32768 (49.983107%)''' || 0 (7.1582148%) || 200 (7.1382498%) || 400 (7.1367141%) || 600 (7.1321068%) || 800 (7.1382498%) || 1000 (7.1336425%) || 1200 (7.1459287%) | |||
|} | |||
==References== | |||
<references /> | |||
[[Category:Mechanics]] |
Latest revision as of 01:03, 21 March 2020
RNG or Random Number Generator is the game's pseudorandom number generator. It allows the game can make things like dust movement seem random[1].
Technical description
The RNG consists of two parts: the evolution function (also known as the RNG function), and the seed. Whenever something (usually an object) wants to use the RNG, it calls the evolution function. The evolution function will read the seed, perform a series of mathematical operations on it, and return the new value of the seed. This means that the seed always reflects the last value that the RNG function returned. Because each object can load, unload, and use RNG multiple times per frame, the RNG function is often called an unpredictable number of times every frame. This makes the game's randomness often unpredictable even if you know the RNG function.
The RNG function
Here is pseudocode of the RNG function. Note that it relies heavily on bitwise/binary operations, specifically the XOR operation.
set RNGSeed to 0 function RNG: if RNGSeed is 22026: set RNGSeed to 0 set value A to (the last byte of RNGSeed) shifted to the left by 1 byte set value A to (value A) XOR (RNGSeed) set RNGSeed to value A swap the bytes of RNGSeed set value A to (the last byte of value A) shifted to the left by 1 bit set value A to (value A) XOR (RNGSeed) set value B to (value A) shifted to the right by 1 bit set value B to (value B) XOR 1111111110000000 (binary) if the last bit of value A is 0: if value B is 43605: set RNGSeed to 0 else: set RNGSeed to (value B) XOR 0001111111110100 (binary) else: set RNGSeed to (value B) XOR 1000000110000000 (binary) return RNGSeed
Here is a walkthrough.
We begin with the seed set to, say, 64917. This is 1111110110010101 in binary.
First, this seed is not equal to 22026, so we don't set it to 0.
Each byte is 8 bits (1s or 0s), so the first byte of the seed is 11111101 and the last byte is 10010101. We set value A to the last byte 1001010, shifted to the left 1 byte. This means 1 byte of 0s are added onto the end. Value A now has the value 1001010100000000 in binary.
Now we XOR value A with the seed. XOR, or Exclusive Or, is a bitwise operation that acts on each bit in the numbers. It takes the corresponding pairs of bits in each number, and checks if they are the same or not. If they are the same, a 0 is put into a new number at the location the pair of bits both had in their original numbers; if they are not the same, a 1 is put.
11111101 10010101 - seed XOR 10010101 00000000 - value A --------------------- 01101000 10010101 - new number ^ ^ 1 and 0 are different, so the new number has a 1 in this place. 1 and 1 are the same, so the new number has a 0 in this place.
Value A is set to this new number. Then the bytes of value A are swapped and the seed is set to that, so the seed becomes 1001010101101000.
The current state is:
- Seed: 1001010101101000
- Value A: 0110100010010101
The last byte of value A is 10010101, and shifting this to the left by 1 bit gives 100101010. Value A is set to that, so it becomes 0000000100101010. It's XORed with the seed again, and value A is set to the new value:
10010101 01101000 - seed XOR 00000001 00101010 - value A --------------------- 10010100 01000010 - new value A
Now we declare value B, and set it to value A but shifted to the right one bit. Value A is 1001010001000010, so value B becomes 0100101000100001.
Value B is now XORed with the number 1111111110000000, which is a so-called "magic number": its purpose is not clear in the code.
01001010 00100001 - value B XOR 11111111 10000000 - magic number --------------------- 10110101 10100001 - new value B
The current state is:
- Seed: 1001010101101000
- Value A: 1001010001000010
- Value B: 1011010110100001
The last bit of value A is 0, so we look at value B. In decimal, it is 46497, not 43605, so the seed will be set to value B XOR 0001111111110100. This is another magic number.
10110101 10100001 - value B XOR 00011111 11110100 - magic number --------------------- 10101010 01010101 - new seed
Now we return the seed. 1010101001010101 in decimal is 43605, which is the expected result.
Description
The function has 65536 possible inputs and 65536 possible outputs. It is a bijection, meaning that every input maps to exactly one output and none repeat or are left out. The function forms two loops, one of length 65534 and one of length 2, but one of the if statements causes the cycle of 2 to lead back to the cycle of 65534. Oddly, the RNG value of 21674 at index 65113 loops back to index 0. This may be because this index's S1 value is equal to the previous RNG value for the first time, but that is no reason to prematurely end the loop. The RNG index and value of 0 is set when the game powers on.
Impossible RNG
Impossible RNG values are values that are theoretically legal within the game, but cannot be reached due to how the RNG values cycle. 1 set of these is a 2 value RNG loop (values 22026 and 58704) that has no lead-in's from the main loop. If you entered this loop somehow, it would send you back to the main loop almost immediately. The other set (indices 65114-65533) is caused by there being a manual check that resets the primary loop early. This leaves the latter part of the loop, after the reset, unreachable. Any other RNG is considered possible.
Cycling RNG
Because RNG indices loop from 0 to 65113 and back to 0 again, by looping through every RNG index Mario can reach any reachable RNG value. By making dust, Mario can advance RNG 4 times per frame, which takes 9 minutes to loop. If objects are calling RNG, this time will be much faster.
Objects that call RNG
The following objects always call RNG under the given circumstances.
- Dust calls RNG to determine its resultant angle and horizontal speed. Note that the dust itself calls RNG, not the dust spawner.
- Goombas call RNG to determine which direction to move when they do not see Mario.
- Bob-ombs call RNG almost every frame to determine whether to blink. If the value that they receive is less than 656, they blink. Otherwise, they don't. Taking into account impossible RNG, the chance of a Bob-omb blinking on a given frame is 0.0099785.
- Although not an object, snow also calls RNG.
- Coins from Bob-ombs, Goombas, Big Cork Boxes, Cork Boxes, Piranha Plants, Bullies, Chuckyas, Fly Guys, Snowmen, etc... you name it, it calls RNG 3 times to determine angle, horizontal speed, and vertical speed. Since angles are shorts just like RNG, the RNG value is used directly for the angle. Horizontal speed is set to (RNG / 65536) * 20, and vertical speed is set to (RNG / 65536) * 40 + 17. Since these RNG calls must be contiguous, there are still only 65114 possible coin trajectories.
- Bowser calls RNG to determine which attack to do next.
- And many, many, many more.
Tick Tock Clock Random Setting Only
The following objects call RNG under the given circumstances when the clock was entered at 6 (the random setting). Click on the link for more details.
- Spinners
- Cogs call RNG twice when they reach their target angular velocity (TAV)[2]. The cog approaches its TAV with an angular acceleration of ±50AU/frame². The first call determines the cog's next TAV. Because of the way the formula is structured, there is a possibility that the TAV is 0. If this occurs multiple times, the cog can stand still. The TAV is calculated by the following formula:
Target Angular Velocity = (RNG % 7) * 200
The second RNG call determines the sign of the TAV. If the result is less than 32768, the sign is -1, and 1 otherwise.
The following table summarizes this information:
RNG1 % 7 | 0 (14.313358%) | 1 (14.265749%) | 2 (14.278035%) | 3 (14.281107%) | 4 (14.282643%) | 5 (14.284179%) | 6 (14.284929%) |
---|---|---|---|---|---|---|---|
RNG2 < 32768 (50.016893%) | 0 (7.1551433%) | -200 (7.1274995%) | -400 (7.1413214%) | -600 (7.1490002%) | -800 (7.1443929%) | -1000 (7.1505360%) | -1200 (7.1490002%) |
RNG2 ≥ 32768 (49.983107%) | 0 (7.1582148%) | 200 (7.1382498%) | 400 (7.1367141%) | 600 (7.1321068%) | 800 (7.1382498%) | 1000 (7.1336425%) | 1200 (7.1459287%) |