Hi! My name is gkhan, and I'm a game developer with a background in mathematics, which means that there are few things that I love more in the world than randomness in games. It's a subject that I find endlessly fascinating and that I love reading and thinking about. Throughout the years I've gathered some stories about how games use (and misuse) randomness, and I thought I would share some of them. Most people would find this subject super-boring, but you guys all seem to be as crazily into games as I am, so I figured I'd write a blog post about it. I hope some of you will find this interesting!

To be clear: this article is specifically about randomness in games, so I'm going to leave out a lot of stuff. Randomness in cryptography, for instance, is a huge and complicated subject that wont be covered here.

Random and Pseudo-random

(this section is about how computers technically generate random numbers. Feel free to skip it if you're not interested, and you'll get to the fun parts about the Doom and Pitfall!)

Randomness is a surprisingly tricky subject for computers to handle, because computers are entirely deterministic machines. If you feed a computer program the same input, it will always produce the same output, every time. This is good because it means that you can always rely on your code to do what you want it to do, but when you need random numbers (and you very often do in games), it poses a problem.

How then do you solve it? The basic answer is two-fold: collect some small piece of randomness from "outside" the machine, and use what is known as a Pseudo-Random Number Generator to generate your random numbers. The small piece of randomness from outside the machine (properly known as "entropy") can be anything that the computer can't predict. The easiest thing to use (and by far the most common in non-cryptographic applications) is the current time. The code simply asks the computer what time it is, which is something that will be different every time you run the game. Some gaming machines (like the NES) didn't have internal clocks, so a common trick then is to use user input. You could, for instance, use the value "How many frames of the game had passed before the user pressed the 'start' button?".

That little piece of randomness is then used as a "seed" for your Pseudo-Random Number Generator ("PRNG"). A PRNG is basically just a mathematical formula that takes your seed value and uses it to start pumping out numbers that "look" random. They aren't actually really random, because the formula will always produce the same sequence given the same seed, but the numbers sort-of look random enough. There are some very complicated PRNGs out there, but I thought I'd give a quick example of a really simple (though a very common) PRNG, the Linear Congruential Generator. A random number generator of that type uses a formula that looks like this:

<next number> = (1103515245 * <previous number> + 12345) mod 2^31

("mod" here means that you take the first number, divide it by the second, and then take the remainder of that division).

So, if your seed number is 42, then your next number in the sequence is 1250496027. After that, you get 1116302264, and after that you get 1000676753, and on and on and on. Keep applying that formula and you have your steady stream of pseudo-random numbers.

(this formula, by the way, with those particular numbers, is the formula that glibc, a very common standard C library, which means that that particular formula is probably the most common PRNG in the world)

Why Doom has the worst pseudo-random number generator EVER

Doom is a technical masterpiece, and should be counted among the greatest achievements in the history of game development. It did, however, have an amazingly bad random random number generator, so bad, in fact, that it even affected gameplay. How did Doom's random number generator work? Well, instead of having a nice formula like the one in the previous section, it just had a list of 256 random numbers. That's it. Literally just a list of numbers. When a new random number was needed, it simply looked at the next value in the list, and used that. When it got to the end, it started from the beginning. If you're curious about what the list of numbers was, it's part of the Doom source code released in 1997 and can be seen here (it starts on line 32).

Now, some might argue "this is good enough, and the player will never know the difference", but the badness of the number generator actually affected gameplay. One of the most notable examples: it nerfs the BFG9000. The BFG heavily uses random numbers to calculate the damage, and it could hypothetically do up to 4280 damage. However, that will never happen in Doom, because there's literally no place on the random number generator table where that amount of damage can be inflicted.

Now, it's true that "max damage" BFG shot would be very unlikely even if it Doom had a proper PRNG, but even so, the fact that the PRNG is so poor means that the "window" of potential damage the BFG can do is much more narrow than the designers intended.

John Carmack, you are a brilliant developer giant among men, but you dropped the ball on this one!

Why No Man's Sky is just a gussied-up version of Pitfall

Another one of the great technical masterpieces in gaming history is Pitfall! for the Atari 2600, and unlike Doom it uses random numbers in an ingenious way.

If you're an expert Pitfall player, you might have noticed that the number of screens in the game is exactly 256 and no two are exactly alike. If you know your games, you might suspect that that number is no coincidence, and you'd be right.

256 is, of course, equal to 2^8, which is the number of possible values that can be stored in a single byte. A byte consists of eight "bits" that are either 0 or 1, and in Pitfall, each screen can be described by 8 bits. For instance, if a certain bit is 1 instead of 0, it might mean that there is water in the level. Another one might mean that there's an enterance to the lower world, or what enemies are on screen. That makes for exactly 256 different possible screens.

Since there are 256 possible screens in Pitfall, and you want to include all of them, the next decision you have to make is what order they come in. The easiest way to do that is to simply store the sequence of 256 screens as 256 numbers (much like how Doom did it, come to think of it), but that wasn't a possibility on the 2600. The reason for that is memory on the carts was extremely limited, and the entire game of Pitfall needed to be stored in just 4 kilobytes. A sequence of 256 one-byte numbers takes 256 bytes to store, which is equal (exactly) to a quarter of a kilobyte, a full 1/16th of the entire space on the cartrige! There was absolutely no way that was going to be possible, so David Crane, the programmer behind Pitfall, had to come up with a better way.

