Random Number Generator

[Nova]

What kind of random number generator does Factorio use?

[ssilk]

https://forums.factorio.com/forum/vie ... 450#p46431

[Nova]

I did read that thread, but I don't see the answer to my question there. Math.random was changed and I can't find map.random.

Something like a link to the definition of the used generator would be nice, or (if not confidental) the source code if it is an own algorithm.

[cube]

http://www.boost.org/doc/libs/1_56_0/do ... aus88.html

[Nova]

Thanks for the information. Random number generators are a complex topic and many bad generators exist, but this looks like a "good" generator. Wanted to make sure you don't use something like a linear congruential generator. ^^

[cube]

I don't think that even LCG would cause problems in Factorio. We are not using it for any security related stuff, only placing entities on map, moving biters ... Yes, it could produce visible patterns, but IMO there is enough chaos in the game that these would quickly disappear anyway.

We chose taus88 mainly because it is the fastest from boost's generators. I was thinking of removing one of the three LFSRs (that should make it about 40% (?) faster), but there is no point, since the ranom numbers are not a bottleneck for us.

[Cilya]

I use LCG in one of my personal project for map generation and it works fine. I don't understand why you would need a better/safer random number generator. LCG is fast at computing the "n-th" random number and very fast at computing the "n+1-th" number. And it can be tweaked to generate 2D-coherent-noise efficiently and easily.

[Nova]

Even much better random number generators are not suitable for random numbers which have to be "safe". Never use a generator which was not specially designed for cryptographic purpose. It will break your neck if someone really wants to attack your program.

Yeah, an LCG is maybe enough for most games, but it's just a terrible generator, plain and simple. Consecutive values will be odd, even, odd, even, odd, even... This "feature" alone is enough to mark the LCG as a very bad generator. (You could alter the values of course, like only using the x highest bits, but it's still pretty awful. Java does this.)
Pretty much own conviction if you want to use a bad, but sufficient generator or a better, but slightly slower RNG. There are many generators which are much better and only slightly more complicated, like for example the xorshift* or xorshift+ generator. Personally I prefer a generator which is good over a slightly faster generator which will maybe, perhaps, possibly be enough for its task. But that's only my opinion.

Xorshift*, 64 bit, fails only one test (MatrixRank) systematically of the TestU01 test suite.

Code: Select all

uint64_t x; /* The state must be seeded with a nonzero value. */
uint64_t next() {
	x ^= x >> 12; // a
	x ^= x << 25; // b
	x ^= x >> 27; // c
	return x * 2685821657736338717LL;
}

Xorshift+, 128 bit. Better than Xorshift*, 64 bit. It fails no test of the TestU01, neither with normal nor with the reversed bits.

Code: Select all

uint64_t s[ 2 ]; // Could be changed to two independent variables, but an array is pretty logical here.
uint64_t next(void) { 
	uint64_t s1 = s[ 0 ];
	const uint64_t s0 = s[ 1 ];
	s[ 0 ] = s0;
	s1 ^= s1 << 23; // a
	return ( s[ 1 ] = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) ) ) + s0; // b, c
}

For comparison, the generator of Java (a 48 bit LCG, which only returns the 32 highest bits) fails nearly every test systematically of the BigCrunch test suite of TestU01.


The code is public domain.
Source for information and the generators.

[Cilya]

Consecutive values will be odd, even, odd, even, odd, even...

No, that's not true. It depends on what constants you are using.

I don't see how you would compute the n-th value with Xorshift. It is needed when you want to do procedural map generation, to create coherent noise. I think you are missing the point. For map generation, we care only about aesthetic criteria. Predictability is not something we would bother with if it's not noticeable by the eye.

[cube]

That xorshift looks nice, I hope I'll rememeber it for next time I need some PRNG.

For map generation we use the 1 byte coordinate hashing from Ken Perlin's ImprovedNoise: http://mrl.nyu.edu/~perlin/noise/

[Nova]

Consecutive values will be odd, even, odd, even, odd, even...

No, that's not true. It depends on what constants you are using.

Yeah, I was talking about the most common x(n) = (a * x(n-1) + c) mod m. (c = odd number and m = power of 2) - There are some with c = 0 (Lehmer RNG), and the value for m doesn't has to be a power of 2, but this are the most common kind of LCG. The named "feature" with odd, even, odd, even... numbers is visible in this generators.

To be honest, I have no idea how to calculate x(n) fast if it is not the next value of the series. Never actually thought about that. ^^

[Cilya]

To be honest, I have no idea how to calculate x(n) fast if it is not the next value of the series. Never actually thought about that. ^^

Well... xorshift is faster than LCG when you don't use power of 2 modulo. But you can compute the n-th element with modulo exponentiation. It's much more costly, but you usually do it only once per map chunk (using incremental computation for other random values) That's very useful for procedural map generation.