c++ - 静态伪随机场发生器

Question

我为游戏编写的随机数生成器遇到了问题。我需要一个快速的伪随机场发生器。它不需要密码安全，它只需要接受一个 vector 和一个种子，并给出一个足够随机的散列值来愚弄粗略的人类检查。

但是，当我给出一个二维 vector 并将结果乘以 2 时，这段代码无法生成“伪随机”输出。它生成的主要是棋盘格图案。

我不确定为什么，老实说，知道会很酷，但如果我永远弄不明白，我也不会担心。大多数情况下，我只是觉得这种生成随机数的方法太糟糕了，所以我想知道解决这个问题的另一种方法。也就是说，我真的是在寻找资源或指示，以了解以这种方式生成随机数的另一种好方法，而不是问“我做错了什么？”

基本上，我正在尝试生成一个“无限”的二维噪声场(想象一下，白噪声)，如果我输入相同的输入，我可以返回该噪声场。

我写的代码是(它应该是一个 fnv 哈希，请原谅模板的东西。我有点把它从代码中拉出来。我稍后会清理它)。

//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

我不是这方面的专家，但这里有一个想法和一个指针。

您的主要哈希混合函数 fnv_hash32_next 相当简单，实际上混合得不是很好。例如，如果您知道“byte”的最低位为 0，则语句 hash ^= byte 会保留 hash 的最低位不变。由于 16777619u 是奇数，hash *= 16777619u 始终保持最低位不变:奇数 (hash) 乘以奇数 (16777619u) 是奇数/偶数(hash) 乘以奇数 (16777619u) 是偶数。

进一步讨论该论点，结果的最低位最终将成为输入每个字节中最低位的异或。好吧，实际上恰恰相反，因为你在fnv_hash32_init中以奇数作为hash的初始值。这可能解释了您所看到的模式。事实上，我敢打赌，如果你仔细检查，你会发现它并不完全是一个棋盘。例如，对于每个 x，(x,255) 的值应该与 (x,256) 相同。

您使用的方案应该工作得相当好，但您需要更好的散列函数。特别是，您需要更好地混合。我以前用过的一个资源是 Thomas Wang 在 http://www.concentric.net/~ttwang/tech/inthash.htm 上的文章.他对基本问题进行了简短的描述，并提供了一些示例代码。另外，不要错过他指向 Robert Jenkins 文章的链接:http://www.burtleburtle.net/bob/hash/doobs.html .

总而言之，使用库中的 MD5 或 SHA1 等加密散列可能会容易得多。不要有错觉:使用加密散列不会使您的使用具有任何“加密安全性”。但是加密哈希函数往往具有您在这里寻找的良好混合类型。