Use a pseudorandom number generator, such as Xorshift, and only seed it from /dev/urandom. Here is some example C99 code:
Code:
#include <unistd.h>
#include <sys/types.h>
#include <fcntl.h>
#include <errno.h>
#include <stdint.h>
/* Xorshift state - default
*/
static uint32_t prng_state[4] = { 123456789, 362436069, 521288629, 88675123 };
/* Generate a new 32-bit unsigned pseudorandom integer using Xorshift algorithm
*/
static inline uint32_t prng_u32(void)
{
uint32_t t = prng_state[0] ^ (prng_state[0] << 11);
prng_state[0] = prng_state[1];
prng_state[1] = prng_state[2];
prng_state[2] = prng_state[3];
prng_state[3] ^= (prng_state[3] >> 19) ^ (t ^ (t >> 8));
return prng_state[3];
}
/* Read new pseudorandom number generator state from device.
* Returns 0 if successful, errno otherwise (and state unchanged).
* (Reads 16 bytes from /dev/urandom to prng_state.)
*/
int prng_randomize(const char *const device)
{
uint32_t state[4] = { 0, 0, 0, 0 };
char *const q = (char *)&state[4];
char *p;
ssize_t n;
int descriptor, result;
if (!device || !device)
return EINVAL;
do {
descriptor = open(device, O_RDONLY | O_NOCTTY);
} while (descriptor == -1 && errno == EINTR);
if (descriptor == -1)
return errno;
do {
p = (char *)&state[0];
while (p < q) {
n = read(descriptor, p, (size_t)(q - p));
if (n > (ssize_t)0) {
p += n;
} else
if (n != (ssize_t)-1) {
do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
return errno = EIO;
} else
if (errno != EINTR) {
const int saved_errno = errno;
do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
return errno = saved_errno;
}
}
} while (!state[0] && !state[1] && !state[2] && !state[3]);
do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
if (result == -1)
return errno;
prng_state[0] = state[0];
prng_state[1] = state[1];
prng_state[2] = state[2];
prng_state[3] = state[3];
return 0;
}
/* Helper function: Count the number of bits value needs
*/
static inline unsigned int bits_used(uint32_t value)
{
int b = 1;
#ifdef __GNUC__
if (sizeof(unsigned long) == 4)
return 32 - __builtin_clzl((unsigned long)value);
if (sizeof(unsigned int) == 4)
return 32 - __builtin_clz((unsigned int)value);
#endif
if (value >= (uint64_t)65536) { b += 16; value >>= 16; }
if (value >= (uint64_t)256) { b += 8; value >>= 8; }
if (value >= (uint64_t)16) { b += 4; value >>= 4; }
if (value >= (uint64_t)4) { b += 2; value >>= 2; }
if (value >= (uint64_t)2) { b += 1; value >>= 1; }
return b;
}
/* Generate a pseudorandom number [min, max), i.e. [min, max-1].
* Remember to initialize the seed using prng_initialize(),
* or you will always receive the same sequence.
*/
int prng_irange(const int min, const int max)
{
if (max > min) {
const uint32_t range = (uint32_t)(max - min);
const uint32_t mask = (0xFFFFFFFFUL) >> (32 - bits_used(range));
uint32_t value;
do {
value = prng_u32() & mask;
} while (value > range);
return min + (int)value;
} else
return min;
}
I initially published the above source code here in mid-September. It seems to be quite well behaved ("random"), and it is quite efficient, too.
The prng_initialize() function will read the new 16-byte state from /dev/urandom, giving you a different sequence. You only need to call that once at the beginning of your program.
The prng_irange(min,max) function returns a pseudorandom integer, min <= result < max. It uses the exclusion method, which avoids the (very small) bias for small values when using the modulus operator. (If the range is not divisible by the modulus, then the "topmost" part of the range will fall on the smaller end of the range, yielding smaller values a bit more often than large values.)
In a game the difference is trivial, so you might not need that; instead, you might use the following variant. It uses an inclusive range, does not care if min > max, and uses the modulus operator:
Code:
/* Return a pseudorandom integer [min, max].
* This function may return both min and max; the range is inclusive.
*/
int prng_int(const int min, const int max)
{
if (max > min)
return min + (prng_u32() % (uint32_t)(max - min + 1));
else if (min > max)
return max + (prng_u32() % (uint32_t)(min - max + 1));
else
return min;
}
If you need to generate a large number of pseudorandom integers within a constant range, modifying the prng_irange(min,max) function will most likely be the fastest option. This is because you only need to calculate the range and mask once for the entire set, and generating (on average, never more than two numbers per one used) the discarded numbers may be faster than taking a modulus. (Modulus happens to be a pretty slow operation.)
Hope this helps.