什么是一个好的随机数发生器的游戏?

What is a good random number generator to use for a game in C++?

在c++中，一个好的随机数生成器是什么?

My considerations are:

我的考虑是:

Lots of random numbers are needed, so speed is good.
需要很多随机数，所以速度是好的。
Players will always complain about random numbers, but I'd like to be able to point them to a reference that explains that I really did my job.
球员们总是会抱怨随机数，但我希望能让他们知道我真的做了我的本职工作。
Since this is a commercial project which I don't have much time for, it would be nice if the algorithm either a) was relatively easy to implement or b) had a good non-GPL implementation available.
由于这是一个商业项目，我没有太多的时间，如果算法a)相对容易实现或者b)有一个好的非gpl实现，那就太好了。
I'm already using rand() in quite a lot of places, so any other generator had better be good to justify all the changes it would require.
我已经在很多地方使用了rand()，所以最好其他任何生成器都能很好地证明它所需要的所有更改。

I don't know much about this subject, so the only alternative I could come up with is the Mersenne Twister; does it satisfy all these requirements? Is there anything else that's better?

我对这个主题不太了解，所以我能想到的唯一的选择就是梅尔森龙卷风;它满足所有这些要求吗?还有什么更好的吗?

Edit: Mersenne Twister seems to be the consensus choice. But what about point #4? Is it really that much better than rand()?

编辑:Mersenne Twister似乎是大家一致的选择。但是点4呢?它真的比rand()好多了吗?

Edit 2: Let me be a little clearer on point 2: There is no way for players to cheat by knowing the random numbers. Period. I want it random enough that people (at least those who understand randomness) can't complain about it, but I'm not worried about predictions. That's why I put speed as the top consideration.

编辑2:让我在第二点更清楚一点:玩家不可能通过知道随机数来作弊。时期。我希望它足够随机，让人们(至少是那些理解随机性的人)不会抱怨它，但我不担心预测。这就是为什么我把速度放在首位。

Edit 3: I'm leaning toward the Marsaglia RNGs now, but I'd still like more input. Therefore, I'm setting up a bounty.

编辑3:我现在倾向于使用Marsaglia RNGs，但我还是想要更多的输入。所以，我准备了一笔赏金。

Edit 4: Just a note: I intend to accept an answer just before midnight UTC today (to avoid messing with someone's rep cap). So if you're thinking of answering, don't wait until the last minute!
Also, I like the looks of Marsaglia's XORshift generators. Does anyone have any input about them?

编辑4:只是一个提示:我打算在UTC时间今天午夜之前接受一个答案(以避免弄乱某人的代表帽)。所以如果你想要回答，不要等到最后一分钟!另外，我喜欢Marsaglia的XORshift发电机的外观。有人对他们有什么看法吗?

16 个解决方案

#1

George Marsaglia has developed some of the best and fastest RNGs currently available Multiply-with-carry being a notable one for a uniform distribution.

George Marsaglia开发了一些最好的和最快的RNGs，目前可用的multiplwith -carry是一个值得注意的统一发行版本。

#2

Sometimes game developers don't want true randomness and a shuffle bag is more appropriate.

有时游戏开发者不想要真正的随机性，而洗牌更合适。

If you do want randomness, the Mersenne twister satisfies your requirements. It is fast, statistically random, has a long period and there are plenty of implementations out there.

如果您确实想要随机性，Mersenne twister满足您的需求。它是快速的，统计上随机的，有很长一段时间，并且有很多的实现。

Edit: rand() is typically implemented as a linear congruential generator. It's probably best if you make an informed choice of whether or not it's good enough for your purposes.

编辑:rand()通常被实现为一个线性一致性生成器。如果你能做出明智的选择是否足够好，这可能是最好的选择。

#3

There are much better choices than Mersenne Twister nowadays. Here is a RNG called WELL512, designed by the designers of Mersenne, developed 10 years later, and an all around better choice for games. The code is put in the public domain by Dr. Chris Lomont. He claims this implementation is 40% faster than Mersenne, does not suffer from poor diffusion and trapping when the state contains many 0 bits, and is clearly a lot simpler code. It has a period of 2^512; a PC takes over 10^100 years to cycle through the states, so it is large enough.

现在有比Mersenne Twister更好的选择。这是一款名为WELL512的RNG游戏，由Mersenne的设计师设计，10年后开发，是一款更适合游戏的游戏。这些代码由克里斯·洛蒙特博士(Chris Lomont)公布。他声称，这个实现比Mersenne快40%，当状态包含许多0位时，不会出现很差的扩散和捕获，而且很明显，代码要简单得多。它有一段2 ^ 512;电脑接管10 ^ 100年循环状态,所以它是足够大的。

Here is a paper overviewing PRNGs where I found the WELL512 implementation. http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

这是一篇概述PRNGs的论文，我在其中发现了WELL512实现。http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

So - faster, simpler, created by the same designers 10 years later, and produces better numbers than Mersenne. How can you go wrong? :)

所以-更快，更简单，由同一设计师在10年后创造，并产生比Mersenne更好的数字。你怎么可能出错呢?:)

