Sign in to follow this  

Value noise that is fast, seedable and non-repeating?

This topic is 417 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 looking for tips on how to create a good point hashing / value noise solution. My input consists of two 64-bit integers. From these, I need to create a number between 0 - N, where N is configurable at runtime (it could be Int64.MaxValue, it could be say 4096). Inputs may vary only in high bits (ie may be multiples of N), so simply multiplying or XORing by a number and using modulo N may not generate any variation at all. Basically each bit in the source needs to contribute to the output.

 

I need to have some form of seed that results in variation across the whole field, and not just simple offsets. I've checked some articles, libraries and samples, but most of them seem to use lookup tables based in some way on the input coordinates. Unfortunatly, that seems to result in repetition fairly quickly, which is painfully obvious on the arbitrarily sized maps I'm generating. 

 

Additionally, I'm going to sample this map a large number of times, from multiple threads simultaneously, so it needs to be immutable after initialization and as fast as possible. I'm working in C# on a cross platform project, so let's focus on the algoritm instead of instruction level optimizations. Yes, I have profiled, and yes, it's a significant bottleneck (97% or so), but right now I'm having problems just getting good values.

 

So, any tips/pointers appreciated!

Share this post


Link to post
Share on other sites

You can "seed" Perlin/Simplex noise by shuffling the permutation table using a PRNG with a given seed.  It's immutable after that.  For speed look at SIMD implementations. 

 

Not sure I understood your input requirements.  Sounds like the appropriate hash of your input would do what you want.

Share this post


Link to post
Share on other sites
There are a number of operations you can do with 64-bit integers that are bijective:
* Add a number
* Multiply by an odd number
* Xor with a number
* Xor with a shift of your number
* Rotate bits (e.g. doing `x = (x<<24) | (x>>40);')

Using several of these operations in a row will result in a pretty good hash function.

See if this looks non-repetitive enough for you. Then try to simplify it until it's fast enough:
 
typedef unsigned long long u64;

u64 mix(u64 key) {
  key += 0x62a9d9ed799705f5;
  key ^= (key >> 33);
  key *= 0x4be98134a5976fd3;
  key ^= (key >> 33);
  key *= 0x3bc0993a5ad19a13;
  key ^= (key >> 33);

  return key;
}

u64 hash_combine(u64 x, u64 y) {
  return mix(x + mix(y));
}

Share this post


Link to post
Share on other sites

You can "seed" Perlin/Simplex noise by shuffling the permutation table using a PRNG with a given seed.  It's immutable after that.  For speed look at SIMD implementations. 

 

Not sure I understood your input requirements.  Sounds like the appropriate hash of your input would do what you want.

 

What I'm currently trying to do is replace the lowest level of a Simplex implementation with a different value noise source, because the method used by those (at least in all my tests..?) results in very obvious repetition patterns. Works fine if you are trying to fill a single texture or similar but I'm working on "infinite" maps and those repeating patterns every km or whatever breaks both immersion and in some ways gameplay.

Share this post


Link to post
Share on other sites

Sounds like you're mapping straight to noise.  Noise by itself is boring and repetitive especially at low frequencies.  The trick is to build a sufficiently complex (and interesting) function using various transformations and combinations of noise, e.g., http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html.

Share this post


Link to post
Share on other sites

See if this looks non-repetitive enough for you. Then try to simplify it until it's fast enough:

 
This is perfect! Much simpler, faster and nicer than my previous attempts (which included adding a number between 0 and N for each set bit in each input source and many variations thereof).
 

Sounds like you're mapping straight to noise.  Noise by itself is boring and repetitive especially at low frequencies.  The trick is to build a sufficiently complex (and interesting) function using various transformations and combinations of noise, e.g., http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html.


I do several different things with the noise. My primary use case is to create irregularly sized and shaped regions representing some form of biome patches. It's not realistic in any way, but it fits the gameplay very well. Each of these patches will have some form of biome type id and possibly also some form of sub-type id, which I can then use to adjust things like elevation and vegetation density.

 

Perlin and Simplex noise are very boring and repetitive, especially at low frequencies, most likely because they were designed to be used for things like seamless textures etc, but using something like what Álvaro posted as a base, it doesn't have to be. 

Share this post


Link to post
Share on other sites

This topic is 417 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this