Better random algorithm?

Question

I'm making a game in C++ and it involves filling tiles with random booleans (either yes or no) whether it is yes or no is decided by rand() % 1. It doesn't feel very random.

I'm using srand with ctime at startup, but it seems like the same patterns are coming up.

Are there any algorithms that will create very random numbers? Or any suggestions on how I could improve rand()?

Answer 1

I have used the Mersenne Twister random number generator successfully for many years. Its source code is available from the maths department of Hiroshima Uni here. (Direct link so you don't have to read Japanese!)

What is great about this algorithm is that:

1. Its 'randomness' is very good
2. Its state vector is a vector of unsigned ints and an index, so it is very easy to save its state, reload its state, and resume a pseudo-random process from where it left off.

I'd recommend giving it a look for your game.

Answer 2

Many pseudo-random number generators suffer from cyclical lower bits, especially linear congruential algorithms, which are typically the most common implementations. Some people suggest shifting out the least significant bits to solve this.

Answer 3

True randomness often doesn't seem very random. Do expect to see odd runs.

But at least one immediate thing you can do to help is to avoid using just the lowest-order bit. To quote Numerical Recipes in C:

If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

and never by anything resembling

j = 1 + (rand() % 10);

(which uses lower-order bits).

Also, you might consider using a different RNG with better properties instead. The Xorshift algorithm is a nice alternative. It's speedy and compact at just a few lines of C, and should be good enough statistically for nearly any game.

Answer 4

The low order bits are not very random.
By using %2 you are only checking the bottom bit of the random number.

Assuming you are not needing crypto strength randomness.
Then the following should be OK.

bool  tile = rand() > (RAND_MAX / 2);

Answer 5

C++11 has the following way of implementing the Mersenne tittie twister algorothm. From cppreference.com:

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 6);

    for (int n=0; n<10; ++n)
        std::cout << dis(gen) << ' ';
    std::cout << '\n';
}

This produces random numbers suitable for simulations without the disadvantages of many other random number generators. It is not suitable for cryptography; but cryptographic random number generators are more computationally intensive.

There is also the Well equidistributed long-period linear algorithm; with many example implementations.

Answer 6

Boost Random Number Library