Back to General and Gameplay Programming

Creating a PRNG input from three values

General and Gameplay Programming Programming

Started by george7378 March 23, 2016 08:35 PM

2 comments, last by BFG 8 years, 1 month ago

george7378

1,443

Author

March 23, 2016 08:35 PM

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 :)

Sourceforge projects

alvaro

21,604

March 23, 2016 09:03 PM

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;
}

LorenzoGatti

4,648

March 24, 2016 05:44 PM

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.

Omae Wa Mou Shindeiru

BFG

1,302

March 24, 2016 08:07 PM

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

Creating a PRNG input from three values

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Creating a PRNG input from three values

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines