2011年9月25日日曜日

ゲームと乱数(Xorshift)

うえしたです。

ゲームプログラミングには必ずといってもいいほど使われる乱数ですが、
その乱数にも色々とアルゴリズムがあって精度や処理速度が違います。

C標準関数のrand()
実装はほとんど線形合同法です。
軽くてお手軽なので、最初はみんなコレ使います。
でも精度がイマイチ(範囲が0~32767で周期が短い)で
乱数シードをグローバル変数に持っていてポータブルじゃないので、
ちょっと本格的なゲームを作るときには、線形合同法や
他のアルゴリズムを使って自前実装します。

次にメルセンヌ・ツイスタ
精度は最強。2^19937-1とかいう化け物みたいな周期。
Pythonの標準乱数だったり、DXライブラリの乱数関数がコレだったりします。
でもちょっと重い。精度もゲームではちょっと大げさな気もします。

メルセンヌ・ツイスタ - Wikipedia
http://ja.wikipedia.org/wiki/メルセンヌ・ツイスタ

そこで今回紹介するのはXorshiftという擬似乱数アルゴリズムです。
Xorshiftは軽くてそこそこ高精度(2^128-1)というバランスが良いのが特徴です。

Xorshift - Wikipedia
http://ja.wikipedia.org/wiki/Xorshift

なんとWikipediaにソースコードが載っているという親切仕様!
でもあまり有名じゃないのはなんでだろ?
Wikipediaのは関数内でstatic変数を持っていてポータブルじゃないので、
Rime Bertaで使っているコードを一部改変して↓にぺたーと貼り付けました。
自己責任でよければ勝手に使ってください。

// Xorshift乱数生成クラス
class MyRand {
 unsigned int x, y, z, w;
public:
 MyRand(unsigned int seed = 88675123) {
  this->x = 123456789;
  this->y = 362436069;
  this->z = 521288629;
  this->w = seed; 
 }
 // 0~2^32-1の範囲の乱数を生成
 unsigned int Get() {
  unsigned int t;
  t = this->x ^ (this->x << 11);
  this->x = this->y;
  this->y = this->z;
  this->z = this->w;
  this->w = (this->w ^ (this->w >> 19)) ^ (t ^ (t >> 8));
  return this->w;
 }
 // min~maxの範囲の乱数を生成
 int GetRange(int min, int max) {
  unsigned int value = this->Get();
  return min + value % (max - min);
 }
};
// てすと☆こーど
int main(void)
{
 MyRand a;
 //MyRand a((unsigned int)time(NULL)); // ←実行のたびに出力変えたい場合はこっち
 printf("%u\n", a.Get());
 printf("%u\n", a.Get());
 printf("%u\n", a.Get());
 printf("%d\n", a.GetRange(0, 100));
 printf("%d\n", a.GetRange(0, 100));
 printf("%d\n", a.GetRange(0, 100));
 return 0;
}

Output: 
 3701687786
 458299110
 2500872618
 8
 18
 74

0 件のコメント:

コメントを投稿