So I sat down to play XCOM the other day. Great game for the most part. However, there were a couple of sequences where I would fire with 3 different soldiers at 90+% chance to hit and I would miss all three times. Well, when you do the math on that ~.1^3 chance for that to happen, you begin to wonder if something is amiss. Like any gamer, I of course assume that I could never be bad at the game. The game must obviously be the problem .
So the answer to the big question? Yes, XCOM uses a mathematically poor PRNG. Specifically, it uses a linear congruential generator. To answer the question of whether it’s broken: it isn’t. Is it bad enough that it really affects gameplay? Not really. So for everyone else who missed that 98% chance shot and became enraged, yes, you’re probably that unlucky .
Now, if you’re curious about how it all works, I explain that below . I’ll apologize up front, I wrote this kinda quickly so the explanation could probably be a bit more clear.
A linear congruential generator uses the equation X sub (n+1) = (aX [sub n] + c) mod m, where X is the seed value for random number generation. Xcom uses a = 0x0BB38435, and c = 0×3619636. Xcom uses CPU ticks since boot as the seed value. Below is the actual code for generating the number:
foo.i = seed * 0x0BB38435;
foo.i += 0x3619636B;
seed = foo.i;
foo.i = foo.i & 0x7FFFFF | 0x3F800000;
return foo.f – 1.0f;
It doesn’t actually use a mod; it uses some floating point arithmetic. The lines:
foo.i = foo.i & 0x7FFFFF | 0x3F800000
return foo.f – 1.0f;
can be a bit confusing. You have to know a bit about how floating point numbers are stored in a computer. Rather than explain it here, I suggest you read: http://kipirvine.com/asm/workbook/floating_tut.htm. Once you understand that these lines become more clear. The foo.i & 0x7FFFFF is zeroing out the sign and the exponent and the | 0x3F800000 is making the sign positive and setting the exponent to 0. Because we know the seed value is greater than 1 we know that going into this calculation we had a value greater than 1. However, the computer is going to interpret the lower 23 bits of the number as a binary mantissa so that’s going to yield a number between 1 and 2.
The final line ” return foo.f – 1.0f;” just forces an implicit conversion from an interger to a floating point number and subtracts 1, which will give us a number between 0 and 1, which will then be used to determine whether we hit or not. Thanks to Yawning Angel at http://www.schwanenlied.me/yawning/XCOM/XCOMPRNG.html for the info.