Correlated RNG

        *

        *

Games that rely heavily on procedural generation often want their random number generators to be deterministic so that if given one single seed, each of your systems will generate the same game elements each time for everyone. Games that don't rely on RNG very much might just use whichever built-in RNG comes with their engine and call it a day, but for games with more complex generation, a more common approach is to use multiple different random number generators for each different area of your game that uses RNG to determine game state.

This method is great for decoupling the results of output across different systems that would otherwise be tied together if using a single random number generator everywhere in your project (Like Unity's built-in Random.value or Random.Range()). When you only have a single shared generator across each of your different systems, the output of each system will change depending on how many times it had been queried so far. Say there's a map generation you like, you could save your game's shared seed to make sure to generate that same map for later. But when all systems are querying and changing the state of your one generator, suddenly adding an extra item roll earlier in the process will progress the generator forwards, resulting in different outputs once you reach the map generation phase. Goodbye cool map :(

Having multiple RNGs for each of your different systems to use means that their outputs can all be kept independent, guaranteeing that if you haven't changed the map generation code in months, it will continue to generate the exact same maps despite all of your work on enemy stat generation.

The one catch to this method is something called "correlated RNG", which happens when you seed all of your various RNGs with the same initial seed. They'll all generate the same numbers in the same order, which is something that players can catch onto and exploit in ways you may not have intended, potentially spoiling their own fun.

This kind of issue happens a fair amount in games! The weather selection in each area of Final Fantasy XIV is determined by a single algorithm that uses the current time in-game as a seed, leading to things like Rak'tika Greatwood always being shrouded in fog whenever Ultima Thule is weathering astromagnetic storms. Correlated weather state is pretty inconsequential within the scope of FFXIV, but even a roguelike like Slay the Spire has this issue! Jorbs made a good video breaking down what it and the consequences of its existence once you learn about it:

The TLDR is that if you're generating the same sequence of numbers for each different system, players can see the results of the generation from one system and have it tell them about what choices will be made in other systems. If you have a system that uses its own generator and needs to choose between 3 things 5 times in a row, players might catch on that seeing options 1, 3, 1, 1, 2 means the random values of the generator are somewhere in these ranges in this order: 0.0 - 0.33, 0.66 - 1.0, 0.0 - 0.33, 0.0 - 0.33, 0.33 - 0.66. If you have another system that always chooses between 12 options, seeing option 1 for the first system will always result in seeing options 1-3 in this other system.

So how do you fix this while retaining the benefits of having multiple independent and deterministic RNGs sourced from a single seed? There are a few ways! Here are the pros and cons of some of them:

1. Start each generator with a different offset...?

This is maybe the most simple method to addressing the problem, but it's definitely more of a bandaid solution than a systemic one. Each RNG will still generate the same sequences as each other, but all it's really doing is making it a little less obvious by pushing the start of the sequence further down the line. The offsets need to be substantially big enough that others shouldn't overlap, some RNGs don't support skipping ahead very well, and it also requires keeping track of which generators use which offsets. IMO this method is definitely more of a pain than it's worth.

2. A dedicated RNG to generate seeds?

This was my first approach to solving the problem, and it definitely is effective! You seed your random seed generator with your single seed for the game, and then you create all further RNGs with seeds sourced from the output of the seed generator. Each RNG will get their own distinct sequence while still deriving from the same initial base seed. The issue with this approach is that the state of each RNG is now tied to the order that they were created in. This is a lot easier to control after it's been initially set up, but if you remove a generator at any point, all of the generators created afterwards will have been changed.

3. Hash-based seeds!

This is the solution I've opted for in my own RNG system, and IMO it's as good as it gets. Whenever you create a new RNG, hash the shared seed with some unique identifier specifically for that RNG instance. As long as your hashing algorithm is deterministic, (DON'T USE C#'s HASHCODE STRUCT LMAO) each generator will have their own unique sequences that are wholly independent from other generators or external systems, with minimal extra work required to create new RNGs.

I've written my RNG system to just accept an optional string/integer for hashing in the RNG constructor, so it's as simple as new RNG(gameSeed, "System Name"). An added benefit to this approach is that it makes it really easy to intentionally couple RNGs together by either hashing the incoming seed with the output of another RNG, or hashing it with the already hashed seed of another RNG. If you also store the input hash inside of your RNG class as well, you can later query it for debug ID purposes or for making your seed variants more readable when serialized. The world's your oyster!

UPDATE: Found out like 6 hours after posting this that MegaCrit (the Slay the Spire devs) actually use almost this exact same method for addressing correlated RNG in Slay the Spire 2, which you can read about here! Definitely worth a read along with the the writeup by tckmn if you're interested in the details of the issue and the gameplay consequences.

TLDR FOR NERDS WHO WANNA KNOW THE DETAILS BUT DON'T WANNA READ ALL THAT

The issue stemmed from the combination of using C#'s built-in System.Random class and the method for combining the run seed with an identifier. System.Random apparently has an implementation quirk which is that linearly increasing seed values will produce correlated linearly increasing output, meaning that their seed combination method of seed = runSeed + hash("identifier") will have all generators outputting the same numbers with some fixed offset from each other. I feel for the devs, I think discovering that fact after going out of my way to prevent correlated RNG would make me tear my hair out lmao. Hashing both the run seed and the identifier together would also have solved the problem, but switching to the xoshiro256** XORShift algorithm is a better play cause XOR shift algorithms are a lot faster and more reliable for games contexts anyways.

I personally use the Squirrel3 algorithm outlined by Squirrel Eiserloh in this great GDC talk cause it's extremely easy to understand, easy to serialize (two uints), fast to jump between arbitrary positions, and guaranteed to return the entire unsigned integer sequence in a random order before repeating any previous value. Anyways. Stop reading about nerd shit and go play Slay the Spire 2 to ease the ailments we both seem to share if you've read this far.