Subtle Lack of Randomness in Maze Generation Algorithm in C

Question

This concerns what I can only surmise is a flaw in somebody's code used to generate random mazes. The code is somewhat long, but most of it is commented-out options and/or not concerned specifically with the randomization.

I got the 2001x2001 maze from the link dllu put up and saved as a png here. From that, I have created this. To get the blue pattern, I started filling in dead ends starting in the bottom left-hand corner of the maze. According to the backtracker algorithm he used, that's the point at which the maze begins to be generated: so if you following the trail of dead ends created by that, you can systematically fill in all the dead ends on that side of the maze. In other words, the central blue mass represents the total accessible area starting from the bottom left, up to the sole frontier pixel at 2678 x 1086.

But there's something immediately anomalous, in that the blue "fractal" seems to repeat itself. Indeed, by overlaying one part of the fractal, rotated and mirrored, you can see there is an exact correspondence of shape. Another anomaly from this overlay maps part of one of the continents onto another, but strangely only a sliver of the landmass this time. Evidently these aren't the only auto-correspondences.

But besides the shape of the dead-end components, there is repetition of the actual pattern of the walls when you zoom in. Strangest of all, the repetition isn't exact, but only maybe 50-60% of the walls correspond. Zoomed and constrasted sample of a region:

Long question short, what in the code is causing this obscure lack of randomness?

Answer 1

Anonymous has properly indicated that rand is poorly implemented and that it has poor entropy in its lower bits.

To alleviate this issue, you could use a stronger pseudo-random number generator (like one suitable for cryptographic methods); however, the higher quality of the randomness tends to lead to longer time in the random number generating function.

I would initially attempt to pull out some of the upper level bits from your random generator. It might be sufficient to improve the result with a less-than perfectly random generator. As they are pulled from a different region of the result, and shifted to the 0-3 values you need, their distribution should be different (and hopefully a bit more random)

Answer 2

The standard library function rand is often horribly implemented and your code is doing rand()%4 which exacerbates the problem because poor implementations tend to have even less randomness in the lower bits. Try replacing rand with a different random number generator.