2

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

ただし、このコードは、2 次元ベクトルを指定して結果を 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

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 に答える
1

私はこれの専門家ではありませんが、ここに考えと指針があります。

プライマリ ハッシュ ミキシング関数fnv_hash32_nextはかなり単純で、実際にはうまくミキシングされません。たとえば、'byte' の最下位ビットが 0 であることがわかっている場合、ステートメントhash ^= byteは の最下位ビットをhash変更しません。16777619uは奇数であるため、常にhash *= 16777619u最下位ビットは変更されません。奇数 (ハッシュ) 倍の奇数 (16777619u) は奇数 / 偶数 (ハッシュ) 倍の奇数 (16777619u) は偶数です。

その引数をもう少し進めると、結果の最下位ビットは、入力の各バイトの最下位ビットの xor になります。実際には、 in の初期値として奇数から開始するため、正反対hashですfnv_hash32_init。これは、あなたが見ているパターンを説明するかもしれません. 確かに、よく調べてみると、市松模様ではないことがわかるでしょう。たとえば、(x,255) の値は、すべての x の (x,256) と同じでなければなりません。

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

そうは言っても、ライブラリから MD5 や SHA1 などの暗号化ハッシュを使用する方がずっと簡単かもしれません。幻想に苦しむ必要はありません: 暗号化ハッシュを使用しても、「暗号化された安全」を使用することはできません。しかし、暗号化ハッシュ関数は、ここで探しているタイプの適切な混合を行う傾向があります。

于 2012-05-06T06:10:21.337 に答える
0

あまり熱心にチェックしていない人間をだますだけなら、標準ライブラリのrandom_r()andを使用するだけです。srandom_r()プライベートな状態オブジェクトを保持できるため、複数の異なる (そして一意の) ジェネレーターを一度にアクティブにすることができます。必要に応じて、便宜上これらをクラスにラップできます。

于 2012-05-06T04:24:56.417 に答える