Random Number Generator

From A complete guide to Super Metroid speedrunning
Revision as of 17:30, 8 August 2022 by Strotlog (talk | contribs) (New wiki page about RNG)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.

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, bit 0 of rngN and bits 0-2 of rngN+1 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

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