• Create Account

## Looking for a good, quick spatial hash...

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

13 replies to this topic

### #1Narf the Mouse  Members

Posted 24 September 2011 - 03:24 AM

Looking for a single-function pRNG with a reasonably long period. That is to say, something I can just call .Generate(seed) on. Speed is also a requirement.

Purpose is generating terrain heights in pseudo-perlin value noise.

Thanks.

### #2ApochPiQ  Moderators

Posted 24 September 2011 - 05:53 AM

http://en.wikipedia.org/wiki/Mersenne_twister
Wielder of the Sacred Wands

### #3Ron AF Greve  Members

Posted 24 September 2011 - 06:52 AM

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 (
mov XORValue,eax


Ron AF Greve

### #4clb  Members

Posted 24 September 2011 - 06:59 AM

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.
Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

### #5JTippetts  Moderators

Posted 24 September 2011 - 07:52 AM

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.

### #6typedef struct  Members

Posted 24 September 2011 - 08:18 AM

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
Anthony Umfer

### #7Bregma  Members

Posted 24 September 2011 - 11:13 AM

If you're using C++, investigate the rich PRNG library you get with #include <random>, but I imagine one of the LCG generators is what you're going to want for Perlin generation. Try std::minstd_rand 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 std::ranlux24.
Stephen M. Webb
Professional Free Software Developer

### #8Narf the Mouse  Members

Posted 24 September 2011 - 12:06 PM

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)

### #9Antheus  Members

Posted 24 September 2011 - 01:10 PM

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.

### #10Álvaro  Members

Posted 24 September 2011 - 02:07 PM

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.

### #11ApochPiQ  Moderators

Posted 24 September 2011 - 07:03 PM

Just for reference, as JTippets alluded to, what you really want is a spatial hash, not a PRNG
Wielder of the Sacred Wands

### #12Narf the Mouse  Members

Posted 24 September 2011 - 08:35 PM

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?

### #13ApochPiQ  Moderators

Posted 24 September 2011 - 09:22 PM

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!)
Wielder of the Sacred Wands

### #14Narf the Mouse  Members

Posted 25 September 2011 - 12:02 AM

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".

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.