# Creating a PRNG input from three values

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

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

##### Share on other sites
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 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 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.

1. 1
2. 2
Rutin
23
3. 3
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633653
• Total Posts
3013160
×