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 = 0x3619636. 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 info.

Leave a Reply