Difference between revisions of "Random Number Generator"

Revision as of 18:18, 8 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

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-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:

• 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

// 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();
    }
}