How classic games make smart use of random number generation

How much thought have you put into the nature of randomness in your game? May I suggest taking a moment and considering it, its nature, and how it could go wrong?

There are some people who don’t think games should be random, or that die rolls at least should play a minimal role. Put all the information out there for the player. If an attack works, it should be definite; get the uncertainty out of it. In an action game, if you point at a player with a gun and pull the trigger, if your aim was true, the target should be hit. No random drift or aiming stat should interfere.

Then there are some who, so concerned are they about people’s misconceptions about what it means to say an attack is 90 percent likely to hit, actually fudge the math, and roll the dice so that it actually means the attack is more like 98 percent likely to hit.

There are few computer games that use what we would call true randomness. In our macro-scaled, Newtonian world, randomness is actually rare. When we roll dice, the outcome is determined largely when the solids leave our hand. What we substitute for randomness is, in actuality, ignorance. We don’t know the consequences of the motion vectors of the dice as they sail through the air, nor how they’ll react when they strike the table, how they’ll tumble and come to rest. Good enough for Monopoly.

You can access true randomness at quantum scales, but this is generally out of reach through conventional electronics. The issue is of enough importance that some Unix-based systems actually maintain a pool of “entropy,” gathered through sources such as the precise timing of user inputs, as an OS-level service, making it available to programs on request. These requests are important enough that they can be set to block, pausing the requesting process, until enough entropy is generated (like through pressing keys or moving the mouse around) to satisfy them. Those are usually intended for cryptographic use.

Less important requests are usually made up for through other methods. Most of the time, what we have to work with in entertainment software are pseudo-random number generators, which are well-understood, supplied with most compilers through standard libraries, and if need be, can be implemented yourself.

And yet, particularly enthusiastic users, especially in the speedrunning community, have drawn attention to these lowly workhorses. They're well worth studying if you're a game maker thinking about how (or if) to implement RNG in your own game; with that in mind, here are three notably different game RNGs, their natures, how they’re used, and in a couple of cases how they’ve been exploited.

Final Fantasy I: Reading sequentially from a list of pre-generated numbers

The original Final Fantasy, and a few other early Square Famicom games, were programmed by Nasir Gebelli, a legendary 8-bit programmer who made a name for himself on the Apple II. The Apple II and Famicom are both 6502-based machines, so Gebelli came to the system with an assortment of tricks under his belt.

One of them is that its encounter random generation is mostly handled by walking up or down through a preset table of 256 values stored in ROM. The index is updated every step (going up or down according to a convoluted process), and the value pointed to compared to a threshold value. If the value is beneath the threshold, an encounter is generated.

Essentially this system is a list of randomish numbers that get reused again and again. The index, notably, is reset when the system is reset.

This is not the original Final Fantasy’s only RNG. During battles, when a die roll is needed, a similar system is used, with a completely different table of 256 randomish values, although this one is read sequentially. Unlike the encounter generator’s index, this one is saved in the battery-backed RAM, meaning, among other things, if you have an encounter after loading a save in a given area, reload the game, then have an encounter in the same area, it will be the same group of enemies, with the same surprise determination.

Interestingly, while the state of the battle random generator (its seed) is saved on the battery-backed RAM, it is not tied to any player’s save file.

After a battle begins, the battle engine does a fairly smart thing. Every two frames, the game calls the random number function but doesn’t use the result, advancing the table to a difficult-to-predict place.

We could call this kind of act, generating numbers not for their values but just to advance the generator, “spinning” the RNG. When the player moves the cursor, the RNG is spun an additional time. The result ties the outcome of battle calculations to the timing of the player’s actions in a way that’s difficult to duplicate between plays. Although the encounter group and surprise status may be the same every time after loading a save, unless the player can duplicate his actions within a 30th of a second accuracy, the states will soon diverge.

That word, diverge, is important. Without outside access to allow it to behave otherwise, a computer program in one state will, provided proper operation, without fail progress along the same track. In an RPG, care must be taken so that a player cannot game the random number generator to create advantageous states. If you know ahead of time, for instance, that being in a given area will result an unwanted encounter, you could arrange, just for that step, to be in a different encounter zone. You could even use this to shop around, and find the encounter zone that produces the best opponents for your fight.

The only way to get out of this, to diverge from this state, is to obtain some outside value, some external source of entropy, that the program can use to vary its running state. On the Commodore 64, the output of the noise oscillator on the sound chip, while not perfect, was often used as a good-enough source of entropy. Sometimes on the NES and SNES, a game will spin the RNG on some or all frames. Since the reactions to the player’s inputs would occur on different frames, over time this would cause the operation of the program to diverge more and more as the player’s behavior provides entropy to the system.

Systems with a real-time clock will often use a hash of that to initialize pseudo-random generators, although since usually the clock is settable by the player, that can also become a possible exploit. It’s most useful if the clock has a fine resolution, we’re talking milliseconds, since by taking the low digits of its value you can end up with a value that’s very hard for the player to usefully manipulate.

