Procedural Generation and Randomness

“Insanity is doing the same thing over and over again and expecting different results.”

Welcome back! It’s been a little while since our last blog post and lots of happened – we moved office, had a baby and have been hard at work on lots of things including our level generator. So I thought it’d be interesting to talk about randomness for video games particularly related to procedural generation.

Mixing it up

“The world is governed by chance. Randomness stalks us every day of our lives.”

Paul Auster

Any sort of procedural generation has to have a changing element, otherwise we’d just get the same output every time. It’s great to procedurally generate a box, but if it’s always the same size then that’s no different from just modeling a box the normal way. Often there’s a lot of decisions that are made with some sort of random chance or probability – basically rolling a dice. For example, in Minecraft is a cobblestone block plain or does it contain iron ore? Throw enough of these decisions together and (hopefully) we end up with something controlled but varied. Often games build on top of this simple dice-rolling randomness with techniques like Perlin Noise / Voronio Diagrams or Random Walk which are structured randomness rather than the complete unpredictability of a dice rolling.

Perlin noise – coherant randomness

But sometimes it’s useful to generate the same output. Debugging is much easier if we can isolate ‘weird’ content and replay the generation to see what’s up and how it came about. Players can also ‘save’ content for later – for example finding a good world to play in Minecraft. Different players can also experience the same content at the same time, like the daily challenges in Sperlunky. It’s also an efficient way to transmit content over the network without really moving a lot of data around.

Fortunately, computers are really bad at actually generating random numbers. They like doing the same thing over and over, with the same results. So to get actual dice rolls we can use a Pseudo Random Number Generator (PRNG), and these use what’s called a ‘seed’. Seeds are just a single big number that’s used as the starting point. It could be an actual word (like the player’s name), or something that changes a lot (like the current date and time) or even how many seconds we spend on the title screen. As long as we run our level generator with the same seed it’ll always generate the same content.

Why does this work? Well computers might be bad at randomness, they’re really good at doing calculations and coming to the exact same result. PRNGs really just do some simple maths – taking the current seed and adding a fixed amount to it each time, which generates a series of numbers. That’s a bit predictable so real PRNGs mix it up with extra maths like multiply and remainder to get something that looks a lot more chaotic. The end result is still just about predictable if you know exactly what’s going on and when the dice rolls are made (which is why Zelda speedrunners are able to predict item drops ahead of time) it’s good enough for games. If you need ‘proper’ randomness (for example for secure encryption) then that’s a whole other rabbit hole that can involve using radio wave static or other external inputs.

A Random Walk moves in a different direction every step

Fortunately PRNGs already exist in most languages, so we just need to set the seed before we start generating a level.

So then everything just works right? Yeah, maybe not. This only works if the RNG is the *only* source of randomness, and it’s very each for accidental randomness to creep in. If that happens, even using the same seed will result in different levels. We have to be vigilant and check that a seed is consistent and produce the same level each time – especially when adding new features!

Accidental Randomness

“The generation of random numbers is too important to be left to chance.”

Robert R. Coveyou

How do we end up with accidental randomness? Well although programs do the same thing each time, the environment around them might be different. It might request a list of textures from the hard drive and they might be returned in any order. The solution here is to sort the textures in a consistent way (such as alphabetically) so it doesn’t matter what the order we get them in.

A Voronoi Diagram starts from randomly placed points to divide up space

Similarly the order of items in memory can trip things up – the same stuff will be stored, but it might be stored in a different place in memory. Structures like Maps or Dictionaries often have undefined ordering. This can be solved by using data structures with guaranteed ordering or by sorting their contents before using them.

Unexpected user differences can also creep in – such as accidentally using a username, or the number of attached monitors or game pads. The solution here is to keep these out of the generator completely. This may seem obvious but often these can have secondary effects that *do* get used in unexpected ways.

Hardware can also make a difference – for example Intel and AMD cpus used to calculate with different internal precision, which means a number might be rounded up on one and down on the other. This is much less of an issue with modern CPUs and languages, but it’s still important to check your maths library produces consistent results. Sticking to integer (whole number) maths can help too.

Inconsistent timing differences across threads are another potential pitfall. Race conditions may not be fatal, but their exact timing may cause the RNG to be used in a different order. Per-thread seeds are a good way to solve this.

Finally we have out-of-order generation. For example in Minecraft the first player to view a chunk of the world trigger its generation. Depending on how players explore the chunks will be generated in different orders. Ideally everything should be generated at once in a predictable order. But if that’s not possible then a separate sub-seed for the bits that come later can be stored.

I hope this has been an interesting introduction to dealing with randomness in a procedurally generated game. There’s lots to take into account, but the payoffs from deterministic generation are really worth it!