His solution was to basically use a random number generator to generate the sequence of screens. Instead of laying them out manually and storing the sequence on the cartridge, he instead just stored the formula for it. Since every cart had the same formula, it would always generate the same screens in the same order, but the order would look random enough for the world to be interesting. In this way, he was able to lower the amount of space the world map needed from 256 bytes to around 50 bytes, a huge savings.

(note for programming nerds: Pitfall doesn't use a classic random number generator like one of the ones I described above, it technically used a Linear Feedback Shift Register implemented as a polynomial counter. But the idea is more or less the same.)

Interestingly, this concept is incredibly similar to how No Man's Sky supposedly works. No Man's Sky isn't composed of screens, it's composed of planets, but just like each Pitfall screen is defined by an 8-bit number, each No Man's Sky Planet is defined by a 64-bit number, generated by a random number generator. And just like Pitfall had its random world "hard-coded" on the cartridge, No Man's Sky will have it's universe hard-coded on the disc, so that everyone is playing in the same "random" world. From a technical perspective, the concepts behind both games are remarkably similar, even though (of course) there's a massive difference in scale.

Breaking random number generators, for fun and profit

Random number generators can really screw you over when playing, so wouldn't it be nice to have a way to manipulate them so they always give you what you want? Every hit would be a critical, every drop legendary, and every romance attempt successful!

Unfortunately, it is almost impossible for regular humans to do, because it requires a detailed knowledge of the internal memory state of the game, and players don't have that. You know who does, though? Tool-assisted speed-runners, that's who!

A major component of a lot of tool-assisted speedruns is what's known as "luck manipulation", basically breaking the random number generator so that it always does what you want. A great example of this is this tool-assisted speedrun of the NES game Dragon Warrior:

Notice that from around 39 seconds into the video, the player embarks on a journey across the world, but he never runs into random encounters unless he wants to. And when he does, every hit is a critical, and every spell succeeds perfectly.

How does he do that? While I'm not privy to the exact technical details, what I think is going on is this: the game uses a random number generator that cycles (i.e. generates a new number) every frame. That number is used to determine how random events that frame are going to go (i.e. whether or not entering a tile triggers an encounter, or whether or not a hit is a critical). So, what the player does is that he always chooses his actions on frames where the random number generator works in his favor. That is, if combat would be triggered when entering a tile on a certain frame, simply wait a single frame for the random number generator to cycle, and do it the next frame instead.

It's interesting to note that the programmers could have mitigated this technique if they wished by only cycling the random number generator when necessary. That is, don't cycle the PRNG on every frame, only on every frame where the character enters a new tile. That way you couldn't avoid the curse of randomness in this simple way.

This might seem extreme (since only TAS-runners can exploit this, why would you care?), but it actually does solve a different way that players can manipulate the PRNG: save-scumming. XCOM: Enemy Unknown does a version of this by saving the state of the PRNG in the save file and only cycling it when a new random number is needed. That means that if you save just before taking an important shot and miss, reloading and trying again will not work. The random number generator will just spit out the same number again. What you have to do is force it to cycle, which in XCOM probably means making a move with a different character first. However, given the nature of XCOM, even that is a limited technique because of how limited the number of possible actions is each turn.

Links to interesting stuff

If you want to read more on this subject, here are some stuff that I like:

• Random vs. Pseudo-Random on the BBC show In Our Time. Do you want to hear 3 british academics discuss the philosophical and mathematical nature of randomness for 45 minutes? Of course you do!
• Doom wiki on the BFG. Discusses the damage calculations in more detail.
• David Crane's GDC talk on the development of Pitfall. Great talk if you're a programmer, though perhaps a bit boring if you're not :) The randomnessstuff starts at 22:20.
• A great page describing luck manipulation in tool-assisted speedruns, which is where I found that Dragon Warrior TAS

This thing became way longer than I expected, if any of you made it down here, I'm really grateful. I was thinking I might write some other stuff about game development concepts in history if you guys like this and are interested. For instance, an obvious part of randomness in games is procedural generation (how does Minecraft generate those nice-looking worlds?) and I was thinking about explaining how you actually do that practically.

If you have any questions about any of this stuff or any comments, I'd be happy to hear them. Cheers!

I'm fascinated by the legal implications of Blizzard real money auction house, and after thinking it through today, I can't imagine any way that they could do this and not run afoul of banking and stock market regulations. In the story about the real money auction house, Blizzard makes it very clear that they have no interest in becoming a bank, and is rigging the system so that you can't "store" money on their servers, and cash out at any time. This is the quote from the Jostiq article:  
 

If there's a legal issue at all, it's likely in the "cash out" option. Blizzard is transferring some of the responsibility to the third-party provider and, in order to do that, players will need to choose, right away at time of sale, whether they want to keep the money in Battle.net, or take it out to cash with that extra percentage fee going to the third-party provider. Any money left in the system needs to stay there. Players won't be able to cash it out at any point in the future, except by buying Blizzard products and services. "We're not a bank," says Pardo. "We don't want to deal with all of those additional regulations. So that's going to be the responsibility of our third-party payment provider."