Friday, December 28, 2012

Seeding Multiple Random Number Generators

I was trying to lower the bandwidth and perceived latency of a game by having both the client and server calculate the combat results instead of transmitting the result from the server. While this worked, it created another issue of keeping the random number generators (RNG) in sync. If the client calculates Character 1's attack then Character 2's attack, but the server does this in reverse order (say, due to packet latency) the client and server desynchronize. The solution to this was for every entity to have its own RNG for its attacks. However, I noticed an issue with the attacks: the first attacks of each entity were the same. It had all to do with how I was seeding it.

It is common knowledge that linear congruential random number generators (LCG) have a number of quality issues. If you choose the constants poorly, plotting random points will draw stripes instead of looking random. In even the best LCGs, the low bits are less random than the high bits. Recently I found another manifestation of the standard issues resulting from a bad choice of seed. I was seeding my RNGs sequentially. As in Entity1 is seeded with one and Entity2 is seeded with two. If you seed two LCGs with sequential seeds, then the first number out of each generator will be close.

While close is a vague word, if you're generating a random number between 0...n using the high bits the "right way", with rand()*N/RAND_MAX instead of rand()%N, then the two close numbers become exact. To fix this I tried using another RNG to generate my seeds, but this only created another problem. Because LCGs are not truly random, but a large looping sequence of numbers, the "random" seeds I were generating were just adjacent positions in the sequence. Resulting in RNG1 generating 1,2,3,4 and RNG2 generating 2,3,4,5.

Working around this issue would require having a second set of LCG constants for the seed generator. While switching to a better generator would fix all this, the better generators have a lot more state information. Using a separate good RNG per entity would use a lot of RAM. In the end, I seeded sequentially and burned off five random numbers before using it and it works good enough. Does anyone have a better solution?