Random Number Generator - Revision history

Strotlog: Add RNG loops section

2022-08-09T00:11:58Z

Add RNG loops section

Strotlog: more accurate phantoon bug

2022-08-08T18:18:21Z

more accurate phantoon bug

Strotlog: New wiki page about RNG

2022-08-08T17:30:26Z

New wiki page about RNG

New page

Super Metroid's random number generator (often referred to as '''RNG''') is implemented as a simple [https://en.wikipedia.org/wiki/Pseudorandom_number_generator Pseudorandom number generator].

A new random 16-bit number is generated every frame of gameplay, and [[Drops|enemy drops]] and some enemy AIs generate further random numbers using the same method, intending that the same RNG value is not reused for multiple purposes on the same frame. Almost always, the random number generated is simply based on the previous random number that was generated. It's a mathematical formula with the previous result as its only input variable.

See C code below for the "formula". It's difficult to write in pure mathematical notation due to the carry bit.

== Phantoon's rare patterns ==

On 2nd round and onward, [[Phantoon]] selects his pattern side using the lowest bit of a newly generated random number, then selects his pattern speed (fast/mid/slow) using the lowest 3 bits of a second newly generated random number.

In the "main loop" number sequence of SM's PRNG algorithm, <code>bit 0 of rngN</code> and <code>bits 0-2 of rngN+1</code> are strongly correlated, making some pattern combinations wildly unlikely, but still possible:

* Left mid = 16/2280 = 0.70%
* Right fast = 8/2280 = 0.35%

Note, the 8 "main loop" RNG values that can produce a right fast are not evenly distributed in time among the 2280 possibilities; so there is a 11-12 second window every 37-38 seconds where generating a right fast is completely impossible.

However, the PRNG is good enough that bits 0-2 are evenly distributed overall; thus a fast pattern in general still happens about 25% of the time, as appears to be the design.

== C implementation ==

<nowiki>
// simulates SM generating 10,000 pseudo-random numbers

#include <stdio.h>

int g_rng;

void seed(int seed) {
g_rng = seed;
}

// implements/emulates $80:8111 Random number generator
void proc() {
int low;
int high;
int firstmul;
int secondmul;
int highaddition;
int carry;

low = g_rng & 0xff;
high = (g_rng & 0xff00) >> 8;
firstmul = low*5;
secondmul = (high*5) & 0xff; // SM code never reads the high byte of this particular multiplication's outcome

highaddition = secondmul + ((firstmul & 0xff00) >> 8) + 1;
if (highaddition >= 256) { // carry of 8-bit high addition operation gets added back to low
carry = 1;
} else {
carry = 0;
}

g_rng = ((((highaddition & 0xff) << 8) | (firstmul & 0xff)) + 0x11 + carry) % 65536;
}

int main(int argc, char ** argv) {
int i;

// seed(0x0017); // beetom
// seed(0x0025); // sidehopper
seed(0x0061); // reset game

// there are other seed values that can happen in quaking/lava rooms or something, which lead to a different loop of numbers ("small loop" and "medium loop").
// OTOH, beetom/sidehopper/reset all eventually lead to a loop of 2280 numbers ("main loop"), which may be larger than the uncommon loops.
// the numerical lead-up sequence ending when the main loop begins is listed at https://pastebin.com/sZCb5J9S for comparison

for (i = 0; i < 1e5; i++) {
printf("%d\n", g_rng);
proc();
}
}
</nowiki>

@@ Line 6: / Line 6: @@
 ''See also: [[RNG1]] - various RNG usage notes''
 == Phantoon's rare patterns ==
@@ Line 11: / Line 27: @@
 On 2nd round and onward, [[Phantoon]] selects his pattern side using the lowest bit of a newly generated random number, then selects his pattern speed (fast/mid/slow) using the lowest 3 bits of a second newly generated random number.
-Due to the PRNG algorithm's often adding an odd number to the previous result, two numbers generated in a row have a 99% chance of having different even-oddness (getting even-odd or odd-even). There are two Phantoon pattern combinations that actually require rolling even-even and odd-odd, respectively, thus making them wildly unlikely, but still possible:
+Due to the PRNG algorithm's often adding an odd number to the previous result, two numbers generated in a row have a 99% chance of having different even-oddness (getting even-then-odd or odd-then-even). There are two Phantoon pattern combinations that actually ''require'' rolling even-even and odd-odd, respectively, thus making them wildly unlikely, but still possible:
 * Left mid = 16/2280 = 0.70%
@@ Line 18: / Line 34: @@
 Note, the 8 "main loop" RNG values that can produce a right fast are not evenly distributed in time among the 2280 possibilities; so there is a 11-12 second window every 37-38 seconds where generating a right fast is completely impossible.
-However, the PRNG is good enough that bits 0-2 are evenly distributed overall; thus a fast pattern in general still happens about 25% of the time, as appears to be the design.
+However, the PRNG is good enough that bits 0-2 are evenly distributed overall; thus a fast pattern in general still happens about 25% of the time, as appears to be Phantoon's design.
 == C implementation ==
@@ Line 60: / Line 76: @@
      int i;
      // seed(0x0017); // beetom
      // seed(0x0025); // sidehopper
      seed(0x0061); // reset game
-     // there are other seed values that can happen in quaking/lava rooms or something, which lead to a different loop of numbers ("small loop" and "medium loop").
+     // there are other seed values that be brought on by lava/acid rooms, which can lead to a different loop of numbers.
      // OTOH, beetom/sidehopper/reset all eventually lead to a loop of 2280 numbers ("main loop"), which may be larger than the uncommon loops.
      // the numerical lead-up sequence ending when the main loop begins is listed at https://pastebin.com/sZCb5J9S for comparison
-     for (i = 0; i < 1e5; i++) {
+     for (i = 0; i < 1e4; i++) {
          printf("%d\n", g_rng);
          proc();