Difference between revisions of "Random Number Generator"

Latest revision as of 00:11, 9 August 2022

Super Metroid's random number generator (often referred to as RNG) is implemented as a simple Pseudorandom number generator.

A new random 16-bit number is generated every frame of gameplay, and 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.

See also: RNG1 - various RNG usage notes

RNG loops

Most RNG interactions are to fetch the next number. When this happens over and over, the RNG gets into its "main loop" where the numbers start repeating every so often: specifically, once the main loop is entered, only 2280 16-bit RNG values are possible under normal conditions.

The following manipulations overwrite the 'last generated RNG value' aka 'seed' at $05E5 with a new value that didn't come from the RNG itself. This effect either temporarily or permanently breaks the RNG out of the main loop.

• Enter a room with a beetom in it. Temporary new seed - leads back to main RNG loop.
• Enter a room with a sidehopper in it. Temporary new seed - leads back to main RNG loop.
• Enter a room with a polyp in it. This action sets a non-temporary new seed that would lead to a different RNG loop - but in vanilla SM, the new seed always gets changed by XBA RNG happening in the same room (see next point), so this manipulation is not effective.
• Process a frame in a room with XBA RNG - that is, acid or lava. Aside from memory corruption techniques, XBA RNG is the only known means of permanently breaking out of the vanilla RNG main loop. RNG becomes more random, and non-looping, while in the room. Then, after the player leaves the XBA RNG area, depending on the last XBA'ed seed, the RNG can enter main or non-main RNG loops.

The main RNG loop has some not-fully-random properties such as sometimes knocking 1-2% off the official PB drop rate of an enemy.

Some RNG loops smaller than the main loop are known to exist via XBA, which can more heavily skew the results of random processes in the game.

14% SuperChargeless page describes a way to intentionally change RNG loops.

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.

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%
• 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 Phantoon's design.

C implementation

// 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(0x0011); // polyp - but rooms with polyps also change the RNG value
    // seed(0x0017); // beetom
    // seed(0x0025); // sidehopper
    seed(0x0061); // reset game

    // 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 < 1e4; i++) {
        printf("%d\n", g_rng);
        proc();
    }
}