Is the XCOM PRNG Broken?

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 ;-p.

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 ;-p.

Now, if you’re curious about how it all works, I explain that below :-D. 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:

uint32_t seed; /* Set elsewhere.

float random_number_plox() {
static union {
uint32_t i;
float f;
} foo;
int bar;

/* LCG: x = 0x0BB38435 * x’ + 0x3619636B */
foo.i = seed * 0x0BB38435;
foo.i += 0x3619636B;
seed = foo.i;

/* Convert the integer to a floating point number between 1.0 and 2.0 by
* manipulating the floating point format.
*/
foo.i = foo.i & 0x7FFFFF | 0x3F800000;

return foo.f – 1.0f; /* Return something between 0.0 and 1.0 */
}

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; /* Return something between 0.0 and 1.0 */

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 information.