静态伪随机字段生成器

Question

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

但是，当我给出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; 
} 

Answer 1

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

您的主要哈希混合函数fnv_hash32_next非常简单，实际上并没有很好地混合。例如，如果您知道“字节”的最低位为0，则语句hash ^= byte将保留最低位hash不变。并且由于16777619u是奇数，因此hash *= 16777619u始终保持最低位不变：奇数（散列）乘以奇数（16777619u）为奇数/偶数（散列）乘以奇数（16777619u）为偶数。

将该参数进一步进行一下，结果的最低位最终将成为输入每个字节中最低位的异或值。实际上，恰恰相反，因为你从hash的初始值开始，在fnv_hash32_init中有一个奇数。这可能会解释你所看到的模式。事实上，我敢打赌，如果你仔细检查，你会发现它不是棋盘格。例如，对于每个x，（x，255）的值应该与（x，256）相同。

您使用的方案应该工作得相当好，但您需要更好的散列函数。特别是，你需要混合一点。我之前使用的一个资源是Thomas Wang的书面文章http://www.concentric.net/~ttwang/tech/inthash.htm。他对基本问题以及一些示例代码进行了简短而简洁的描述。此外，不要错过他与罗伯特詹金斯的文章链接：http://www.burtleburtle.net/bob/hash/doobs.html。所有这一切说，从库中使用像MD5或SHA1这样的密码散列可能会容易得多。不要错过：使用加密哈希不会使您使用任何类型的“加密安全”。但是密码散列函数往往有你想要的混合类型。

Answer 2

如果你需要做的就是糊弄谁不检查很辛苦人类，我只想用random_r()和srandom_r()从标准库。它们允许你保留一个私有状态对象，这样你可以同时拥有多个不同的（和唯一的）生成器。如果你愿意，你可以将它们包装在一个类中以方便使用。

Answer 3

东西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。

Answer 4

这是柏林噪音的用途。 Minecraft使用Perlin噪音。它可以让您立即计算场地中任意点的数值，而无需首先计算中间点。如果你随心所欲地生成你的世界的一部分，然后你生成加入这些任意点的位，它们将完全匹配在一起。