Jump to content
  • Advertisement
Sign in to follow this  
george7378

Creating a PRNG input from three values

This topic is 843 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone,
 
I'm currently trying to create a simple procedural terrain system that I will later be able to expand and improve. So far I've created a quadtree-based system of cells which will divide based on camera proximity. When enough recursive division has occured, each cell is put into a queue and used to generate vertices for a dynamic buffer. I'm happy with my plane-generating system, but at the moment all it does is generate a flat plane with appropriate subdivision.
 
When each vertex is generated, I want to determine its height using a noise function. I'm familiar with using octaves of noise along with interpolation and 1d and 2d PRNG functions to produce perlin-style noise, but the functions I've used in the past won't quite meet my needs here. I want to have a noise function that will produce the same pseudo-random output for a given pair of x-y coordinates, but I also want to be able to set a 'seed' value that will let me generate more than one terrain output as a result.
 
I'm thinking that the simplest way to do this would be to use a 1D noise function like this one I've used before:
float hash_noise_1d(int input)
{           
    input = (input << 13)^input;
    float r = 1 - ((input*(input*input*15731 + 789221) + 1376312589) & 0x7fffffff)/float(1073741824);
    return (r + 1)/2;
}
 
...and to find a way of collapsing the x coordinate, the y coordinate and the seed down into a single integer value for input. This way, I would always get the same result for a given set of x-y coordinates combined with a given seed. So my question is: does anyone have a clever way to combine two (integer) coordinates along with an integer seed? I'm thinking that clever use of some bitwise operators would do the trick.
 
Thanks for your input :)

Share this post


Link to post
Share on other sites
Advertisement
What you are looking for is a hash function.

The following operations are all permutations of the integers in the interval [0,2^32):
* Add a constant: x + C
* Multiply by an odd constant: x * C
* XOR with a constant: x ^ C
* Rotate bits: (x >> S) + (x << (32 - S))

You can mix three integers using a sequence of those operations.

This is the first thing I would try:
// C1, C2, C3, C4, C5 and C6 are unsigned constants; pick some random values
// This code assumes 32-bit unsigned ints, which is what pretty much any compiler provides these days.
unsigned hash(unsigned x, unsigned y, unsigned z) {
  unsigned h = C1 ^ x;
  h *= C2|1u;
  h = (h << 16) + (h >> 16);
  h += C3 ^ y;
  h *= C4|1u;
  h = (h << 16) + (h >> 16);
  h += C5 ^ z;
  h *= C6|1u;
  h = (h << 16) + (h >> 16);
  return h;
}

Share this post


Link to post
Share on other sites

The most appropriate hash function depends on the size and distribution of x,y and seed, which are unlikely to cover the full range of 32 bit unsigned integers and even more unlikely to do it with equal probability and without correlation.

 

Let's call the function h(x,y,s); scaling all rational numbers to integers we can have x, y and s integers, with x1<=x<x2, y1<=y<y2, and since we can invest a lot of resources in the seed s it can be uniformly distributed between 0 and 2n, for n fairly large.

 

Since x and y are mere input values, they can be combined cheaply and leaving "holes" of invalid hash function inputs that won't be required. For example, v=x-x1+(y-y1)*(x2-x1).

 

We want the height h to have an (approximately uniform) distribution in a range that doesn't matter (more values are preferable, but it will be transformed to an arbitrary floating point range), with an obvious quality constraint: the value of h for every x,y pair should be independent. This is infeasible in practice, but it can be approximated with the well studied class of K-independent hash function families: choosing a random hash function from the family (here, for a random s), for any choice of K inputs (here, K points as x and y pairs) all hash values (here, all sequences of K heights) are equally probable.

You could try tabulation hashing, which is 3-independent: with 0<=v<2p and p=r*t and 0<=h<2q, form a table T of 2r by t numbers of q bits (all these bits are part of the seed, n=q*t*2r), split v into t r-bit numbers v0...vt-1 and output hs(v)=T(v0,0) xor T(v1,1) xor...xor T(vt-1,t-1).

 

Plausible example: q=32, and 1000*1000 terrain implying p=20; with r=4, and t=16, n=8192. For use as a single octave of noise, much lower values of q could suffice.

Share this post


Link to post
Share on other sites

What's wrong with just using Perlin/simplex noise?  You can shuffle the permutation table with a PRNG to get different results.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!