Gameplay in HTML5: Random numbers

Overview

Random vs pseudo-random numbers

Good algorithms

  • The mathematical algorithms we will discuss produce sequences of numbers with excellent statistical properties:
    • They cover their range quite uniformly.
    • They exhibit very little serial correlation.
    • They do not repeat for a very long time.
  • But not truly random

    • Starting from a given state, any purely mathematical algorithm will produce the same sequence.
    • Technically they are deterministic and hence pseudo-random number generators (PRNGs).
    • They should not be used when, say, money is involved.
    • For true random numbers, special hardware is available that uses physical processes such as thermal noise.
    • Unix-like systems offer /dev/random, which "gathers environmental noise from device drivers and other sources into an entropy pool." But it can be slow or stall while waiting for new noise.
    • Since neither the hardware nor /dev/random are sure to be present on client computers, we will confine our attention to PRNGs.
    • When a true RNG or a better PRNG is needed, it will need to be provided by a server.
    • I will just say "RNG" from now on.

    Seeding

    JavaScript's built-in RNG

    Linear congruential generators

    The algorithm

    • A fast, simple, and very common RNG produces the next number, Xn+1 using
      Xn+1 = (aXn + c) mod m,
      where a, c, and m are constants chosen with care.
    • Since we always have 0 <= Xn < m, m is usually chosen to be a large integer, often 232 or even 264, depending on what the computer supports.
      JavaScript's support for integers is complicated, but 248 works.
    • The multiplier, a, must be chosen very carefully. 31167285 turns out to be a good value.
    • The value of c is not as critical. It mustn't be 0, but 1 is fine (as in fact most odd numbers would be here).
    • Another, easy-to-remember, LCG: m = 232, a = 69069, c = 1
    • In most languages mod 2n is an easy bit-wise and (or truncation at the word size). Not in JavaScript, unfortunately.

    Code

    app.lcRandom =
        (function()
         {
        //-------------------------------------------------------------------------
    
             var seed,
                 m = 0x1000000000000, //2^48
                 sqrtM = 0x1000000,
                 a = 31167285,
                 c = 1,
                 x;
             
        //=========================================================================
    
             function reseed( newSeed )
             {
                 if ( newSeed === undefined )
                 {
                     newSeed = app.stdRandom.integer( m );
                 }
                 x = seed = newSeed;
             }
             
        //-------------------------------------------------------------------------
    
             function getSeed( )
             {
                 return seed;
             }
             
        //=========================================================================
    
             function real( )
             {
                 return integer( m ) / m;
             }
             
        //-------------------------------------------------------------------------
    
             function integer( limit )
             {
                 if ( seed === undefined )
                 {
                     reseed( );
                 }
                 x = ( a * x  +  c ) % m;
                 if ( limit < sqrtM )            //When possible, just use the
                     return (x / sqrtM) % limit; // higher-order bits.
                 else
                     return x % limit;
             }
             
        //=========================================================================
    
            return {
                reseed: reseed,
                getSeed: getSeed,
                real: real,
                integer: integer
            };
             
        //-------------------------------------------------------------------------
         }
    )();
                              

    Pros and cons

    • Built-in method may be faster, use more bits, and use a better algorithm. (It can use bit-wise operations and techniques not available in JavaScript.)
    • Historically, library RNGs have sometimes been notoriously poor, though that is probably a thing of the past.
    • As noted above, the ability to set the seed can be valuable.

    Shuffling arrays

    You can randomly reorder a list like this:
    app.shuffleArray = function( array, random )
    {
        var rng = random || app.shRandom,
            len = array.length,
            i, r, tmp;
        for ( i = len - 1; i > 0; --i )
        {
            r = rng.integer( i + 1 );
            if ( r !== i )
            {
                tmp = array[ i ];
                array[ i ] = array[ r ];
                array[ r ] = tmp;
            }
        }
    };
              

    Example

    Example

    More info