There are some events in SMW that are not
consistent and seem to have no predictable pattern to the outside observer. These events are said to be luck-based. Examples of these are subpixels, speed oscillation,
and RNG. It is important to clarify that random number
generation, or RNG, is a subset of luck-based events, and that not all luck-based events
are driven by RNG. This video will focus only on this subset. In software and computing, RNG is used to
make events act random; however, the algorithm that generates these numbers is just another
piece of code, so the outcome is consistant and predictable if you look hard enough. SMW has four bytes in memory that relate to
the RNG output. They are $148B through $148E.
The first two bytes can be seen as the "seeds" which are used to create the second two bytes,
which are the actual output of the RNG routine. When a sprite needs to make a random action,
it calls the RNG routine which uses the current seeds to update the output and create new
seeds for the next call. The sprite can then use these two values to
decide what action to take. If it needs more than 2 bytes of randomness,
it can call the routine as many times as it needs. The RNG routine is actually very simple. SMW uses a relatively small amount of randomness,
so this routine fits the need well. This is the actual RNG routine, located at
$01ACF9 in the ROM. First I will explain this algorithm explicitly
in assembly terms, then I will provide a simpler walkthrough. But first, you should know what the ASL, BIT
and EOR instructions do. ASL stands for Arithmetic Shift Left, and
will shift the bits of the operand one space to the left, effectively doubling the number
contained in the register. The bit that was shifted out the left side
goes into the carry flag. BIT stands for Bit Test, and will set the
Z flag in the processor if the accumulator AND the operand equals zero. AND sets each bit of the result if the corresponding
bits of both of the operands are set. EOR stands for Exclusive Or, and will set
each bit of the result if the corresponding bits of each of the operands are different. You can also think of EOR as flipping the
bits of operand 1 where the bits in operand 2 are set. The registers used in this routine are our
RNG bytes, $148B through $148E, the index register Y, and the accumulator, A. The processor
flags C and Z are used as well. Suppose these are our four bytes prior to
the RNG call. Now I'll step through the routine to see how
this effects the output. In the first part of the routine, we see that
we load 1 into Y, call a subroutine, decrement Y to 0, call that same subroutine again, and
then return. This is because for each of the two output
bytes, the same seed bytes are used in succession. I'll only cover this subroutine once, but
do know that it is called twice for each of the two output bytes. First, we load $148B into A and shift it left
twice. We set the carry flag, and then add $148B
plus the carry into our result. We store A back into $148B, overwriting it. Then, we shift $148C left once in place. The bit that was shifted out gets placed into
the carry flag. Load the constant #$20 into A and bit test
it with $148C. The Z flag will get updated with this test instruction. Then, depending on the states of the C and
Z flags, we may or may not increment $148C in place. In this case, we don't. All of the flow paths merge on this instruction,
where we load the new value of $148C into A.
Then we exclusive or it with the value contained in $148B.
And finally, we store this result into the output register signified by Y. All of this happens again with the new seed
values and the second output byte. At the end of this routine, the seed bytes
were both "ticked" twice, and the output bytes were both "ticked" once. Additionally, the value of A already contains
the value of $148D, so you conveniently don't have to read the value again once the RNG
routine is called. After looking at this function for a while,
I have come up with a simpler way of thinking about it. We'll call the seed bytes S and T, and the
output bytes J and K respectively. Take S, multiply it by 5, add one, then store
that value back into S. Now take T. Look at bits 4 and 7. If they are equal, multiply T by 2 and add
one; otherwise, just multiply it by 2. Take the exclusive or of the new values of
S and T and put the result in K. Update S and T again using the same method
as before. Then take the exclusive or of the new values
of S and T and put the result in J. Leave the value J in the accumulator and return. If you do some analysis, you can find how
long until this routine will start repeating output. The value of S is defined by this recursive
formula. You can see that S_0 = S_256, so after 256
ticks of S, it will repeat. Since S is ticked twice per routine call,
S will repeat every 128 routine calls. The value of T is defined by this recursive
formula. You can see that T_0 = T_217, so after 217
ticks of T, it will repeat. Now since T is ticked twice per routine call,
it actually switches parity after one repeat, since the length of the sequence is odd. So T will only repeat every 217 routine calls. The output of the RNG routine is just the
exclusive or of S and T, so we can find when the output repeats by finding the least common
multiple of the lengths of the sequences of S and T. The factorization of 128 is 2^7,
and of 217 is 7 * 31. They have no common factors, so the LCM is
27776. Therefore, the output of SMW's RNG routine
will repeat after 27776 successive calls. And I have verified this by writing a small
Java program that emulates this routine and continues calling the RNG until it reaches
a repeated value. The RNG routine is available for any function
of the game to call. In practice, only sprites call the routine,
usually to determine what state they should spawn in or how to behave. Since the RNG values update each time the
routine is called, we can tell if some sprite is using RNG if the RNG registers are updating. Each currently loaded sprite may call the
RNG routine in its update routine. The sprites are updated in order of sprite
slots, starting at slot B and ending at slot 0. Very few sprites actually call the RNG routine
often, and most don't even touch it at all. It is also important to know that the four
RNG bytes are always set to zero when you exit a level. This means things that call the RNG routine
at the start of a level are likely to be consistant even though they are supposed to be random. For example, the first Dino-Torch will always
shoot fire upwards since the RNG value it uses will always be 05. Throughout the entirety of the game's code,
the RNG routine is only called 53 distinct times. So I have actually documented each call and
highlighted exactly how each RNG value is used. There are 3 categories of RNG calls: a call
when the sprite is spawning to give it a perminent attribute, a consistant call to provide a
continuous sequence of randomness, and a periodic call in response to a particular event occuring. The following sprites tick the RNG at least
once when they are initialized. The yellow Koopas use the random number as
its initial turn around timer. They can only turn around every 128 frames,
when their timer hits #$80 and #$00. This random value assigned to it allows the
Koopas to turn around at different points in time relative to when they were first spawned. See how the different RNG values result in
the Yellow Parakoopas to turn around at different times, despite Mario's identical movement. Reznor uses the value in a similar way, as
it can only shoot fireballs every 256 frames. This means that once you know the pattern
of fireballs being shot, you can predict when they will be shot the next time. The horizontally flying Parakoopas use this
value to determine the starting value of their flying timer. When the timer's bit 5 is set, it flies down,
otherwise it flies up. Because of this, Parakoopas have an interesting
range of flight, and their flight path through this range is dependant on RNG. The Fishbone and Eerie use the random number
as its initial animation timer. For whatever reason the animation cycle on
these guys starts differently if the RNG is different. The Bonus Game uses the value to determine
which symbol to put in the center. Interestingly, the star and mushroom both
have a 3/8 chance of occuring, but the flower only has 2/8. The table to determine this is actually 9
bytes long, but only 8 can be read since the index into the table is only 3 bits long. When something lands in lava, lava splash
particles are spawned, which each call the RNG routine twice to determine their trajectory
and how long they stay on the screen. Similarly, the flame particles that the Podoboo
give off call the routine once when they spawn to determine their trajectory. The Boo Cloud Ceiling will call the RNG routine
for each boo to determine its starting position on the screen. If we are in the first room of a level, the
positions will be consistant since the RNG values are reset when you exit a level. These sprites all tick the RNG at a constant
rate. Magikoopa, her magic, & Yoshi wings, all call
the RNG routine every 4 frames to determine where the sparkles will show up. Similarly, Princess Peach calls it every 8
frames, and the orb uses it every 32 frames for the same purpose. Monty Mole calls for RNG every frame to determine
whether or not to turn and face Mario, even if it is already facing Mario. This results in a chaotic movement pattern,
even when Mario is standing still. The candles in Ludwig's room and the fire
in Yoshi's House both call the RNG every 4 frames to determine which animation frame
to display. The candle flames present in castle backgrounds
call the RNG every frame for the same purpose. Spike Tops, Urchins, Hot Heads, Fuzzies, and
Sparkys call the RNG every single frame to determine whether or not to blink. Only the Hot Head can actually blink, but
the other enemies still tick the RNG since they share parts of code with Hot Head. Similarly, Fishbone, Bowser, and Peach all
call the RNG routine every 128 frames to determine whether or not to blink. The Boo Cloud Ceiling will call the RNG routine
every 8 frames to determine which Boo in the cloud should dive at Mario next. All of these sprites have a complex behavior,
and call the RNG routine at some point during their behavior cycle. Paragoombas, Podoboos, and Hopping Flames
call the RNG after they finish hopping to tell how long until they start hopping again. Hopping Flames, Footballs, and Cheep Cheeps
out of water call the RNG to determine how high their next jump will be. Magikoopa calls the RNG routine every time
she tries to appear in the level to pick a position on the screen and test whether that
is a good spot to stand. When her magic his a block, it calls the RNG
to determine what comes out of the block. Usually the blocks turn into yellow Koopas,
but there is a 9/256 chance of it being a thwimp, 8/256 chance of it being a coin, and
a 1/256 chance of being a 1up. The fireball, Cheep Cheep, Super Koopa, Bubble,
Dolphin, Eerie, and Parachuting Enemy generators all call the RNG routine to determine where
the next enemy will spawn. Chargin' Chuck will call the RNG to determine
how long he stays in his idle state every time he enters it. The large crusher calls RNG every time it
crushes to determine where it will positioned on the screen. The birds at Yoshi's House call RNG to determine
how many times it pecks before moving, the time it takes in between each peck, whether
to turn around or not, and how many times it jumps before pecking again. That's a lot of work for something that doesn't
have any effect on gameplay at all. Dino Torch calls the RNG to determine whether
to shoot fire up or sideways. The falling fire in the Bowser fight calls
the RNG to determine where the first fireball will show up. And finally, Wendy and Lemmy Koopa call the
RNG twice on every cycle to determine which pipes they will show up in, and to determine
what pose they will be in. In general, this video showed how the random
number generator works, using SMW as an example. Other games have their own RNG routines that
have different outputs, but the idea is still the same. Remember, RNG is not truly random since it
is software based (which is why it should be called Pseudo-RNG). In order to get something truly random, you
would need an implementation that is hardware-based. But then that is another piece of expensive
hardware that can fail, which is probably why a software implementation was chosen instead. Thank you for watching. If you would like to see some of my previous
videos, head over to my speedrunning channel where I uploaded a few more videos about Super
Mario World. If you enjoyed what you saw and would like
to support the channel and any future videos, considering becoming a patron over at patreon.com/rgmechex. Thank you again for watching!
This is such an interesting video! Any more like it?
Post of the week :)