Looking for a good, quick spatial hash...

http://en.wikipedia.org/wiki/Mersenne_twister

I use something like this, simple and fast but of course you have to test if it is good enough for your situation (I think I got the algo from wikipedia, lookup PRNG)

For the first time set XORValue to your seed value.


XORValue = ( XORValue * 1664525 + 1013904223 ) & 0xFFFF;

Or in x86 assembly:

mov eax,1664525
mov edx,XORValue
mul edx ; result in edx:eax (
add eax,1013904223
mov XORValue,eax


The method given above by Ron AF Greve is generally called the Linear Congruential Method.

It is one of the simplest mechanism to use, and I can't think of a much faster method. Several C library implementations of rand() use it. There are lots of arguments in favor and against. Some say the lowest order bits have poor randomness, and while true for some instances of the LCG method, it is not a true fact in general. Knuth treats this in detail. There exists a battery of randomness tests by George Marsaglia you can use to test the randomness of different generators.

Typically, the "generators" used in a Perlin noise implementation are implemented more like a hash rather than a typical PRNG. That is, they are not seeded explicitly, but rather are seeded using the integer parts of the coordinate components, in order that the values be deterministic. So while an LCG or some type of XOR generator are commonly used, they are used in-place and without an external seed function, meaning that Mersenne or other generators that have a very involved seeding process are probably unsuitable due to the overhead of populating tables during the SetSeed process. Given that the coordinate hash tends to not have any kind of correlation between adjacent coordinate locations, it provides the illusion of randomness and is commonly considered to be "random enough". If desired, an optional seed can be considered as an additional coordinate component, so that a generator can be seeded, and the seed will be folded into the hash along with the coordinates in order to provide multiple variants.

My implementation uses FNV-1A hashing.

I use this to generate floats +-1

float sfrand( int *seed ) {
float res;
seed[0] *= 16807;
*((unsigned int *) &res) = ( ((unsigned int)seed[0])>>9 ) | 0x40000000;
return( res-3.0f );
}

Source

If you're using C++, investigate the rich PRNG library you get with #include , but I imagine one of the LCG generators is what you're going to want for Perlin generation. Try [font="Courier New"]std::minstd_rand[/font] for a good LCG, or for a faster lagged Fibonacci generator with discards (LFG is nuch faster than LCG at the expense of initialization time and memory footprint) try [font="Courier New"]std::ranlux24[/font].

I'll tackle your replies in order:

@ApochPiQ: Thanks, but as it would be seeded once for every single coordinate check (see JTippetts' post), Mersenne is not suitable.

@Ron AF Greve: Thanks, but the pseudo-random number needs to rely only on the coordinate seed value (JTippetts probably explained it well enough).

@clb: Thanks, but see above.

@JTippets: Thanks; that's the sort of information I should have provided with my post and probably would have if I weren't literally falling asleep in my chair when I posted. I may well use that; will have to test it against the one I'm using now (which is something of a hack).

@Typedef Struct: Thanks, I may well use that. Don't know yet if it's better than the one I'm using now.

@Bregma: I'm using C#, but thanks. (I really should have posted that, but, well, was literally falling asleep in my chair)

very involved seeding process are probably unsuitable due to the overhead of populating tables during the SetSeed process

They have large state. Mersenne's internal state (seed) is 19937 bits. A coordinate will be 32 bits or so. Ideally, size of internal state would be same as number of bits in coordinate, allowing them to be used interchangeably.

TinyMT could be used instead, even though it has still comparatively large state.

There are several operations you can do with 64-bit integers that are invertible (which means they don't lose data):
* Multiply by any odd constant: x *= ODD_CONSTANT;
* Add any constant: x += CONSTANT;
* XOR with any constant: x += CONSTANT;
* Swap the high and low 32-bit parts: x = (x<<32) | (x>>32);

Concatenating a few of them will twists bits around in ways that are hard to predict, which is probably what you want. For instance, you could do:
unsigned long long x = x_coordinate;
x *= 0x0c88be9b660ae531ull;
x += 0x6e8ff6fab43479c7ull;
x = (x<<32) | (x>>32);
x += y_coordinate;
x *= 0x6ea2d3951e64c421ull;
x ^= 0xa7080d55f4cc1186ull;
x = (x<<32) | (x>>32);
x *= 0xcce2e2c89c6892bfull;


It might be faster to break the long dependency chain by computing a hash for x, a hash for y and then combining them.

Just for reference, as JTippets alluded to, what you really want is a spatial hash, not a PRNG

Just for reference, as JTippets alluded to, what you really want is a spatial hash, not a PRNG

Good to know, thanks. Is it possible to rename the thread?

Done :-)


(For the record, I have no idea if regular users can do that, heh. If you do find a way to do it, let me know - I'm curious!)

Done :-)


(For the record, I have no idea if regular users can do that, heh. If you do find a way to do it, let me know - I'm curious!)

Yep. Edit, then "Use full editor".