Unreal Engine PRNG

blog

はじめに

Unreal Engineの疑似乱数生成器について調査します.

Unreal Engineの疑似乱数生成器は次の３つがあります.

  • FGenericPlatformMath::Rand
    • libcのrandのラッパー
  • FRandomStream
    • 独自の線形合同法
    • 構造体なので, 状態を独立して作ることができる
  • Random.ush
    • アルゴリズムをいくつか用意
    • PCGがあるのはここ
    • シェーダ内のハッシュ関数として使用される

範囲指定

範囲指定疑似乱数は次の２つです. 境界の包含が異なります. これはBlueprintでもそのままです.

// [0 1)
float frand();

// [0 max_)
int range(int max_)
{
    return (0<max_)? trunc_to_int(frand()*max_) : 0;
}

// [min_ max_]
int range(int min_, int max_)
{
    return min_ + range(max_-min_+1);
}

FRandomStream

次のような独自の線形合同法です. RFC 6716に同じパラメータがありますが, こちらはOpusのコーデックで疑似乱数としての性能は求めていないようにみえます.

uint32_t rand()
{
    seed = (seed * 196314165U) + 907633515U;
    return seed;
}

考察

範囲指定

FMathやFRandomStream経由で範囲指定する場合は次の計算になります.

trunc_to_int(frand()*max_)

エンジン内ではFGenericPlatformMath::RandやFRandomStream::GetUnsignedIntを直接呼び出し次のように余りを計算します. ほとんどは単体テストのコードですが, ランタイムのコードでも, 理解して意図的にしているのかわかりませんが, 余りを使用しています.

FGenericPlatformMath::Rand()%4

[0 1)の浮動小数点数を使う方法, 余りを使う方法, どちらも偏りがあることが知られています.

Blueprintから使う場合

整数を得たい場合は必ず範囲指定になります. 線形合同法の下位ビットに周期性がある弱点もあまり目立ちません. 浮動小数点数を経由するため, もとの疑似乱数生成器の周期よりずっと短くなります. また, range(2147483647)のような意地の悪いことをすると偶数しかでなくなります.

FGenericPlatformMath::Rand

リンクするlibcに依存するため, 性質は予測できません. 種を保存しておいて状態を再現するなどはできないと思っておいた方がいいです.

FRandomStream

C++からはFRandomStream::GetUnsignedIntを直接呼び出せます. 線形合同法そのままの値なので, 例えば偶数と奇数が交互に出現するなどの性質はそのままになります.

まとめ

よく周知されていない辺りをみると, Unreal Engineに詳しい方々にとっては常識で, とるに足らないことなのでしょう.

Blueprintから呼び出す場合, 大きな範囲を指定しない限り, それほど問題にならないと思います.

C++から呼び出す場合, ターゲットプラットフォームごとのrand()の性質や線形合同法の性質をよく理解しておいた方がいいでしょう. FRandomStreamについては, エンジン改造して誰が扱ってもそれなりに動くようにしてしまってもいいかもしれません. Async/Fundamental/LocalQueue.hにある, FRandomStream::GetUnsignedInt()%4が周期性を利用しようとした意図的なものなのか確認する必要はあります.

統計的な品質や長い周期が必要な場合, 開発者全員が疑似乱数生成器について熟知しなくても扱えるようにしたい場合, は自前の実装を用意しましょう.

範囲指定

偏りのある方法ならば浮動小数点数を使う方法をお勧めします. 上位ビットから使うことになるので, 線形合同法のような下位ビットに顕著な周期性のある疑似乱数生成器でもそれなりの結果が得られます.

偏りのない結果を得たい場合はC++ STLを使うか, Efficiently Generating a Number in a Rangeを参考に実装するといいでしょう.

ToDo

  • 広大なボックス範囲のランダムな３次元点, など高次元での周期性について調査する