Don’t Generate, Hash

This 2020 RoguelikeCelebration talk by Andrew Clifton is a great look at a practical, technical implementation detail that digs into some of the topics that come up once someone has implemented their first few generators and start trying to figure how to get more control.

Random seeds are the first place to start, but as Andrew points out just storing random seeds quickly runs into problems. Instead, he suggests using a hash function: which in this case is just a function that takes your data and returns a number that looks random. But, importantly, the same data always results in the same hash value.

If you’re using a standard PRNG, the result is very sensitive to the order that things are generated in. You can think of a PRNG as a long tape with random numbers printed on it: each time you get a new random number from it, it looks at the next number on the tape and gives you that one. (The actual implementations use clever math to achieve unpredictability without storing that long list of numbers.) The seed is where the sequence starts. Starting with the same seed gives you the same results–unless things are done in a different order.

A blatant example of how this works can be found in many of the Civilization games, where attacking with different units first can cause different outcomes because the RNG checks happen in a different order. Speedrunners also make use of this, particularly when the RNG is predictable enough to be externally manipulated. And there’s a lot of ways this can go wrong, for example if loading game objects from a save game means that they get initialized in a different order than the order they were originally created in.

But hashing doesn’t care about initialization order because the hash value always starts from the parameters that you give it. This does mean that the various parts of your game need to be things that hash to meaningfully different hashes: the parameters need to be different so that you get different results.

Frontier: Elite uses a hash to generate sectors. Each sector uses the hash as the seed and determines the number of stars and then goes from there to generate the planets and so on. A weakness of the parameters being fed into the hash means that some sectors repeat–which is useful as a player if you can figure out where the human outposts have been accidentally placed in the galactic core. But that’s usually not the kind of emergent randomness that you want, so pay attention to your parameters.