Back to Final Fantasy. This is all, for the most part, too fiddly to be taken advantage of by casual players, even if they could do the work to figure out the state of the random seed. But what if there is a particularly difficult encounter that a player might want to avoid, or perhaps trigger, for some reason?

In one room of the game, there is a legendary pseudoboss called Warmech. It appears in a room with a very high enemy encounter rate, but it is a member of enemy encounter group 8. The table the game reads from when determining random monsters does so by reading the low bits of a value, and the table is constructed so that only three values in the table will cause it to set up encounter group 8, meaning Warmech is generated only 3 times in 256 battles. If you know the state of the battle generator, you could engineer this encounter, forcing it to happen.

Speedrunners have analyzed all of this. At AGDQ 2017, runners Gyre and Feasel used these facts, and others, to keenly manipulate enemy generation, avoid high risk/low reward encounters, gain levels in an optimized way, and generally make a mockery of the idea of randomness. See it for yourself here.

Super Mario 64: Linear Congruential Generator

A popular source of pseudo-random numbers, provided that they don’t produce game-breaking effects if manipulated, is what’s called a linear congruential random number generator (LCRNG). It is worth looking that up on Wikipedia. The essence of a good LCRNG is a kind of counter that doesn’t count sequentially. Its value jumps around, yet it will still step through nearly all of its domain.

Basically you start with a seed value. You perform some basic arithmetic operations on it to get a result value, which is both returned to the caller and used to reseed the generator. You end up with a sequence of values that progresses forward from each possible seed. If you ever were to end up with a seed that, at some point, produces itself after some number of runs, you’d end up with a cycle. The result values would reoccur at the point where the seed reproduced itself. An RNG algorithm has to avoid these kinds of situations where possible. This is a reason that LCRNGs can make good RNGs: chosen well, they won’t cycle until they nearly exhaust their domain, and they’re quick both to implement and run using basic math.

Such a LFSR is used in Super Mario 64. Mario 64 expert pannenkoek, the guy who does the A-press challenge videos on YouTube, has an excellent explainer video that covers exactly how the game implements its RNG, complete with code. One artifact of its algorithm is that it cycles after 65,114 values. Since there are only 65,114 possible states for the RNG, the game’s randomness at any point can only proceed down one of 65,114 tracks. The game does not spin the RNG unnecessarily, so all uses for random numbers come from game entities that request them (one of which can be the player if he performs certain moves).

Pokemon Emerald: Bad seed behavior

Manipulating Final Fantasy’s RNGs can allow a player to dictate which enemies appear and when, but it takes a lot of work to do so. Mario 64’s single RNG can affect how coins spawn and enemies behave, which turns out not to be hugely breaking of that game. Pokemon games put their RNGs through more strenuous use.

When a Pokemon is generated, the resulting stats could hang around for a long time. Some of these stats are secret, hidden to the player, but have long-lasting effects. Being able to manipulate them could be fundamentally game-breaking, and because Pokemon can be traded between players, it could end up that it’s not just a single game that gets broken.

Because RNG is such an important part of the Pokemon series, the more recent games use particularly strong algorithms for their pseudo-randomness, like the Mersenne Twister. And because of the series’ popularity, players have gone quite far in their efforts to crack them. The interested reader is directed to Bulbapedia’s article on Pokemon RNGs and Smogon University’s page on Pokemon RNG exploitation.

One purpose of these manipulations is to try to obtain “shiny” Pokemon, which have no battle advantages but are extremely rare. In the Ruby/Diamond/Emerald series, the RNG is spun every frame, and twice as often in battle, not to mention by anything that requires randomness. The Smogon site has a whole page devoted to manipulating Emerald’s RNG, that game in particular because of an unusual flaw: on power-up, Emerald does not turn to the cart’s internal clock to seed its RNG, but always sets it to zero. The other games of its generation, Ruby and Sapphire, only do this if their clock batteries die.

Because the game’s RNG proceeds on a schedule from its seed (potentially advanced by other things on-screen which might spin the generator), it is the specific frame a Pokemon is generated on that determines if it is shiny or not.

Knowing which frame will generate a shiny Pokemon does not guarantee that the player will be able to get it generated, timing issues are precise and another consumer of randomness might eat that value, but having a target to work towards can greatly cut down on the work needed to get it. And since resetting the game resets the RNG seed to zero, instead of an indeterminate value, a player can try again and again, and, depending on the specifics, may have a much better chance at catching the elusive shiny Pokemon than the 1-in-8,192 odds most players have to suffer through.

Note that the program’s RNG utilizes both the generated Player’s ID and “secret ID,” which are stored in the save file and are not ordinarily changeable, in its calculations, so what might be a (relatively) easy catch on one save might require a lot of waiting around on another.

Another reason to manipulate, or more accurately predict, Pokemon Emerald’s RNG is to attempt to get a prodigy Pokemon with very high IVs. This has been studied enough by speedrunners to turn into a reliable exploit. For example, at AGDQ 2017 runner thetyrant14 used RNG manipulation to gain a starter Mudkip with high IVs that carried him through much of the game.