Looking for a good, quick spatial hash...
Members - Reputation: 318
Posted 24 September 2011 - 03:24 AM
Purpose is generating terrain heights in pseudo-perlin value noise.
Members - Reputation: 900
Posted 24 September 2011 - 06:52 AM
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
Members - Reputation: 2143
Posted 24 September 2011 - 06:59 AM
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.
Moderators - Reputation: 12015
Posted 24 September 2011 - 07:52 AM
My implementation uses FNV-1A hashing.
Crossbones+ - Reputation: 7822
Posted 24 September 2011 - 11:13 AM
Professional Free Software Developer
Members - Reputation: 318
Posted 24 September 2011 - 12:06 PM
@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)
Members - Reputation: 2409
Posted 24 September 2011 - 01:10 PM
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.
very involved seeding process are probably unsuitable due to the overhead of populating tables during the SetSeed process
TinyMT could be used instead, even though it has still comparatively large state.
Crossbones+ - Reputation: 19073
Posted 24 September 2011 - 02:07 PM
* 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.