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”

How to debug fast-paced action games

During the development of my last game I took a different approach of debugging it which is especially useful for real time games. Because it’s so simple I’m wondering why I haven’t used this method before (perhaps too lazy ? ;-)) Usually you include a bunch of trace statements everywhere or create a logger system which prints out the information you need. But this is useless in games where many simultaneous events occur. Your logger will be flooded with messages so it’s hard to keep track of everything.

The idea is to include a simple playback control by using keys or invoking a custom breakpoint() method, so you can stop and resume the game at any time and trace out additional information with it. Here is how it’s done (again, basic stuff here):

var updateGame:Boolean = true;
var useBreakpoints:Boolean = false;

//main loop: update game logic, render scene..
function tick():Void
{
	if (!updateGame) return;

	update();
	render();
}

function update():Void
{
	//...
	if (player.collides(wall)) breakpoint("player-wall collision");
	//...
}

So whenever the player collides with the wall, the game stops and prints out the passed string. The breakpoint function itself can look like this:

function breakpoint(message:String, forced:Boolean):Void
{
    //just quit if breakpoints are disabled
    //this can be overridden by setting forced=true
    if (!useBreakpoints && !forced) return;

    //print out message and stop game
    trace("breakpoint:" + message);
    updateGame = false;
}

Obviously, when breakpoint() is called, ‘updateGame’ is set to false so the main loop stops doing anything. The function also checks if breakpoints are enabled so you can globally turn them on or off. Furthermore, you have the option to call breakpoint() with a forced flag, so even if breakpoints are entirely disabled, your game will stop at that point. This is useful to keep some breakpoints active for very rare events or stuff you aren’t sure is working at all and at the same time you can test the game without being constantly bothered by existing regular breakpoints. I have also defined some keys:

function onKeyDown()
{
    switch (String.fromCharCode(Key.getAscii()))
    {
        //stop/resume game
        case "u":

            updateGame = !updateGame;
            break;

        //toggle breakpoints
        case "b":

            useBreakpoints = !useBreakPoints;
            trace("breakpoints " + (useBreakpoints ? "on" : "off"));
            break;

        //step through game
        case "s": 

            if (!updateGame)
            {
                update();
                render();
            }
            break;
    }
}

Game playback is toggled with ‘u’, and when the game is frozen by a breakpoint call, you can advance frame-by-frame by pressing the ’s’ key or resume playing by pressing ‘u’. This makes debugging much easier because you actually now have the time to think about what’s going on when something goes wrong ;-).

Updates

Its been a while since my last post. First I was sick for two weeks and then hired to make another flash game. Now that everything has settled down a bit I can continue working on my physics code. Some things that are coming up:
Try to release a beta version of my data structures package in the next two week for AS3 (currently half-way done) and of course getting a usable version of my physics engine done ASAP. There are some other great flash physics engines in development, and to stand out from the crowd, I try to go for the performance trophy, adding more features after I have established a stable and fast groundwork. My philosophy is therefore: prefer performance over features.