A Short History of Randomness in Games (or "Why No Man's Sky is just a pretty Pitfall!")

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!

Interesting stuff. Thanks for the write-up, duder!

That was a great read man, really interesting stuff, really weird the rather simplistic approach carmack used on doom, I'd think he'd opt for a far more exotic solution, perhaps just because it was cheaper on the processing department, I mean CPUs at the time weren't exactly powerhouses.

And yes I'm hugely interested in procedural generation so yes please!

Great post, thanks!

More great examples of RNG manipulation in Tool-Assisted Speedrunning are the Shining Force runs by DarkKobold. This run of SF2 has since been improved by the same author but the RNG manipulation is only discussed in the comments there, with details about 7 Lua scripts the author created to manage the RNG.

This is fantastic! I'd love to hear about procedural generation, as I'm very young and inexperienced in the subject, but much like you love the concept of computers generating randomness and using it.

Great, interesting post! And very well written since that was a pretty painless read even for someone that isn't exactly the most glorious mathematician around. Needless to say, I'd really like you to continue to explore similar subjects in future.

The part about Doom's Big Fucking Gun was really new to me even just as a piece of gaming history. Very fascinating stuff.

But I liked pitfall...

@driadon: @cmblasko: @notnert427:Thanks! I thought it turned out pretty well :)

I've thought a bit of why exactly Doom chose to use this approach, and I don't think CPU limitations is the reason. Good PRNG's (or at least "good enough" PRNG's) can be implemented that use very little processing power. The example I provided, the Linear Congruential Generator, is an example of that: in order to generate a new number you only have to do two arithmetic operations: one addition and one multiplication (the "mod" operation can be implemented using something called bit-masking if the modulus is an even power of two, which is the reason 2^31 was chosen in this case. Bit masking is much faster than arithmetic). Two arithmetic operations is nothing for a computer, even a computer in the 90's. The computational cost is totally trivial. It's true that Doom's version is a tiny bit faster, but it's only faster by two or three CPU cycles. Given that you don't necessarily need to calculate very many random numbers inside a single frame, the computational cost makes no difference what-so-ever.

Another way to put it is this: if David Crane could implement a decent random number generator for a machine made in 1977 (the Atari 2600), the Doom guys could easily have done the same thing on a machine made in the 90's.

No, I think the reason is simply that programmers back then had much less general awareness of what "good" random number generation looks like and why it's a good idea to use a good PRNG. The Doom dudes are brilliant programmers, but they weren't number theorists. They used the first solution that came to mind and since it more or less works, they didn't worry about it after that. I would bet money that none of them even realized that their random number generator affected the damage output of the BFG, because it is a very subtle effect.

Pitfall is amazing :) It's also a minor miracle of programming that it even runs on a 2600, that device is insanely underpowered for a game like that. The developers had to break the machine in all sorts of ways to even get it to run. For instance: the 2600 only had support for single-colored sprites, but look at Pitfall Harry. He's a multicolored sprite. How did they do that?

Well, basically: magic. A CRT monitor draws the screen line by line from left to right with a cathode beam, which means that when the beam reaches the right edge, it has to travel back to the left side of the screen. During that time, you can squeeze in a few extra instructions, so what Pitfall does is that it changes the palette of the sprite while the beam is traveling to the left side of the screen. That's why every line of the Harry sprite is the same color. I cannot put in to words how clever that is, it's absolutely brilliant.

Getting Pitfall to run on a 2600 is sort-of like getting Crysis to run on a PS2. It's just insane that it was even possible.

@gkhan: And I guess I'm saying, I think I will like NMS too. nothing about that game is new or whatever. Its like many other space games but with all the procedural stuff it has on top of that. Those other games were just empty planets with space ships near them. NMS is that with something extra. Its doing things that have never been done before regardless of if people will call it repetitive or bland or variations of the same thing slightly changed by random variables.

Maybe I"m one of the few people with realistic expectations for no mans sky.

Cool Read, especially since i always failed to put the pieces together on how the scale of random-yet-persistent planets on NMS is gonna work.

I'd like to add (even if most may know already) that 256 (or 255) Levels is incredibly common in Games of the 80ies because of the reason stated above, although many (arcade) games did not really plan to have players getting through 255 Levels and just programmed the game to continue "endlessly", which results in games like Pacman, (EDIT: originally counted Donkey Kong, but thats not a 256 case, should actually read what i link) Galaga or Dig Dug just breaking themselves in what is mostly and famously referred to as "Kill Screens"

Interesting blog! I love stuff like this. The underlying workings of video games are super interesting, and randomness is absolutely not an exception.

That was a fun read! Thank you! A lot of great information there.

Fantastic blog post, really interesting stuff.

Thanks for the great write up. Really interesting info and it made No Many's Sky make more sense. Hope to see more posts like this.

This was really cool to read, thanks! I'd love to read more of this type of stuff!

It's always great to see how games are made and you've explained a small facet of this process perfectly.

Good writeup, it's still pretty surprising how many people don't have a solid grasp on the distinction between random and pseudorandom even when they are constantly using systems that have to rely on pseudorandom number generation.

This blog post was a real treat. I look forward to whatever else you might want to share in the future!

Interesting read. There are options for true random (enough in practice and in most theory) numbers but require special hardware. Imagine if an RPG would have hardware requirement of TRNG-card.

I remember that Golden Sun had PRNG that relied on player movement on the over world map. There was an enemy that one dropped real nice gear extremely rarely (in practice never) or 100% of the time if you did certain movement pattern before entering the area.

Fascinating read, thanks a bunch!

This was a more interesting read than pretty much anything I ever come across on the internet. Please, do more!

@gkhan said:

Pitfall is amazing :) It's also a minor miracle of programming that it even runs on a 2600, that device is insanely underpowered for a game like that. The developers had to break the machine in all sorts of ways to even get it to run. For instance: the 2600 only had support for single-colored sprites, but look at Pitfall Harry. He's a multicolored sprite. How did they do that?

Well, basically: magic. A CRT monitor draws the screen line by line from left to right with a cathode beam, which means that when the beam reaches the right edge, it has to travel back to the left side of the screen. During that time, you can squeeze in a few extra instructions, so what Pitfall does is that it changes the palette of the sprite while the beam is traveling to the left side of the screen. That's why every line of the Harry sprite is the same color. I cannot put in to words how clever that is, it's absolutely brilliant.

Getting Pitfall to run on a 2600 is sort-of like getting Crysis to run on a PS2. It's just insane that it was even possible.

Sorry for the double post, but this is just so incredibly insane and interesting. Where do you find pieces of technological minutia and game dev history like this? Is it mostly just developer talks/retrospectives like the pitfall one? This is the kind of thing I would love to dive deep into.

My dumb head hurts a little, but you should definitely do more posts like this, interesting stuff.

Great post, really really interesting!

@gkhan: Are you aware of the methods players used to game the random number generator in Final Fantasy XII? The equipment you recieved when you opened a chest in that game was random, and to get some of the best items you had had like a 0.1% chance. However (if I understand this right) the game used a random number generator with a pre-determined seed, so the sequence of numbers you'd obtain was the same every time you turned the PS2 on - and it took one number from this sequence every time it needed a random number in the game. So, you could apparently garuntee rare treasure by loading a game, running to the chest without doing anything to generate a random number, and then making your character attack themselves over and over - an action that just required one random number, to determine the length of the "combo" you got. A telltale 5-hit-combo around 80 tries in would tell you you were at the position in the sequence where the next number would garuntee a rare item. I don't know whether that's a quirk of the PS2's PRNG or just the implementation in Final Fantasy XII, but given that they had a proper PRNG at their disposal it seems crazy that they didn't just use the system time as a seed or something.

Rad post!! I love the idea that we can't ever generate truly random values. There's something profound in the idea that any number you come up with always has a process which created it.

Just put your iPod on shuffle and watch the generator pick the same favourites.

Cool man, thanks for writing!!

Absolutely fascinating. Thanks for write up! :D

That's awesome, I wish I knew it before so I could've included it in the post :)

Reasons like this is why many developers use the current time (or any other source of outside entropy) as your seed instead of hard-coding it, so players can't make these kinds of exploits. It also shows why high quality random number generators are a good idea. Most developers (like the developers in Doom) think "I don't really need that high quality randomness, I just need something that's sort-of random, players will never notice the difference!". That attitude is mostly right, but it also leads to things you (as a developer) could never predict, like nerfed BFGs and weird looting techniques.

One clarification: saying "the PRNG in the PS2" is a bit wrong. PRNG's are software, generally speaking the games come with them themselves, it's not something that's built in to the console. You can run the same PRNG on a GameBoy, a PC and a PS4, it's just an algorithm that generates numbers (there are things called "hardware RNG's" that generate much higher quality random numbers for cryptographic purposes, but those aren't necessary for games). So it's not "the PS4's PRNG", it's "Final Fantasy XII's PRNG".

(all that said, operating systems often provide random number generators if programmers want to use them, but generally speaking PRNG's are part of the code of the game itself, not the operating system or the hardware. If you're on a Mac or Linux box, you can try this out for yourself by opening a terminal and typing "cat /dev/random | xxd -p", and see staggering amounts randomness before your eyes. Press Ctrl-C to abort)

This is such an awesome post. Please keep 'em coming!

Great read, very interesting.

@effache:A good place to start (for the Atari specifically) is the book Racing the Beam.

@gkhan: Luck manipulation can be a big factor in non–tool-assisted speedruns too! There was a great speedrun of Earthbound in a recent AGDQ/SGDQ. Basically, Earthbound generates a random number every time you do something in a menu (to pick a random sound), so by moving the cursor x times, you can get to a good random number that makes your characters get critical hits and the enemies miss. (I assume the route was determined using tools, but still, humans are able to memorize enough of it to get through the whole game.)

Legend of Zelda runners also manipulate the item drops. A normal pseudo-random generator determines whether an enemy drops an item, but IF it drops an item, the item it drops is determined by the number of enemies you've killed mod 10 and the type of enemy. (There are also guaranteed drops if you kill a certain number of enemies without getting hit.)

Bubble Bobble item drops might seem to be random at first, but all of them are determined by counters for things like the number of bubbles you blow or the distance you move.

Tetris also does something interesting. It essentially puts n of each tetromino into a bag and pulls one at pseudo-random until the bag is empty. (Or, equivalently, gives you a pseudo-random permutation of n copies of each tetromino.) This guarantees you don't get an extreme case of randomness where you, say, never get an I or get far more Zs than any other piece.

Also, there's a cool website that explains the procedural generation algorithm in Spelunky with interactive examples (it uses a version of spelunky ported to browsers, modded to only do the level generation): http://tinysubversions.com/spelunkyGen/

@gee_rad: That's really cool. I'm not deep enough into the speedrunning community to know about those specific tricks, but I really dig that human players have learned how to do this as well.

The Tetris thing is interesting because it enables an algorithm that means that you could theoretically play forever, something which is not possible with the more basic algorithm of just spitting out random pieces. As someone who has played an unnecessary amount of Tetris in my life, I love the Random Generator. Even if you don't explicitly keep track of the bags, it allows you to "plan ahead" much better, and know on an instinctual level what kinds of pieces are "due". It really improves the game.