静的擬似乱数フィールドジェネレータ

Question

ゲーム用に作成した乱数ジェネレータの問題が発生しています。高速な擬似乱数発生器が必要です。それは暗号的に安全である必要はありません。ベクトルとシードを取り入れ、人間の検査を欺くだけのランダムなハッシュ値を与えるだけです。

しかし、このコードでは、2dのベクトルを与え、2でmodを計算すると「擬似乱数」の出力が得られません。ほとんどのチェッカーボードパターンが生成されます。

私はなぜ、そして正直なところ、それは知っていることが涼しいだろうが、私はそれを把握しない場合、私はそれを汗をかくことはありません。ほとんどの場合、乱数を生成するこの方法はあまりにもひどいので、私はこの問題に近づく別の方法を知りたがっています。つまり、「何が間違っているのですか」と尋ねるのではなく、このような方法で乱数を生成するための良い代替方法となるようなリソースや指針を実際に探していました。

基本的には、同じ入力を入力すると、元に戻すことができる「無限の」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はかなりシンプルで、実際にはうまく混合されません。たとえば、 'byte'の最下位ビットが0であることが分かっている場合、hash ^= byteというステートメントは、hashの最下位ビットを変更しません。 16777619uは奇数であるため、奇数（16777619u）が奇数/偶数（hash）×奇数（16777619u）の場合、常に最下位ビットは変化しません。hash *= 16777619uは常に最下位ビットを変更しません。

あなたの結果の最下位ビットは、入力の各バイトの最下位ビットのxorになります。最初の値がhashの奇数で始まり、fnv_hash32_initになるので、実際は逆です。これはあなたが見ているパターンを説明するかもしれません。確かに、私はあなたがそれがかなりチェッカーボードではないことがわかるでしょう。たとえば、（x、255）の値は、xごとに（x、256）と同じにする必要があります。

使用しているスキームは正常に動作するはずですが、より良いハッシュ関数が必要です。特に、少しうまくミックスする必要があります。以前私が使っていたリソースの1つは、Thomas Wangの書き込みでhttp://www.concentric.net/~ttwang/tech/inthash.htmでした。彼は、いくつかのサンプルコードとともに、基本的な問題の簡潔な簡潔な説明を提供します。また、Robert Jenkinsの記事へのリンク：http://www.burtleburtle.net/bob/hash/doobs.htmlもお見逃しなく。

すべてのことは、ライブラリのMD5やSHA1のような暗号化ハッシュを使うほうがはるかに簡単かもしれないということです。錯覚を起こさない：暗号ハッシュを使用しても、「暗号的に安全」なのではありません。しかし、暗号のハッシュ関数は、あなたがここで探している良い混合のタイプを持つ傾向があります。IMOはうまく動作

Answer 2

あなたがする必要があるすべては、私はちょうど標準ライブラリからrandom_r()とsrandom_r()を使用することになり、非常に難しいチェックされていない人間をだますある場合。それらはプライベートな状態オブジェクトを保持することができるので、一度に複数の異なる（そしてユニークな）ジェネレータをアクティブにすることができます。あなたが望むならば、便利なようにこれらをクラスでラップすることができます。

Answer 3

何かが

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つのレベルを使用しています）、いくつかのスケールレベルでベースランダムタイルをXORすることです。より多くのレベルを追加するほど、期間が長くなります。この例では16 ** 5です。

Answer 4

これはパーリンノイズの原因です。 MinecraftはPerlinノイズを使用します。介入ポイントを最初に計算することなく、即座にフィールドの任意のポイントで値を計算できます。任意の世界のビットを任意に生成し、これらの任意の点に結合するビットを生成すると、それらはすべて完全に一致します。