Randomness in generative code
Recently I wrote an experiment with a single background on a single element using radial gradients. This resulted in a seedable image set in motion by Simplex noise.
This made me think of a merge request I made a while back that puzzled my co-worker because it had a linear congruential generator in it. My work isn't usually this exciting but I was adding a skeleton loader to a table component. This had to be random, but seedable, hence the LCG.
Wait wut?!
Okay, a few steps back, starting with 'seedable'.
As you may know computers are great at computing. Give it a problem and it will always calculate the same result. Which is fine mostly, but a problem when you do not want the same result. Because unfortunately computers are really bad at random.
Luckily our human pattern matching capabilities fail with large enough numbers. Computers don't mind large numbers. So we came up with something called a pseudo random number generator, or PRNG.
This is a function that turns any number into a seemingly unrelated different number. It seems random, but it will always give the same result for a given input. So ehrm, pseudo random.
This input number is what is called 'the seed'.
And this is very useful. A random seed allows us to create something that looks chaotic but is in fact very predictable.
You might have used seeds in games or seen it in generative art. Minecraft has world seeds that are used for terrain generation. The planets in No Mans Sky or Star Citizen are generated this way as well.
So how does pseudo random work?
There are different ways to create a random number.
A linear congruential generator is fast but of quite low quality. Higher quality generators are generally slower because they are more complex. Relatively fast ones are the Mersenne Twister and Xorshift.
We'll stick with the linear congruential generator because it is easy to understand.
It looks like this:
seed = ( seed * multiplier + increment ) % modulus
This uses just three constant variables. Multiply the seed and add something (that is the linear part ax+b) and calculate the remainder for a division by another number (% is the remainder operator).
This is a simple operation even my ten year old son can do by hand.
The outcome of the operation is generally used as the seed input for the next.
For most values of the constants this will produce very regular results. Take the following simple example:
const multiplier = 47
const increment = 59
const modulus = 113
let seed = 12
const random = _seed => seed = ( (_seed||seed) * multiplier + increment ) % modulus
// run `random()` 150 times:
// 58 73 100 13 105 22 76 15 86 33
// 28 19 48 55 45 27 85 99 79 43
// 46 74 34 75 81 24 57 26 38 37
// 103 41 65 63 82 71 6 2 40 18
// 1 106 69 25 104 88 14 39 84 52
// 17 67 44 93 23 10 77 62 35 9
// 30 0 59 7 49 102 107 3 87 80
// 90 108 50 36 56 92 89 61 101 60
// 54 111 78 109 97 98 32 94 70 72
// 53 64 16 20 95 4 21 29 66 110
// 31 47 8 96 51 83 5 68 91 42
// 112 12 58 73 100 13 105 22 76 15
// 86 33 28 19 48 55 45 27 85 99
// 79 43 46 74 34 75 81 24 57 26
// 38 37 103 41 65 63 82 71 6 2
Well that's no good. These starting conditions start repeating after 112 iterations, and the distance between two numbers repeats after only 56 iterations.
This might sound a bit vague, so lets put it in an image where every pixels is generated by a random value. We'll take some better starting values. The ideal image would be one that looks like white noise.
const multiplier = 13523
const increment = 13
const modulus = 31457
A sheet of numbers is difficult to compare, but in this image you can easily discern the repetition (which is after 1292 pixels). This is for a remainder size of 31457.
Carefully chosen starting values
The multiplication and increment must fit the modulus in such a way that a large number of unique values are passed. You could say that the angle of the linear equation must cover as much points as possible before doubling onto itself again.
This is called the period. One of the characteristics of a good PRNG is a large period.
Prime numbers are popular modulo values, especially Mersenne primes. But you can find relatively random constants by trial and error. A large enough modulo certainly helps.
Wikipedia has a good list of values that have proven to give good results.
(an LCG works with modulus but JavaScript's % operator is a remainder calculation, which has different outcomes for negative values.)
Movement
A lifelike random movement is created by using Simplex noise. This Perlin noise variation is generally used for terrain and texture generation, but works great for movement as well.
It is created by interpolating random numbers and stacking one or more results with different periods. Thanks to the Wayback machine we can still access this very good explanation.
The random number generator used in Simplex noise is a bit different from the one shown above. It uses the Alea PRNG (by Johannes Baagøe). Alea has a period of about 2^16.
The original Perlin noise uses a hash table. Not a PRNG per se, but it works for the particular application.
True randomness
To come back to the skeleton loader: I said it had to be seedable. But by now you may realise randomisation in computers is always seeded. The seed may be hidden, like with JavaScript's Math.random, but it is definitely in there.
True randomness can only come from the real physical world. Like the atmospheric noise used by random.org or Cloudflare's lava lamps. You can let your computer use a special electronic circuit board that derives the numbers from real life, not from ones and zeroes.