rand() let me down.

[mkultra333]

Not asking a question, nothing important, just noting something.

I'm generating simple mazes inside a map editor on an 8x8 grid, using the recursive backtracking method. It makes nice, windy mazes with a couple of dead ends here and there. I was just using rand()%N for all the randomization, and the N values are always powers of 2 so letterboxing bias isn't a problem (N is often 4, for choosing one of 4 directions randomly). It seemed to be going well.

But then I decided to make it search for a subset of mazes, ones that have at least 2 crossroad junctions in them, a cell with exits in all four directions. These are only a small subset of all possible mazes but still common enough that you can randomize mazes and keep throwing them out until you find one that fits the bill.

Suddenly I hit a problem. The mazes generated were repeating. After six initial original mazes, the following would just be repeats of the first six, over and over. I was pretty sure there were more than just 6 mazes that had 2 crossroads out of the entire set of possible mazes backtracking could generate. So I guessed that rand() simply wasn't being random enough.

Seems strange. rand() does have an admittedly short period by randomizer standards, I've read it's a mere 2^32. It still seemed weird that it would produce such a limited repeating series with my usage. Another thing I read is that rand() is a type of Linear Congruential Generator (LCG), which are known to have two important flaws. The first is they don't have very good randomization of the least significant bits. But Microsoft rand() supposedly discards those bits which is why rand() has such a small range, from 0 to 32767. Second, and maybe more importantly, LCG numbers are known to fall into a distinct number of planes when plotted into 3D space. This is a much more serious issue that makes them useless for many scientific and statistical purposes.

Perhaps my 2D maze generation was somehow, from another perspective, a three dimensional mathematical problem, and so the number of possibilities rand() could dish up became severely restricted. Or maybe the 4 billion or so period of rand() just wasn't big enough to cope with the number of mazes to be randomized. Or a mixture of the two.

At any rate, I found a Mersenne Twister class and used that instead, and I'm now getting the desired results, new mazes and no repeats. Mersenne Twisters generally have a period of 2^19937 − 1, and have much better statistical behaviour than rand(). Took a while to find a suitable class. I know boost has one but I avoid using boost unless absolutely necessary. Found a lot that weren't classes, some that did my pet hate of not including license info, and finally settled on this one, http://fantacci.wikidot.com/mersenne-twister, which the author states isn't really speed optimized, but it doesn't really matter for my purposes.

And a final note about using randomizers in general. It's bad to go randomizer()%N to get a number from 0 to N-1, unless N divides evenly into MAX_RAND+1. You'll get bad biasing. Many of the workarounds don't really get rid of the biasing. The only way that really gets rid of the bias is to keep calling for random numbers until you get one in the range. See http://www.azillionmonkeys.com/qed/random.html

[Klaim]

By the way, if you use a recent version of a common compiler, you might have access to the random library in the standard C++ library... (that is almost the same than boost.random).
There is a mesene-twister implementation.

[lingfors]

I know boost has one but I avoid using boost unless absolutely necessary.

Why?

[duststorm]

I also don't understand why you prefer to avoid boost. To me boost is like a part of the stdlib.
My only grudge with it sometimes is that all the templating tends to result in cryptic hard-to-read linker errors.

[Kojack]

I tend to use George Marsaglia's Xorshift. It has a period of 2^128-1. Extremely small, simple and fast:

Code: Select all

uint32_t xor128(void) {
  static uint32_t x = 123456789;
  static uint32_t y = 362436069;
  static uint32_t z = 521288629;
  static uint32_t w = 88675123;
  uint32_t t;
 
  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

http://en.wikipedia.org/wiki/Xorshift
His Multiply With Carry generator can get a bigger period than mersenne twister and isn't much bigger code than the one above.

[CABAListic]

Heh, that's pretty nice! Any easy way to "seed" it so that you don't always get the same sequence? I could just xor the return value with my seed, but does that retain the cryptographic strength of the generator?

[mkultra333]

I know boost has one but I avoid using boost unless absolutely necessary.

Why?

Why not? If it isn't needed, it isn't needed.

Alternately, do you think it would be better to make boost a necessity just to get the randomizer, rather than perhaps using Kojack's 10 line Xorshift?

Kojack:

I tend to use George Marsaglia's Xorshift.

That's a nice looking randomizer. I had a similar type of xor-shift randomizer used in another project, but I couldn't find it or a link to it, so I went with the mersenne twister. Speed and space aren't super critical in my case. Next time I need a randomizer I'll keep that Xorshift in mind though.

Edit: I found the randomizer I used to use, and it turns out it's also by George Marsaglia. In my other project I had multiple channels of independed random numbers, so that different parts could have their own repeatable random sequences. Aparrently has a period of about 2^60.

Code: Select all

// these are based on George Marsaglia's multiply-with-carry generator.  I only seed the z value
void ModelFromImages::SeedRandom(int nChannel, unsigned int uSeed)
{
	uZ[nChannel]=362436069+uSeed ;
	uW[nChannel]=521288629 ;
}

unsigned int ModelFromImages::Random(int nChannel)
{
	unsigned int z =  uZ[nChannel] ;
	unsigned int w =  uW[nChannel] ;
	uZ[nChannel] = 36969*(z&65535)+(z>>16) ;
	uW[nChannel] = 18000*(w&65535)+(w>>16) ;

	return (uZ[nChannel]<<16) + (uW[nChannel]&65535) ;
}

But that Xorshift looks better, next time I'll try that.

[mcordingley]

Kojack,

Do you know what the range on that xorshift algorithm is? I think that it's [0, 2^32 - 1], but I could be wrong here.

Thanks!

[mkultra333]

Interestingly, the Mersenne Twister let me down too.

I seed it using an array of 624 unsigned ints, but the ints are set from rand() so they'll each only be from 0 to 32767. The Mersenne Twister has an issue that it takes a while to build up steam if there's lots of zeros in the initial seed.

I noticed the first cell of every maze, which should have 50/50 chance of an exit either to the south or east, was exiting south every single time. Not very random. Not random at all. The intial values coming out of the Mersenne Twister were heavily biased, I'm guessing by the large number of zero bytes in the seed array.

To get around this, after seeding I call for a couple of thousand random values and then discard them. After that it works ok.

[bstone]

Very interesting. Thanks for sharing!

[Zonder]

I'm just looking into this at the moment did you stick with Mersenne Twister? or swap to the xor shift?

[mkultra333]

Hey Zonder, sorry for slow reply, wasn't around for a bit. Just noticed this today.

The Mersenne Twister works great for the maze generator (and other functions in that project, it's a random map generator). It's certainly fast enough for that project, its cost is negligible compared to many of the other functions, and I haven't noticed any further problems after the bad warmup issue was fixed.

However, for another project, a game, I'll probably use one of those George Marsaglia fast randomizers. The idea of doing all those Mersenne Twister calculations just to add some randomness to a plasma shot makes me uncomfortable, I'd much rather the cpu was spent elsewhere.

The two have different needs. The map generator needs really, really random numbers, because I've already seen what happens when weak or flawed randomizers are used to search the potential map-space. But the game just needs "good enough" randomness. I'm actually using rand() at the moment and it looks fine for things like scattering shots or having AI pick random wandering locations, but I'd still like to change to the Marsaglia randomizers when I have the time.