Static Pseudorandom field generator

Question

I'm running into an issue with the random number generator I wrote for a game. I need a fast pseudorandom field generator. It does not need to be cryptographically secure, it just needs to take in a vector and a seed, and give a hashed value that's random enough to fool cursory human inspection.

However, this code is failing to produce "pseudorandom" output when I give a 2d vector and mod the result by 2. It produces a mostly checkerboard pattern.

I'm not sure why, and honestly, it would be cool to know, but I won't sweat it if I never figure it out. Mostly, I just figured that this way of generating random numbers was too terrible, so I wanted to know of an alternate way of approaching this problem. Ie, I was really seeking resources or pointers on what would be a good, alternate way to generate random numbers in this manner, rather than asking "what am I doing wrong?"

Basically, I'm trying to generate an "infinite" 2D noise field (think, white noise) that I can get back, if I put in the same inputs.

The code I wrote is (it's supposed to be an fnv hash, please excuse the template stuff. I kinda just pulled this out of the code. I'll clean it up a bit later).

//Static random number generator, will generate a random number based off of a seed and a coordinate
template<typename T, typename... TL>
uint32_t static_random_u32(T const& d, TL const&... rest) {
  return fnv_hash32(d, rest..., 2938728349u); //I'm a 32-bit prime!
}

template<typename T, typename... TL>
uint32_t fnv_hash32(T const& v, TL const&... rest) {
  uint32_t hash;
  fnv_hash32_init(hash);
  fnv_hash32_types(hash, v, rest...);
  return hash;
}

inline void fnv_hash32_init(uint32_t& hash) {
  hash = 2166136279u; //another 32-bit prime
}

// Should produce predictable values regardless of endianness of architecture
template<typename T, typename... TL>
void fnv_hash32_types(uint32_t& hash, T const& v, TL const&... rest) {
#if LITTLE_ENDIAN
  fnv_hash32_bytes(hash, (char*)&v, sizeof(v), true);
#else
  fnv_hash32_bytes(hash, (char*)&v, sizeof(v), false);
#endif
  fnv_hash32_types(hash, rest...);
}

inline void fnv_hash32_types(uint32_t& hash) {}

inline void fnv_hash32_bytes(uint32_t& hash, char const* bytes, size_t len, bool swapOrder = false) {
  if (swapOrder) {
    for (size_t i = len; i > 0; --i)
      fnv_hash32_next(hash, bytes[i - 1]);
  } else {
    for (size_t i = 0; i < len; ++i)
      fnv_hash32_next(hash, bytes[i]);
  }
}

inline void fnv_hash32_next(uint32_t& hash, char byte) {
  hash ^= byte;
  hash *= 16777619u;
}

Answer 1

I'm not an expert in this, but here's a thought and a pointer.

Your primary hash mixing function, fnv_hash32_next is fairly simple, and doesn't actually mix very well. For instance, if you know that the lowest bit of 'byte' is 0, then the statement hash ^= byte leaves the lowest bit of hash unchanged. And since 16777619u is odd, hash *= 16777619u always leaves the lowest bit unchanged: an odd number (hash) times an odd number (16777619u) is odd / an even number (hash) times an odd number (16777619u) is even.

Carrying that argument a bit further, the lowest bit of your result will just end up being the xor of the lowest bit in every byte of your inputs. Well, actually, just the opposite, since you start with an odd number as the initial value of hash in fnv_hash32_init. This might explain the pattern you're seeing. Indeed, I bet if you check closely you'll see it's not quite a checkerboard. For instance, the value for (x,255) should be the same as (x,256) for every x.

The scheme you're using should work reasonably well, but you'll need a better hash function. In particular, you need to mix a bit better. One resource I've used before was Thomas Wang's writeup at http://www.concentric.net/~ttwang/tech/inthash.htm. He gives a brief, terse description of basic issues along with some example codes. Also, don't miss his link to Robert Jenkins' article: http://www.burtleburtle.net/bob/hash/doobs.html.

All that said, it might be a lot easier to just use a cryptographic hash like MD5 or SHA1 from a library. Suffer no illusion: using a cryptographic hash won't make your use any sort of "cryptographically secure." But the cryptographic hash functions tend to have the type of good mixing you're looking for here.

Answer 2

Something that IMO works nicely is

int base[16][16]; // Random base tile

int random_value(int x, int y)
{
    return (base[y&15][x&15] ^
            base[(y>>4)&15][(x>>4)&15] ^
            base[(y>>8)&15][(x>>8)&15] ^
            base[(y>>12)&15][(x>>12)&15] ^
            base[(y>>16)&15][(x>>16)&15]);
}

The idea is to xor a base random tile with several scale levels (i'm using 5 levels in this examples). The more levels you add the larger is the period; in this example is 16**5.

Answer 3

If all you need to do is fool a human who isn't checking very hard, I would just use random_r() and srandom_r() from the standard library. They allow you to keep a private state object so you can have several different (and unique) generators active at once. You could wrap these in a class for convenience, if you wish.

Answer 4

This is what Perlin noise is for. Minecraft uses Perlin noise. It lets you calculate the value at any point in your field instantly, without having to calculate the intervening points first. If you generate bits of your world arbitrarily, and then you generate the bits that join these arbitrary points, they will all match together perfectly.