Geeks With Blogs

News

Google My Blog

Catch me at: The List!


My InstallScript Utility Belt My Amazon Wishlist
My Standard Disclaimer


Archives
Chris G. Williams Beware: I mix tech and personal interests here.

I've had a few folks ask me why I implemented a custom Random Number Generator (Mersenne Twister) in my game, Heroic Adventure! This article explains why far better than I could.

From the Rec.Games.Roguelike.Development FAQ, section 37:

What's wrong with the random number generator that came with my programming language?

Almost all programming environments come with random number generators that suck.  While they may be okay for casual use, the use of random numbers in roguelike games is anything but casual.

Most "default" PRNG's suck by having only 32 or 64 bits of state, which means they generate a sequence of numbers either 2^32 or 2^64 long, and then repeat.

Most roguelike games feature a lot of "sequential rolling", where further random rolls are made depending on the outcome of earlier rolls, and in this case each further roll reduces the number of possibilities for where in the cycle of numbers generated by the PRNG we happen to be.  It's easy to literally "run out of numbers" in such a way that rolls made after a certain point in a sequence are always the same, or drawn from an artificially reduced set of possibilities, because there are a limited (or nonexistent) set of subsequences of the main PRNG sequence that could have resulted in the rolls being made.

Let's see how this works in a dungeon scenario.  Say the player character turns over a rock.  You consult the random number generator to resolve a one in a thousand chance that there was something under the rock, and find that there is something there.

32 bits is about 4 billion numbers: that means that we are now in one of about 4 million number sequences where there would have been something under the rock.

So, what general category of item was under the rock? Back we go to our random number generator, to resolve possibilities like, it could be armor, or a weapon, or junk, or a magic item, or a treasure.  Most of what you find under rocks will be junk, but let's say that about 2 percent of the time, including this time, it's a magic item.  We're now in one of just eighty thousand possible sequences out of the whole PRNG cycle that could have led to this point.

What kind of a magic item was it?  The next roll sends us to "rods, wands, and rings", which was about ten percent likely.  Now we can tell by the fact that we're here that we're in one of just 8 thousand possible subsequences that could have led to this point.

Another roll sends us to the rings subtable.  Was that about 25 percent likely?  Okay, now we're talking about one sequence chosen of about 2 thousand sequences in the cycle of 32-bit numbers that could have gotten us here.  A magic ring is under a rock.

Rings of speed are rare; let's say that we find a ring of speed, and one ring out of every two hundred or so rings is a ring of speed.  That means there's just ten (on average) possible sequences that could have gotten us to this point: A ring of speed is under a rock.

Finally, we roll to find the ring's bonus.  But no matter how many possible results there are in our table, or what probabilities they're assigned, there are only ten (approximately) 32-bit numbers that could follow all the other 32-bit numbers that have led here, thus only ten results are possible and all probability distribution on this table is in increments of ten percent, no matter what it says in your code.

You may think this example is contrived; but it's not. In fact, it's oversimplified, and most roguelikes will constrain things even further.  The problem here is with the short period of the PRNG.  It repeats after a cycle of just 2^32 trials, and when we are sequential rolling, we can quickly winnow out all possibilities of where on the cycle we are.

There's another problem too; Lots of c-library PRNG's suck in a particularly amazing way by having very short cycles in their low-order bits. When these are taken modulo small numbers, as is the naive approach for simulating die rolls, patterns quickly emerge and sequential rolling becomes ridiculous. For example, a coin toss simulated by taking the PRNG output modulo 2, if your PRNG has this bug, would give an endless series of alternating heads and tails, which don't seem very random at all.  If you get a good PRNG to start with, the modulo construction shouldn't hurt you; but if you are at all uncertain, use scaled division instead.

In fact, lots of roguelike games in the past have behaved so differently under different random number generators that the balance and playability, inadvertently tuned to a particular generator, was upset.

If you don't want to have a problem running out of numbers after a long sequence of dependent rolls, then you need to provide a *GOOD* random number generator that takes a long time (way longer than 4 billion numbers) to cycle.

I like a lagged-fibonacci generator, as described in Knuth v2, as a pseudorandom generator that is fast, apparently avoids detectable patterns, and has a very long period.

The Mersenne Twister is almost as fast and its output is very good.  Lots of people prefer it because we can prove more about its properties.

But there's lots of code for good PRNG's floating around the net these days, much of it borrowed from the cryptography or simulations communities.  You don't really need cryptographic PRNG's, and they are mostly slow.  But there are some very good PRNG's made for simulations (like the Mersenne Twister) that are both fast, and strong in precisely the ways we need PRNG's for roguelike games to be strong.

Posted on Wednesday, April 20, 2005 1:32 PM Game Development , General Interest | Back to top


Comments on this post: Mersenne Whatsit?

# re: Mersenne Whatsit?
Requesting Gravatar...
Could you explain exactly what the 'scaled division' method is for the particularly dense among us?
Left by DM on Jun 11, 2005 1:08 PM

# re: Mersenne Whatsit?
Requesting Gravatar...
I can try... the term scaled division (as I understand it) refers to a workaround for floating point values.

Consider decimal arithmetic, where fixed-point decimal fractions can be represented by arbitrary precision simply by multiplying values by powers of 10, performing integer arithmetic and, if necessary, scaling to put our notational decimal point back into the right place. Let's say that we want to perform arithmetic to a precision of two decimal places. To add two numbers together (say 1.75 and 2.86), we start by multiplying our input values by 100 so that they can be represented as integers (175 and 286), add them together as integers (175+286), and end up with a value (461) that we know, by convention, actually represents 4.61.

Multiplication and division represent a slightly more complicated case as the notational decimal point will move around, so, in the case of multiplication, taking our values of 175 and 286 as again representing decimal fractions to two decimal points, we end up with a value of 50050, which must be scaled by dividing by 100 representing an integer value of 5.00 (in critical applications we might want to apply some form of rounding to minimize the effects of loss of precision when we use integer division to scale the results).

Division is slightly different. Dividing 1.75 by 2.86 should give a result of 0.61, but if we divide 175 by 286 using integer division we will get a result of 0! This can be avoided by performing scaling before we do the integer division by multiplying the dividend by 100, so, 17500 is divided by 286, giving a value of 61, which correctly represents the expected value of 0.61.

Does that help?
Left by Chris on Jun 11, 2005 3:13 PM

# re: Mersenne Whatsit?
Requesting Gravatar...
Yes indeed. Thank you.
Left by DM on Jun 11, 2005 8:38 PM

Your comment:
 (will show your gravatar)


Copyright © Chris G. Williams | Powered by: GeeksWithBlogs.net