UPDATE (11-18-14): Fixed error (changed 0xDA442D20UL to 0xDA442D24UL, as described in the paper linked above).

更新(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];
   }

#4

Mersenne Twister is typical in the industry, especially since it lends itself well to SIMD and can be made super fast. Knuth is popular too (thanks, David).

Mersenne Twister在业界是典型的，尤其是因为它很适合SIMD，而且可以制作得非常快。Knuth也很受欢迎(谢谢，David)。

In most game applications speed is really the critical factor, since players are going to complain about low framerate a lot more than they will complain about the fact that there is a slight bias towards generating a 3 whenever it is preceded by a 7, 2, and 9 in that order.

在大多数游戏应用程序速度是关键因素,因为球员们会抱怨低帧速率远高于他们会抱怨这一事实有一个轻微的偏向生成3之前在7、2和9的顺序。

The exception of course is gambling for money, but there your relevant licensing authority will specifically lay out the algorithms that you can use.

当然，唯一的例外是为了钱而赌博，但是你的相关授权机构会专门列出你可以使用的算法。

#5

Buy a cheap webcamera, a ionizing smoke detector. Disassemble both of them, smoke detector contain little radioactive material - a source of gamma waves - which will result in firing photons at your webcamera. That's your source of true randomness :)

买一个便宜的webcamera，一个电离烟雾探测器。把它们拆开，烟雾探测器含有少量的放射性物质——伽马波的来源——这将导致你的网络摄像头发射光子。这就是真正随机性的来源

#6

Mersenne Twister is very good, and it's fast as well. I used it in a game and it's not hard at all to implement or use.

Mersenne Twister非常好，而且速度也很快。我在游戏中使用过它，它的实现和使用并不困难。

The WELL random algorithm was designed as an improvement over the Mersenne Twister. Game Gems 7 has more info. on it, if you can borrow that or have it.

井的随机算法是对梅森恩绕射器的改进。游戏Gems 7有更多信息。在上面，如果你能借到或拥有它。

On that WELL page I linked you to, the number is the period of the algorithm. That is, you can get 2^N - 1 numbers before it needs reseeding, where N is: 512, 1024, 19937, or 44497. Mersenne Twister has a period of N = 19937, or 2^19937 - 1. You'll see this is a very large number :)

在我链接到的那个页面上，数字是算法的周期。也就是说,您可以得到2 ^ N - 1数字之前需要再播,其中N是:512,1024,19937,19937。梅森素数捻线机一段N = 19937,或2 ^ 19937 - 1。你会发现这是一个很大的数字

The only other thing I can point out is that boost has a random library, which you should find useful.

我唯一能指出的是boost有一个随机库，您应该会发现它很有用。

In response to your edit, yes the Twister or WELL is that much better than rand(). Also, the old modulus trick harms the distribution of the numbers. Even more reason to use boost :)

对于您的编辑，是的，Twister或WELL比rand()要好得多。同样，老模变换也会影响数字的分布。更有理由使用boost:

#7

In a real-time game, there's no way for a player to determine the difference between a "good" generator and a "bad" one. In a turn-based game, you're right--some minority of zealots will complain. They'll even tell you stories, in excruciating detail, of how you ruined their lives with a bad random number generator.

在实时游戏中，玩家无法判断“好的”生成器和“坏的”生成器的区别。在一个基于回合的游戏中，你是对的——少数*者会抱怨。他们甚至会用一个糟糕的随机数生成器来讲述你如何毁了他们的生活。

