Pseudo Random Number Generators


Pseudo Random Number Generators, or RNGs for short, are algorithms that generate a sequence of numbers that appear to be random, but are actually deterministic. This means that the same sequence of numbers will be generated for the same seed.

This is useful for games, as it allows us to generate the same sequence of numbers on different machines, and to reproduce the same sequence of numbers at a later time. Or to provide seemingly random numbers by using a seed that is based on the current time, the current state of the game or some other value that changes. It is important for an RNG to initialize it correctly and choose a seed that fits the style of the game.

RNGs have different properties, such as speed, statistical quality, period, and distribution. Some RNGs are better suited for generating random numbers for games, procedural content and/or artistic styles.

Period is the number of numbers that can be generated before the sequence repeats, meaning the RNG will produce the same numbers in the same sequence as it did in the beginning. A longer period might be better, depending on the usage but doesn’t imply the rng has a better statistical quality.

Quality is the statistical quality of the numbers, good statistical quality means that the numbers are evenly distributed and that the numbers are not biased.

Speed is the time needed to compute the next random number value. Not only the speed of the RNG is important, but also which type of values are needed. De-biased int32 values are slower to generate as biased int32 values. Specific CPU architectures also have an impact on the speed of the RNG, for example some CPUs are very slow with float operations making int32 values faster to generate. Whereas modern Intel CPUs are very fast with float operations.

Distribution is the probability of the numbers being generated, basically how often a number is generated. All RNGs in this package are uniformly distributed, meaning that all numbers have the same probability of being generated.

For example the Unity supplied Random class math.Random is based on Xorshift32 with 32 bits internal state. This is very fast, but has a very short period of 2^32. This means that after 2^32 numbers have been generated, the sequence will repeat. It also fails quality tests from Dieharder, PractRand and TestU01.

The goal of the package is not to provide secure random numbers, that can be used for cryptography, but to provide
alternatives to the Unity random number generator and allow more control over the randomness in the game.

Linear Feedback Shift Registers (LFSR)

Linear Feedback Shift Registers are a very old form of “random number generators” and are provided out of curiosity. These structs do not feature the same methods as the RNGs. LSFRs have the property that they are very, very fast and need only one Xor operation, whereas the fastest RNG needs at least three operations. They also have the property, that with the correct parameters, they iterate over all numbers in a seemingly random sequence. They have been used in old hardware to generate random sequences, like the random button in old CD players,
or in old games like Wolfenstein 3D to generate the screen transition (Fizzle Fade).