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”

24 Comments

  1. Nice article. Few years ago I had to use random number generator with seed. I’ve found some code in AS1 which now arose to that class:


    class PRand
    {
    private static var _gen:Number = 834427406578561;
    private static var _mod:Number = 2147483647;
    private var _seed:Number;
    private var steps:Array = [];
    private var step:Number = 0;
    function PRand(p_nSeed:Number)
    {
    seed = p_nSeed;
    }
    public function next(Void):Number
    {
    var element:Number;
    if (step 0)
    {
    step--;
    }
    var element:Number = steps[step];
    return element;
    }
    public function get seed():Number
    {
    return _seed;
    }
    public function set seed(p_nSeed:Number):Void
    {
    _seed = p_nSeed;
    }
    }

    btw. LOVE YOUR SITE

  2. hi there, what a nice site you are and props for all the source you provide.
    I noticed something interesting in the nextIntRange and nextDoubleRange functions. The argument names led me to believe that you put the minimum value first and max value second, but on executing it seems the first value is the range and second is the minimum value , so nextIntRange(50,10) would show results between 10 and 60. I like it this way but just wondered if it was intentional :)

    thanks again for a great resource

  3. hi, the functions should always return a number between min and max, that is min < n < max. if the min argument is bigger that the max argument, you get different results of course :) but I’ll have to check this, perhaps there is abug-

  4. I’m just using the AS3 version at the moment, i haven’t tested the as2 implementation, but the results i get when using nextIntRange(10,100) returns values from 101 to 110. After examining the algorithm a little it looks like you just missed off a couple of brackets, in the nextIntRange and nextDoubleRange return statements you have

    return min + max - min * nextDouble();

    changing this to

    return min + ((max - min) * nextDouble());

    makes it work as expected,
    thanks again for the class

  5. I would recommend to change

    public function PM_PRNG(){
    seed = 1;
    }

    to

    public function PM_PRNG(s:uint = 1){
    (s == 0)?seed = 1:seed = s;
    }

    for AS3, or

    public function PM_PRNG(s:Number){
    (s == 0 || s == undefined)?seed = 1:seed = s;
    }

    for AS2.

    That way, the seed can be set up at the same time as PM_PRNG initialization (new PM_PRNG(12345); gives you a seed of 12345).

    Also, it would be cool to change the class into a memorable name like Randomizer or something like that.

    Thanks for the class

  6. Hello Michael,

    the deploy doesn’t state any license. This makes it pretty problematic to deploy it together with other libraries. Would it be possible to add one?

    yours
    Martin

  7. Just added a BSD license to the source file so you can use it wherever you want.

  8. This is a fast and good PRNG

    Algorithm: x_n+1 = frac(s+nx_n)

  9. Hi, and thanks for this excellent and clear util – I’m finding it very clear and easy to use.

    However, I’m having a rather surreal issue with it – the results seem to alter with changes to trace statements! Now, I realize this is inexplicable, and I’ve looked at the code to investigate, and I can’t find any reason it should be so. But I really promise I honestly can get it to change output simply by adding or deleting a line that says “trace(‘HI’)”. Am I going mad, or is there some way this could be true?

    1. maybe a compiler bug, who knows. if you can reproduce the problem with a few lines drop me a note.

  10. Found the issue! I *was* going mad, but I’ll write it up here in case anyone is having the same problem.

    I was using the standard Flash AS3 Math.random to generate the seed for your PR – and that’s time-based! So adding trace statements made it load slower, which in turn changed everything else. Or rather, *not* adding trace statement caused it to generate the same numbers over again, which I thought was the PRNG’s doing, but really wasn’t. How strange!

  11. Thanks, I was trying hard to figure out how to do this! Very useful and easy to use.

  12. guillaume

    Hi,

    Thanks for it, I use it with the nextDouble() method and it appear that the first call to this method always return a value near zero, with a lot of different seed.

    Have you ever note this problem?

    An issue?

    Thanks!

    1. I can’t reproduce this. there are many seed values that also generate values close to 1, like 985675

Trackbacks/Pingbacks

  1. [...] Edit 25 April 2007: It seems I’m not the only one to address Flash’s lack of a seed based random number generator. Michael Baczynski presents a more academic approach to random number generation in actionscript. [...]

  2. [...] AS3 Random Number Generator April 30th, 2007 — drawk Polygonal Labs has an excellent random number generator.  There is an AS2 and AS3 version and it has much better random numbers tools such as seeds and ranges. 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. [...]

  3. [...] Recently I needed seeded pseudo-random number generator for my Flex project. After searching I found three good articles with solution of that problem. Grant Skinner proposed use of BitmapData.noise() method. He also provides Parker-Miller psuedo-random number generator based on implementation by Michael Baczynski. [...]

  4. [...] Generator. Fortunately, a couple of people had already done the job amongst which (and before all)POLYGONAL. Of course, he did a great job and I have to admit that I couldn’t get it [...]

  5. [...] I use the Random Number Generator from Polygonal that allows me to positionate the text always in the same [...]

  6. [...] pour Pseudo Random Number Generator. heureusement deux trois gars étaient passés par là dont POLYGONAL. évidemment il a encore envoyé du pâté et je dois bien admettre que j’ai pas tout [...]

  7. [...] uses, one should go for a regular prng, be it Math.random, or one with a custom seed, such as the Park-Miller prng supplied by polygonal [...]

  8. [...] that one could take any prng, be it Math.random, a Park-Miller lcg (again, check out the one on Polygonal labs), a Mersenne twister or whatever, and map its output to the standard normal [...]

  9. [...] for the random positioning I used this PRNG: lab.polygonal.de [...]

  10. [...] visualization showing the value distribution in PRNG This entry was posted in Algorithm, Scripts, Work and tagged Generator, Number, Pseudo, Random. Bookmark the permalink. ← De Casteljau & Bezier Chaos → [...]

Get Adobe Flash player