2

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

但是，当我给出一个 2d 向量并将结果修改为 2 时，此代码无法产生“伪随机”输出。它产生的主要是棋盘格图案。

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

基本上，如果我输入相同的输入，我正在尝试生成一个可以返回的“无限”2D 噪声场（想想，白噪声）。

我写的代码是（它应该是一个 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;
}
4

4 回答 4

1

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

您的主要哈希混合函数fnv_hash32_next相当简单，实际上混合得不是很好。例如，如果您知道 'byte' 的最低位是 0，那么该语句hash ^= byte将保持最低位hash不变。由于16777619u是奇数，所以hash *= 16777619u始终保持最低位不变：奇数（散列）乘以奇数（16777619u）是奇数/偶数（散列）乘以奇数（16777619u）是偶数。

进一步推进这个论点，结果的最低位最终将成为输入的每个字节中最低位的异或。好吧，实际上，恰恰相反，因为你从一个奇数开始作为hashin的初始值fnv_hash32_init。这可能解释了您所看到的模式。确实，我敢打赌，如果您仔细检查，您会发现它并不完全是棋盘格。例如，对于每个 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 之类的加密哈希可能要容易得多。不要有任何幻想：使用加密散列不会使您的使用具有任何“加密安全性”。但是加密散列函数往往具有您在这里寻找的良好混合类型。

于 2012-05-06T06:10:21.337 回答
1

IMO 运作良好的东西是

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

这个想法是对具有多个比例级别的基本随机图块进行异或（我在此示例中使用 5 个级别）。您添加的级别越多，周期就越大；在这个例子中是 16**5。

于 2012-05-06T07:00:42.077 回答
0

如果你需要做的只是愚弄一个检查不那么努力的人，我只会使用标准库中的random_r()and srandom_r()。它们允许您保留一个私有状态对象，以便您可以同时激活多个不同（且唯一）的生成器。如果您愿意，可以将它们包装在一个类中以方便使用。

于 2012-05-06T04:24:56.417 回答
0

这就是 Perlin 噪音的用途。Minecraft 使用 Perlin 噪声。它使您可以立即计算字段中任何点的值，而无需先计算中间点。如果你任意生成你的世界的比特，然后你生成连接这些任意点的比特，它们将完美地匹配在一起。

于 2015-04-25T15:43:34.300 回答