A good Pseudo-Random Number Generator (PRNG)
April 21, 2007 on 3:24 pm | In Actionscript | 23 CommentsWhen 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());
}
[...] 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. [...]
Pingback by doesnotcompute » Blog Archive » Seed Based Pseudorandom Number Generator in Actionscript — April, 26 2007 #
[...] 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. [...]
Pingback by [ draw.logic ] AS3 Random Number Generator « — April, 30 2007 #
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
Comment by Severiaan — June, 20 2007 #
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
Comment by freshcut — October, 3 2007 #
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-
Comment by Michael — October, 4 2007 #
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
Comment by freshcut — October, 5 2007 #
[...] 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. [...]
Pingback by simplebits.org » Seeded random in ActionScript 3 — April, 12 2008 #
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
Comment by Joaqo — July, 22 2008 #
[...] 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 [...]
Pingback by Seed-based Noise Generator | HIDIHO! — December, 22 2008 #
[...] I use the Random Number Generator from Polygonal that allows me to positionate the text always in the same [...]
Pingback by Road to tag cloud 1 | Leichtgewicht — February, 16 2009 #
[...] 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 [...]
Pingback by trop bien le blog » Seed-Based Noise Generator (=>fait du bruit avec ta graine) — February, 25 2009 #
[...] 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 [...]
Pingback by True random numbers in Flash: clock drift at controul — April, 2 2009 #
[...] 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 [...]
Pingback by Controul > Standard normal distribution in as3 — April, 16 2009 #
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
Comment by Martin Heidegger — August, 12 2009 #
Just added a BSD license to the source file so you can use it wherever you want.
Comment by Michael — August, 13 2009 #
This is a fast and good PRNG
Algorithm: x_n+1 = frac(s+nx_n)
Comment by Ribeiro Alvo — August, 27 2009 #
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?
Comment by Greg — October, 23 2009 #
maybe a compiler bug, who knows. if you can reproduce the problem with a few lines drop me a note.
Comment by Michael — October, 29 2009 #
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!
Comment by Greg — October, 30 2009 #
Thanks, I was trying hard to figure out how to do this! Very useful and easy to use.
Comment by JK — January, 27 2010 #
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!
Comment by guillaume — February, 12 2010 #
I can’t reproduce this. there are many seed values that also generate values close to 1, like 985675
Comment by Michael — February, 21 2010 #
[...] for the random positioning I used this PRNG: lab.polygonal.de [...]
Pingback by Random::Align to a grid | theTconcept — April, 13 2010 #