CODEWITHSUNDEEP
c++performancerandom
Michael Myers
Michael Myers

Reputation: 191955

What is a good random number generator for a game?

What is a good random number generator to use for a game in 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.

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 seems to be the consensus choice. But what about point #4? Is it really that much better than rand()?

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.

Upvotes: 63

Views: 43090

Answers (25)

Chris Lomont
Chris Lomont

Reputation: 381

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.

Here is a paper overviewing PRNGs where I found the WELL512 implementation. https://www.lomont.org/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? :)

UPDATE (11-18-14): Fixed error (changed 0xDA442D20UL to 0xDA442D24UL, as described in the paper linked 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];
   }

Upvotes: 38

redcalx
redcalx

Reputation: 8647

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

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

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

=== Update 2021-02-23 ===

In .NET 6 (currently in preview) the implementation of System.Random has been changed to use xoshiro256**, but only for the parameterless constructor. The constructor that takes a seed uses the old PRNG in order to maintain backwards compatibility. For more info see Improve Random (performance, APIs, ...)

Upvotes: 28

Charlie
Charlie

Reputation: 653

Even tho this post is years old, it showed up when I was looking for a similar answer, and the answer I wound up using, isnt even in it. So I'm adding the one I found;

#include <random> msdn entry

This approach will build a self contained random generator, and I found it to be a lot more random than rand()%x; over a few hundred thousand iterations. rand()% would never throw 16+ heads/tails in a row, when it should every other 65k attempts. This one not only does that, but it does it in a quarter of the time.

This is how I implement #include <random> myself:

//create rng_gen, using mt technique, with range 0,1 (coin) and 1,6(dice);
std::random_device rd; //seed
std::mt19937 gen(rd()); //seed for rd(Mersenne twister)
std::uniform_int_distribution<> rng_coin(0, 1); //rng1 range
std::uniform_int_distribution<> rng_dice(1, 6); ///rng2 range

rng_coin(gen); //will apply rng1 range on (gen) object. Is very fast
rng_dice(gen); //will apply rng2 range, returns int.

//will output 1000 cointosses to console
for (int i=0;i<1000;++i)std::cout<<rng_coin(gen)<<"\n";
//will generate 1000 dice throws
for (int i=0;i<1000;++i)rng_dice(gen);

Upvotes: 4

David Johnstone
David Johnstone

Reputation: 24450

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.

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.

Upvotes: 45

Serge Rogatch
Serge Rogatch

Reputation: 15040

Starting with Ivy Bridge architecture Intel added RdRand CPU instruction and AMD added it later in June 2015. So if you are targeting a processor that is new enough and don't mind using (inline) assembly, the fastest way to generate random numbers should be in calling RdRand CPU instruction to get a 16- or 32- or 64-bit random number as described here. Scroll to approximately the middle of the page for code examples. At that link there is also a code example for checking the current CPU for support of RdRand instruction, and see also the Wikipedia for an explanation of how to do this with the CPUID instruction.

Related question: Making use of sandy bridge's hardware true random number generator? (though according to Wikipedia, RdRand instruction first appeared in Ivy Bridge, but not Sandy Bridge architecture as that question says)

Example C++ code based on _rdrand64_step() :

#include <immintrin.h>

uint64_t randVal;
if(!_rdrand64_step(&randVal)) {
  // Report an error here: random number generation has failed!
}
// If no error occured, randVal contains a random 64-bit number

Upvotes: 8

Sunsetquest
Sunsetquest

Reputation: 359

Two good alternatives from intel's site:

1) fastrand - it is 2.01 X faster than the std rand(). The routine returns one integer, similar output value range as C lib.

inline int fastrand() { 
  g_seed = (214013*g_seed+2531011); 
  return (g_seed>>16)&0x7FFF; 
}

2) an SSE version (see link below) is about 5.5 X as fast as std rand() however it generates 4 random values at a time, requires a processer with sse (almost all do), and is more complicated.

http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/

Upvotes: 35

Kirill V. Lyadvinsky
Kirill V. Lyadvinsky

Reputation: 99605

Boost library has a set of random generators. Performance chart could be found here.

EDIT: This answer was here before the edit of the original question. But I hope it could be still helpful, so I leave it here.

Upvotes: 2

user2700021
user2700021

Reputation:

I think WELL is pretty good, and WELL512a is pretty short. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a is complex at the time too. However, WELL generates a number between 0 and 1.

Upvotes: 0

sschaem
sschaem

Reputation: 11

GameRand implement the algorithm posted here 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.

Upvotes: 1

jay_t55
jay_t55

Reputation: 11652

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

Upvotes: 0

AndyV
AndyV

Reputation: 819

The other thread mentioned Marsaglia's xorshf generator, but no one posted the code.

static unsigned long x=123456789, y=362436069, z=521288629;

unsigned long xorshf96(void) {          //period 2^96-1
unsigned long t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;

   t = x;
   x = y;
   y = z;
   z = t ^ x ^ y;

  return z;
}

I've used this one all over the place. The only place it failed was when I was trying to produce random binary matrices. Past about 95x95 matrices, it starts generating too few or too many singular matrices (I forget which). It's been shown that this generator is equivalent to a linear shift feedback register. But unless you are doing cryptography or serious monte carlo work, this generator rocks.

Upvotes: 81

John D. Cook
John D. Cook

Reputation: 30089

See these generators from random number generator expert George Marsaglia. They're implemented as C macros, and they're lightning fast, just a few operations per number generated.

Upvotes: 12

abelenky
abelenky

Reputation: 64682

rand() is really darn fast, and I don't believe you'll find much faster.

If it is in fact slowing you down (which I kinda doubt), then you need an architecture change.

I recommend pre-populating a long list with random numbers, then when you need one, simply take one from the list, rather than generating one. You may be able to re-fill the list with a background thread.

Upvotes: -3

lhf
lhf

Reputation: 72312

The Mersenne Twister has some fast implementations.

Upvotes: 5

Mikeb
Mikeb

Reputation: 6361

can you pregenerate a bunch of random bits ahead of time and peel them off 2 at a time (since you only need a random number between 1 and 3)?

Upvotes: 1

geowar
geowar

Reputation: 4447

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.

Upvotes: 2

nonpolynomial237
nonpolynomial237

Reputation: 2169

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.

Upvotes: 0

Michael F
Michael F

Reputation: 40829

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.

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.

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.

Upvotes: 1

Marsh Ray
Marsh Ray

Reputation: 2875

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.

Upvotes: 0

Armin Ronacher
Armin Ronacher

Reputation: 32533

Based on the random number generator by 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

Upvotes: 3

GManNickG
GManNickG

Reputation: 503953

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.

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.

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

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

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

Upvotes: 7

Vexatus
Vexatus

Reputation: 890

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

Upvotes: 11

Ape-inago
Ape-inago

Reputation: 1866

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

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.

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

Upvotes: 4

Nosredna
Nosredna

Reputation: 86216

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.

Upvotes: 4

Crashworks
Crashworks

Reputation: 41404

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

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.

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

Upvotes: 10

Related Questions