A good Pseudo-Random Number Generator (PRNG)

When developing games you often need a PRNG that, once initialized with a seed value, produces always the same sequence of random numbers after it. The Math.rand() function in Flash is a PRNG, but it doesn’t let you define a seed value (I think it’s picked randomly when the swf starts, but there isn’t much information about it) so another solution has to be found.

One of the best PRNGs is the Mersenne Twister algorithm, but in my opinion it’s total overkill for flash games (also slow and difficult to implement). However, after spending some time with google I found an interesting site explaining the implementation of the Park-Miller-Carta PRNG, which belongs to the group of Linear congruential generators (LCGs).

As the name implies, the PRNG algorithm was developed by Stephen K. Park and Keith W. Miller and published in this paper [1]. David Carta provided a fast implementation of this algorithm by using only bitwise operators and no division.

I wrote a simple class for generating pseudo randoms which includes the two integer versions found in the paper and in addition Carta’s optimized version. The Park-Miller LCG generates a circular list of 2^31-1 (2,147,483,646) random numbers so this should be quite enough :-).

In the paper you find implementations using integers or floats only. ‘Integer Version 1’ produces only correct results for systems that can handle a max integer value of 2^46-1 whereas ‘Integer Version 2’ is suited for a max integer value of 2^31-1 (32bit). I’m using ‘Integer Version 1’ with the Number data type since this is the most efficient computation in Flash and I also verified it until the last iteration 2^31-1 (which took about 20 minutes in AS3 ;-)).

Carta’s optimization also works perfectly, but it’s approx. 15% slower than ‘Integer Version 1’ so I have commented it out together with ‘Integer Version 2’ in the PRNG class. The computation is therefore reduced to:

new-value = (old – value * a) % m

Where m is the modulus constant and a is the multiplier. Though the result of this formula is entirely predictable the sequence of numbers is ‘random’ because each number isn’t related to the numbers before and after it in the current sequence. This behavior is very dependent of the a and m constants so they must be chosen carefully (I suggest you read trough the site for a full explanation).

Edit: After reading another nice article explaining pseudo randoms that included a visualization of the randoms, I created a little visualization myself to show the value distribution (click flash & keep mouse inside stage). You can also change the multiplier (a) and watch what happens when you use low numbers like 10.

Download & Usage

Park-Miller-Carta Pseudo-Random Number Generator:
AS2 Version
AS3 Version

First define a seed value (default is one) and then call nextInt() to get the next integer value, nextDouble() to get a floating point number between 0..1 and nextIntRange() or nextDoubleRange() to generate numbers within a certain range.

var pr:PM_PRNG = new PM_PRNG();
pr.seed = 123;

for (var i:Number = 0; i < 10; i++)
{
     trace(pr.nextInt());
}

Works cited

[1] "Random Number Generators: Good ones are hard to find"