什么是游戏的好随机数生成器？

Question

什么是用于C++游戏的优秀随机数生成器？

我的考虑是:

1. 需要大量随机数,因此速度很快.
2. 玩家总会抱怨随机数字,但我希望能够将它们指向一个解释我真正完成工作的参考.
3. 由于这是一个我没有太多时间的商业项目,如果算法a)相对容易实现或者b)具有良好的非GPL实现,那将是很好的.
4. 我已经rand()在很多地方使用,所以任何其他发电机最好能够证明它需要的所有变化.

我对这个问题知之甚少,所以我能想到的唯一选择是Mersenne Twister ; 它满足所有这些要求吗？还有什么比这更好的吗？

编辑: Mersenne Twister似乎是共识的选择.但是第4点呢？它真的好多了rand()吗？

编辑2:让我对第2点更清楚一点:通过了解随机数,玩家无法作弊.期.我希望它足够随意,人们(至少那些了解随机性的人)不能抱怨它,但我并不担心预测.这就是为什么我把速度作为首要考虑因素.

编辑3:我现在倾向于Marsaglia RNG,但我仍然想要更多的输入.因此,我正在设立一个赏金.

编辑4:只是一个注释:我打算在今天午夜UTC之前接受一个答案(以避免弄乱别人的代表帽).所以如果你想回答,不要等到最后一分钟!
此外,我喜欢Marsaglia的XORshift发电机的外观.有没有人对它们有任何意见？

Answer 1

有时游戏开发者不希望真正的随机性,而洗牌包更合适.

如果您确实需要随机性,梅森捻线机可以满足您的要求.它速度快,统计随机,周期长,并且有很多实现.

编辑:rand()通常实现为线性同余生成器.如果你明智地选择它是否足够好用于你的目的,这可能是最好的.

Answer 2

现在有比Mersenne Twister更好的选择.这是一款名为WELL512的RNG,由Mersenne的设计师设计,10年后开发,是游戏的更好选择.该代码由Chris Lomont博士提交公共领域.他声称这种实现比Mersenne快40%,当状态包含许多0位时,不会受到扩散和陷阱的影响,并且显然是很简单的代码.它的周期为2 ^ 512; 一台PC需要10到100年的时间来循环通过各州,所以它足够大.

这是一篇关于PRNG的文章,在那里我发现了WELL512的实现. http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

因此 - 更快,更简单,10年后由相同的设计师创造,并产生比Mersenne更好的数字.你怎么会弄错？:)

更新(11-18-14):修正了错误(将0xDA442D20UL更改为0xDA442D24UL,如上面链接的文章中所述).

/* initialize state to random bits */
static unsigned long state[16];
/* init should also reset this to 0 */
static unsigned int index = 0;
/* return 32 bit random number */
unsigned long WELLRNG512(void)
   {
   unsigned long a, b, c, d;
   a = state[index];
   c = state[(index+13)&15];
   b = a^c^(a<<16)^(c<<15);
   c = state[(index+9)&15];
   c ^= (c>>11);
   a = state[index] = b^c;
   d = a^((a<<5)&0xDA442D24UL);
   index = (index + 15)&15;
   a = state[index];
   state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28);
   return state[index];
   }

Answer 3

乔治·马萨格利亚(George Marsaglia)开发了一些目前可用的最好和最快的RNG. 乘法携带是一个值得注意的统一分布.

===更新2018-09-12 ===

对于我自己的工作,我现在正在使用Xoshiro256**,这是对Marsaglia的XorShift的一种进化/更新.

Answer 4

Mersenne Twister是行业中的典型代表,特别是因为它非常适合SIMD并且可以超快速地制造.Knuth也很受欢迎(谢谢David).

在大多数游戏应用程序中,速度确实是关键因素,因为玩家会抱怨低帧率比他们抱怨这样一个事实,即只要它在7,2之前产生3,就会略微偏向于和9顺序.

当然例外是赌博,但您的相关许可机构将专门列出您可以使用的算法.

Answer 5

买一个便宜的webcamera,一个电离烟雾探测器.拆卸它们两者,烟雾探测器含有很少的放射性物质 - 伽马波源 - 这将导致你的摄像头发射光子.那是你真正随机性的来源:)

Answer 6

Mersenne Twister非常好,而且速度也很快.我在游戏中使用它并不是很难实现或使用它.

该井随机算法被设计为在梅森倍捻机的改善.Game Gems 7有更多信息.在它上面,如果你可以借用它或拥有它.

在我链接到的WELL页面上,数字是算法的周期.也就是说,你需要在需要重新播种之前获得2 ^ N - 1个数字,其中N是:512,1024,19937或44497.Mersenne Twister的周期为N = 19937,或2 ^ 19937 - 1.你将会看到这是一个非常大的数字 :)

我唯一可以指出的是,boost有一个随机库,你应该觉得它很有用.

为了回应你的编辑,是的Twister或WELL比rand()要好得多.此外,旧模数技巧会损害数字的分布.更有理由使用boost :)