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

What is a good random number generator for a game?

提问by Michael Myers

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

在 C++ 中用于游戏的好的随机数生成器是什么？

My considerations are:

我的考虑是：

1. Lots of random numbers are needed, so speed is good.
2. 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.
3. 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.
4. 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.

1. 需要很多随机数，所以速度很好。
2. 玩家总是会抱怨随机数，但我希望能够向他们指出一个参考资料，说明我确实做到了我的工作。
3. 由于这是一个我没有太多时间进行的商业项目，如果算法 a) 相对容易实现或 b) 有一个很好的非 GPL 实现可用，那就太好了。
4. 我已经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?

我对这个主题了解不多，所以我能想到的唯一选择是Mersenne Twister；它是否满足所有这些要求？还有什么更好的吗？

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：让我更清楚地说明第 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 RNG，但我仍然想要更多的输入。因此，我正在设置赏金。

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 生成器的外观。有没有人对他们有任何意见？

采纳答案by redcalx

George Marsagliahas developed some of the best and fastest RNGs currently available Multiply-with-carrybeing a notable one for a uniform distribution.

George Marsaglia开发了一些目前可用的最好和最快的 RNG ，这是一个值得注意的均匀分布的乘法。

=== Update 2018-09-12 ===

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

For my own work I'm now using Xoshiro256**, which is a sort of evolution/update on Marsaglia's XorShift.

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

回答by David Johnstone

Sometimesgame developers don't want true randomness and a shuffle bagis 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.

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

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()通常作为线性同余生成器实现。如果您对它是否足以满足您的目的做出明智的选择，这可能是最好的。

回答by Chris Lomont

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；一台 PC 需要超过 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

这是一篇概述 PRNG 的论文，我在其中找到了 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 年后创建，并产生比梅森更好的数字。你怎么会弄错？:)

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];
   }

回答by Crashworks

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

Mersenne Twister 是业界的典型代表，特别是因为它非常适合 SIMD 并且可以超快地制作。Knuth也很受欢迎（谢谢，大卫）。

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.

在大多数游戏应用程序中，速度确实是关键因素，因为玩家会抱怨低帧率，而不是抱怨这样一个事实，即在 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.

当然，赌钱是个例外，但您的相关许可机构会专门列出您可以使用的算法。

回答by Vexatus

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 :)

买一个便宜的网络摄像头，一个电离烟雾探测器。拆开它们，烟雾探测器几乎不含放射性物质 - 伽马波的来源 - 这会导致在您的网络摄像头上发射光子。那是你真正随机性的来源:)

回答by GManNickG

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 algorithmwas designed as an improvement over the Mersenne Twister. Game Gems7 has more info. on it, if you can borrow that or have it.

该井随机算法被设计为在梅森倍捻机的改善。游戏宝石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:)

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

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

我唯一可以指出的另一件事是boost有一个random library，您应该会发现它很有用。

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 的更多理由:)

回答by Nosredna

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 上得到一些。将它们用于回合制游戏，或作为实时游戏的种子。

回答by Ape-inago

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

我是Isaac的粉丝，与 mersense twiner 不同，它在密码学上是安全的（你*不能通过观察卷来破解这个时期）

IBAA(rc4?) is also one that is used by blizzardto 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?) 也是暴雪用来防止人们预测用于战利品卷的随机数的一种。我想当你在战网服务器上玩游戏时，暗黑破坏神 II 也做了类似的事情。

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

*不能在任何合理的时间范围内（几个世纪？）

回答by Armin Ronacher

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
• easy to understand

• 非常非常快
• 比大多数标准rand()实现更高的熵
• 容易理解

回答by geowar

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。