What is a good random number generator for a game?

Question

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

My thoughts:

• It takes a lot of random numbers, so the speed is good.
• Players will always complain about random numbers, but I would like to point them to a link explaining that I really did my job.
• Since this is a commercial project for which I have little time, it would be nice if the algorithm either a) was relatively easy to implement or b) had a good implementation other than the GPL.
• I already use rand() in quite a few places, so any other generator should be good to justify all the changes it needs.

I am not very versed in this matter, so the only alternative I could come up with is Mersenne Twister ; Does it satisfy all these requirements? Which is even better?

Edit: Mersenne Twister seems to be a consensus choice. But what about point number 4? Is this really much better than rand() ?

Edit 2: Let me be a little clearer in paragraph 2: players are not able to cheat, knowing random numbers. Period. I want it to be random enough so that people (at least those who understand randomness) cannot complain about it, but I'm not worried about the forecasts. That is why I put speed as the main focus.

Edit 3: Now I'm leaning towards the Marsaglia runes, but I still like more info. Therefore, I create generosity.

Edit 4: Note only: I intend to accept the answer before midnight UTC today (so as not to bother with any of the players). Therefore, if you want to answer, do not wait until the last minute! Also, I like the Marsaglia XORshift generators. Does anyone have any information about them?

Answer 1

George Marsaglia has developed some of the best and fastest Multiply-with-carry fracturing currently available is noticeable for even distribution.

Answer 2

Sometimes game developers do not need true randomness and a bag in random order is more suitable.

If you need randomness, the Mersenne Spinner meets your needs. It is fast, statistically random, has a long period, and there are many realizations.

Edit: rand() usually implemented as a linear congruent generator . This is probably best if you make an informed choice about how much is enough for your purposes.

Answer 3

There is currently a much better choice than Mersenne Twister. Here's an RNG called WELL512, designed by Mersenne designers, designed 10 years later, and everyone around is the best choice for gaming. This code is in the public domain by Dr. Chris Lomont. He claims that this implementation is 40% faster than Mersenne, does not suffer from poor diffusion and traps when the state contains many 0 bits and is obviously much simpler. It has a period of 2 ^ 512; A PC takes 10 ^ 100 years to go through the state, so it is big enough.

Here is a document that discusses PRNG where I found an implementation of WELL512. http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

So, faster, easier, created by the same designers in 10 years and produces better numbers than Mersenne. How are you wrong? :)

UPDATE (11-18-14) : Bug fixed (changed 0xDA442D20UL to 0xDA442D24UL, as described in the document above).

 /* 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 4

Mersenne Twister is typical in the industry, especially since it lends itself well to SIMD and can be done very quickly. Knuth is also popular (thanks, David).

In most gaming applications, speed is indeed a critical factor, as players are going to complain about the low frame rate much more than they will complain that there is a slight bias towards generation 3 when it is preceded by 7, 2 and 9 in that order.

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

Answer 5

Buy cheap webcamera ionizing smoke detector. Disassemble both of them, the smoke detector contains little radioactive material - a source of gamma waves, which will lead to shelling of photons in your webcam. This is your source of true randomness :)

Answer 6

Mersenne Twister is very good, and he is also fast. I used it in the game, and it is not at all difficult to implement or use.

The random WELL algorithm was designed as an improvement over the Mersenne Twister. The game Gems contains additional information. on it if you can borrow it or have it.

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

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

In response to your editing, yes, Twister or WELL is much better than rand (). In addition, the old module trick harms the distribution of numbers. More reasons to use boost :)

Answer 7

In a real-time game, the player cannot determine the difference between a “good” generator and a “bad” one. In the turn-based game, you are right - some minority of zealots will complain. They will even tell you stories, in painful details, about how you ruined your life with a random number generator.

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

Answer 8

I am a fan of Isaac , unlike mersense twister, it is crystal protected (you * cannot hack the period for observing rolls)

IBAA (rc4?) Is also used by snowstorms so that people do not predict the random number used for production channels. I assume something like this is done w / diablo II when you play from the battle.net server.

* cannot be within a reasonable time frame (centuries?)

Answer 9

Based on the random number generator Jan C. Bullar:

 // 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

Answer 10

Additional criteria to consider are thread safety. (And you should use streams in today's multi-core environments.) Just calling rand from more than one thread can ruin its deterministic behavior (if your game depends on it). At least I recommend you switch to rand_r.

Answer 11

I would vote for the Mersenne Twister. Implementations are widely available, it has a very large period of 2 ^ 19937 -1, is quite fast, and passes most random tests, including the Dichard tests developed by Marsaglia. rand () and Co., being LCGs, produce lower quality variances and their consistent values ​​can be easily deduced.

However, it should be noted that it is necessary to correctly transfer the MT to a state that passes randomness tests. Typically, an LCG is used for this purpose, such as drand48 ().

I would say that MT satisfies all the requirements that you set (provably), and would be redundant for something like MWCG imo.

Answer 12

You know? Forgive me if you think this answer completely sucks ... But I was (because God only knows for what reason ...), using DateTime.Now.Milliseconds as a way to get a random number. I know that he is not completely random, but it seems he ...

I just had nothing to type on a typewriter enough to get a random number !: P

Answer 13

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

This is what I originally developed in the late 80s. It easily beats rand () in terms of numerical quality, and since the side benefit is the fastest random algorithm.

Answer 14

I want this to be random enough so that people (at least those who understand randomness) cannot complain about it, but I'm not worried about the predictions.

Ah ha!

There is your real requirement!

In this application, no one could defeat you for using the Mersenne Twister.

Answer 15

Depending on the target OS, you may use / dev / random. It really does not require any implementation, and on Linux (and possibly on some other operating systems) it is really random. Reading blocks until sufficient entropy is available, so you can read the file and save it in a buffer or something else. If you cannot use a blocking read call, you can use / dev / urandom. It generates random data in much the same way as / dev / random, but it reuses some random data for immediate output. This is not so safe, but it may work fine, depending on what you plan to do with it.

Answer 16

Apparently (I forgot where I read it, just like I forgot where I read that curry is good to prevent alzheimes), taking the absolute value of the checksum of the newly created GUID will be randomly random. This is a large amount, and you can use it modulo to reduce it.

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

Rob