Click here to Skip to main content
Click here to Skip to main content
Technical Blog

Tagged as

Is the XCOM PRNG Broken?

, 30 Jul 2014 GPL3
Rate this:
Please Sign up or sign in to vote.
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 […]

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 Poke tongue | ;-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 Poke tongue | ;-P .

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

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

Share

About the Author

Grant Curell

United States United States
Grant is a specialist in computer security and networking. He holds a bachelors degree in Computer Science and Engineering from the Ohio State University. Certs: CCNA, CCNP, CCDA, Sec+, and GHIH. More info at grantcurell.com.

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web04 | 2.8.141022.2 | Last Updated 30 Jul 2014
Article Copyright 2014 by Grant Curell
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid