CODEWITHSUNDEEP
c#randomunity-game-engine
Nicholas Pipitone
Nicholas Pipitone

Reputation: 4142

Custom Random Number Generator

Is it possible to get an extremely fast, but reliable (Same input = same output, so I can't use time) pseudo-random number generator? I want the end result to be something like float NumGen( int x, int y, int seed ); so that it creates a random number between 0 and 1 based on those three values. I found several random number generators, but I can't get them to work, and the random number generator that comes with Unity is far to slow to use. I have to make about 9 calls to the generator per 1 meter of terrain, so I don't really care if it's not perfectly statistically random, just that it works really quickly. Does anyone know of an algorithm that fits my needs? Thanks :)

Upvotes: 3

Views: 5420

Answers (2)

schwer
schwer

Reputation: 279

I guess you had to create a Random instance on every call to NumGen. To get the function to return the same number for the same parameters you could use a hash function.

I tested a few things, and this code was about 3 times faster than recreating intances of Random.

//System.Security.Cryptography
static MD5 hasher = MD5.Create();
static byte[] outbuf;
static byte[] inbuf = new byte[12];
static float floatHash(uint x, uint y, uint z) {
    inbuf[0]= (byte)(x >> 24);
    inbuf[1]=(byte)(x >> 16);
    inbuf[2]=(byte)(x >> 8);
    inbuf[3]=(byte)(x);
    inbuf[4]=(byte)(y >> 24);
    inbuf[5]=(byte)(y >> 16);
    inbuf[6]=(byte)(y >> 8);
    inbuf[7]=(byte)(y);
    inbuf[8]=(byte)(z >> 24);
    inbuf[9]=(byte)(z >> 16);
    inbuf[10]=(byte)(z >> 8);
    inbuf[11]=(byte)(z);
    outbuf = hasher.ComputeHash(inbuf);
    return ((float)BitConverter.ToUInt64(outbuf, 0))/ulong.MaxValue;
}

Another method using some RSA methods is about 5 times faster than new System.Random(seed):

static uint prime = 4294967291;
static uint ord = 4294967290;
static uint generator = 4294967279;
static uint sy;
static uint xs;
static uint xy;
static float getFloat(uint x, uint y, uint seed) {
    //will return values 1=> x >0; replace 'ord' with 'prime' to get 1> x >0
    //one call to modPow would be enough if all data fits into an ulong
    sy = modPow(generator, (((ulong)seed) << 32) + (ulong)y, prime);
    xs = modPow(generator, (((ulong)x) << 32) + (ulong)seed, prime);
    xy = modPow(generator, (((ulong)sy) << 32) + (ulong)xy, prime);
    return ((float)xy) / ord;
}
static ulong b;
static ulong ret;
static uint modPow(uint bb, ulong e, uint m) {
    b = bb;
    ret = 1;
    while (e > 0) {
        if (e % 2 == 1) {
            ret = (ret * b) % m;
        }
        e = e >> 1;
        b = (b * b) % m;
    }
    return (uint)ret;
}

I ran a test to generate 100000 floats. I used the index as seed for System.Random and as x parameter of floatHash (y and z were 0).

System.Random: Min: 2.921559E-06 Max: 0.9999979 Repetitions: 0

floatHash MD5: Min: 7.011156E-06 Max: 0.9999931 Repetitions: 210 (values were returned twice)

getFloat RSA: Min: 1.547858E-06 Max: 0.9999989 Repetitions: 190

Upvotes: 1

Sam Axe
Sam Axe

Reputation: 33738

I think you are underestimating the System.Random class. It is quite speedy. I believe your slow down is related to creating a new instance of the Random class on each call to your NumGen method.

In my quick test I was able to generate 100,000 random numbers using System.Random in about 1 millisecond.

To avoid the slow down consider seed points in your 2D plane. Disperse the seed points so that they cover a distance no greater than 100,000 meters. Then associate (or calculate) the nearest seed point for each meter, and use that point as your seed to System.Random.

Yes, you will be generating a ton of random numbers you will never use, but they are virtually free.

Pseudo-code:

double NumGen(x, y, distance, seed) {
  Random random = new Random(seed);
  double result = 0;
  for (int i=0; i<distance; i++) {
    result = random.NextDouble();
  }
}

You could modify this simple outline to return a sequence of random numbers (possibly representing a grid), and couple that with a caching mechanism. That would let you conserve memory and improve (lessen) CPU consumption.

Upvotes: 3

Related Questions