If you need a bunch of genuine random numbers (and you're an online game), you can get some at Random.org. Use them for turn-based games, or as seeds for real-time games.

如果你需要一些真正的随机数(你是一个在线游戏)，你可以在Random.org上找到。用它们做回合制游戏，或者作为实时游戏的种子。

#8

I'm a fan of Isaac, unlike mersense twister, it's crypographically secure (you *can't crack the period by observing the rolls)

我是艾萨克的粉丝，不像mersense twister，它是加密的(你不能通过观察卷轴来破解周期)

IBAA (rc4?) is also one that is used by blizzard to prevent people from predicting the random number used for loot rolls.. I imagine something similar is done w/ diablo II when you are playing off of a battle.net server.

IBAA (rc4?)也是暴雪用来阻止人们预测抢劫卷的随机数的工具。我想，当你从战网服务器上玩的时候，也会有类似的事情发生。

*can't within any reasonable timeframe (centuries?)

*不能在任何合理的时间范围内(几个世纪?)

#9

Based on the random number generator by Ian C. Bullard:

基于Ian C. Bullard的随机数发生器:

// utils.hpp
namespace utils {
    void srand(unsigned int seed);
    void srand();
    unsigned int rand();
}

// utils.cpp
#include "utils.hpp"
#include <time.h>

namespace {
    static unsigned int s_rand_high = 1;
    static unsigned int s_rand_low = 1 ^ 0x49616E42;
}

void utils::srand(unsigned int seed)
{
    s_rand_high = seed;
    s_rand_low = seed ^ 0x49616E42;
}

void utils::srand()
{
    utils::srand(static_cast<unsigned int>(time(0)));
}

unsigned int utils::rand()
{
    static const int shift = sizeof(int) / 2;
    s_rand_high = (s_rand_high >> shift) + (s_rand_high << shift);
    s_rand_high += s_rand_low;
    s_rand_low += s_rand_high;
    return s_rand_high;
}

Why?

为什么?

very, very fast
非常非常快
higher entropy than most standard rand() implementations
比大多数标准rand()实现的熵更高
easy to understand
容易理解的

#10

An additional criteria you should consider is thread safety. (And you should be using threads in todays multi-core environments.) Just calling rand from more than one thread can mess with it's deterministic behavior (if your game depends on that). At the very least I'd recommend you switch to rand_r.

您应该考虑的另一个标准是线程安全性。(您应该在今天的多核环境中使用线程。)仅仅从多个线程调用rand就会扰乱它的确定性行为(如果您的游戏依赖于此)。至少我建议你改用rand_r。

#11

I'd vote for the Mersenne Twister as well. Implementations are widely available, it has a very large period of 2^19937 -1, is reasonably fast and passes most randomness tests including the Diehard tests developed by Marsaglia. rand() and Co., being LCGs, produce lower quality deviates and their successive values can be easily inferred.

我也会投梅森恩龙卷风的票。实现普及,它有一个非常大的段2 ^ 19937 1,相当快,经过大多数顽固的随机性测试包括测试由马。rand()和Co作为LCGs，产生较低的质量偏差，它们的连续值很容易推断出来。

One point of note, however, is to properly seed MT into a state that passes randomness tests. Usually a LCG like drand48() is used for that purpose.

然而，值得注意的一点是，要正确地将MT种入通过随机性测试的状态。通常，像drand48()这样的LCG是用于这个目的的。

I'd say the MT satisfies all the requirements you've set (provably), and it'd be an overkill to go for something like MWCG imo.

我想说MT满足了你所设定的所有要求(可以证明)，而像MWCG这样的东西就太过分了。

#12

You know what? Forgive me if you think this answer completely sucks... But I've been (for god only knows what reason...) using DateTime.Now.Milliseconds as a way to get a random number. I know it's not completely random, but it appears to be...

你知道吗?如果你认为这个答案很糟糕，请原谅我……但我已经(因为上帝只知道什么原因…)使用日期。作为一种获取随机数的毫秒数。我知道这不是完全随机的，但它看起来……

I just couldn't be bothered typing so much JUST to get a random number! :P

我只是不想为了得到一个随机数而费劲地输入那么多!:P

#13

GameRand implement the algorithm posted here http://www.flipcode.com/archives/07-15-2002.shtml

GameRand实现发布在这里的算法http://www.flipcode.com/archives/07-15-2002.shtml

This is something I originally developed in the late 80s. It easily beat rand() in term of numerical quality, and as the side benefit to be the fastest random algorithm possible.

这是我在80年代末发明的。就数值质量而言，它很容易打败rand()，同时它还可以成为最快的随机算法。

#14

I want it random enough that people (at least those who understand randomness) can't complain about it, but I'm not worried about predictions.

我希望它足够随机，让人们(至少是那些理解随机性的人)不会抱怨它，但我不担心预测。

A-ha!

啊哈!

There's your real requirement!

你真正的需求!

No one could fault you for using Mersenne Twister in this application.

在这个应用程序中使用Mersenne Twister，没有人会指责你。

#15

Depending on the target OS, you might be able to use /dev/random. It doesn't really require any implementation, and on Linux (and maybe some other operating systems) it's truly random. The read blocks until sufficient entropy is available, so you might want to read the file and store it in a buffer or something using another thread. If you can't use a blocking read call, you can use /dev/urandom. It generates random data almost as well as /dev/random, but it reuses some random data to give output instantly. It's not as secure, but it could work fine depending on what you plan to do with it.

根据目标OS，您可能可以使用/dev/ randomting。它并不需要任何实现，而且在Linux(可能还有其他一些操作系统)上，它确实是随机的。读取块直到足够的熵可用，所以您可能想要读取文件并将其存储在缓冲区中或使用其他线程。如果您不能使用阻塞读调用，您可以使用/dev/ urandomm。它生成的随机数据几乎和/dev/random一样多，但它重用了一些随机数据，以便立即输出。它没有那么安全，但是根据你打算用它做什么，它可以很好地工作。

#16

Apparently (I forget where I read it, just like I forget where I read that curry is good to prevent altzheimas), taking the absolute value of the checksum of a newly generated GUID is nicely random. It's a large number, and you can use a modulo of it to shrink it down.

显然(我忘记了我在哪里读的，就像我忘记了在哪里读到curry是用来防止altzheimas一样)，取新生成的GUID的校验和的绝对值是很随机的。它是一个很大的数，你可以用它的模来缩小它。

So in SQL (my area), this is ABS(CHECKSUM(NEWID())) % 1000

在SQL (my area)中，这是ABS(CHECKSUM(NEWID()))) % 1000

Rob

罗伯

#1