Fast pseudo random number generator for procedural content

Question

I am looking for a pseudo random number generator which would be specialized to work fast when it is given a seed before generating each number. Most generators I have seen so far assume you set seed once and then generate a long sequence of numbers. The only thing which looks somewhat similar to I have seen so far is Perlin Noise, but it generates too "smooth" data - for similar inputs it tends to produce similar results.

The declaration of the generator should look something like:

int RandomNumber1(int seed);

Or:

int RandomNumber3(int seedX, int seedY, int seedZ);

I think having good RandomNumber1 should be enough, as it is possible to implement RandomNumber3 by hashing its inputs and passing the result into the RandomNumber1, but I wrote the 2nd prototype in case some implementation could use the independent inputs.

The intended use for this generator is to use it for procedural content generator, like generating a forest by placing trees in a grid and determining a random tree species and random spatial offsets for each location.

The generator needs to be very efficient (below 500 CPU cycles), because the procedural content is created in huge quantities in real time during rendering.

Answer 1

Seems like you're asking for a hash-function rather than a PRNG. Googling 'fast hash function' yields several promising-looking results.

For example:

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

Edit: Yep, some hash functions definitely look more suitable than others.

For your purposes, it should be sufficient to eyeball thefunction and check that a single-bit change in the input will propagate to lots of output bits.

Answer 2

Yep, you are looking for a fast integer hash algorithm rather than a PRNG.

This page has a few algorithms, I'm sure you'll find plenty more now you know the correct search terms.

Answer 3

see std::tr1::ranlux3, or other random number generators that are part of TR1 additions to the standard C++ library. I suggested mt19937 initialially, but then saw your note that it needs to be very fast. TR1 is should be available on Microsoft VC++ and GCC, and can also be found in the boost libraries which support even more compilers.

example adapted from boost documentation:

#include <random>
#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
#include <ctime>
using namespace std;
using namespace std::tr1;
int main(){
    random_device trueRand;
    ranlux3 rng(trueRand);  // produces randomness out of thin air
                            // see pseudo-random number generators
    uniform_int<> six(1,6); // distribution that maps to 1..6
                            // see random number distributions
    variate_generator<ranlux3&, uniform_int<> >
           die(rng, six);   // glues randomness with mapping

    // simulate rolling a die
    generate_n( ostream_iterator<int>(cout, " "), 10, ref(die));
}

example output:

2 4 4 2 4 5 4 3 6 2

Any TR1 random number generator can seed any other random number generator. If you need higher quality results, consider feeding the output of mt19937 (which is slower, but higher quality) into a minstd_rand or randlux3, which are faster generators.

Answer 4

If memory is not really an issue and speed is of utmost importance then you can prebuild a large array of random numbers and just iterate through it at runtime. For example have a seperate program generate 100,000 random numbers and save it as it's own file like

unsigned int randarray []={1,2,3,....}

then include that file into your compile and at runtime your random number function only needs to pull numbers from that array and loop back to the start when it hits the end.

Answer 5

Here's a small random number generator developed by George Marsaglia. He's an expert in the field, so you can be confident the generator has good statistical properties.

v = 36969*(v & 65535) + (v >> 16);
u = 18000*(u & 65535) + (u >> 16);
return (v << 16) + u;

Here u and v are unsigned ints. Initialize them to any non-zero values. Each time you generate a random number, store u and v somewhere. You could wrap this in a function to match your signature above (except the ints are unsigned.)

Answer 6

Marsaglia's PRNG above has a typo: it needs (u & 65535) in the code. See Marsaglia's post:

http://www.math.uni-bielefeld.de/~sillke/ALGORITHMS/random/marsaglia-c

Answer 7

I use the following code in my Java random number library - this has worked pretty well for me. I also use this for generating procedural content.

/**
 * State for random number generation
 */
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);

/**
 * Gets a long random value
 * @return Random long value based on static state
 */
public static long nextLong() {
 long a=state;
 state = xorShift64(a);
 return a;
}

/**
 * XORShift algorithm - credit to George Marsaglia!
 * @param a initial state
 * @return new state
 */
public static final long xorShift64(long a) {
 a ^= (a << 21);
 a ^= (a >>> 35);
 a ^= (a << 4);
 return a;
}