[tfinniga]

With maze generation, you need some way of deciding which subset of the possible walls you're going to keep. Usually you rely on some random or pseudorandom numbers to feed into the algorithm or use internally.

Having the maze verts in the same positions is possible and not too unlikely. Having the same walls is astronomically unlikely. Even if you had exactly the same algorithm (possible, but unlikely) and the implementations used the random values in exactly the same order, you'd also need exactly the same random seed. There are a lot of possibilities for that seed.

[userbinator]

you'd also need exactly the same random seed. There are a lot of possibilities for that seed.

I've seen a lot of code that either forgot to srand(), or misused it in some way so the output was pretty determinate. There are also a limited number of PRNGs in use, and they're most definitely not understood well by the majority of programmers; the crypto community knows this quite well. A collision may not be so unlikely after all.

(Try Googling "41, 18467, 6334" for example. "41184676334" also brings up some interesting results.)

[chton]

Thanks for the explanation. what would the impact be if they had a different seed, would the maze be really drastically different? Or could it look more like the 2 mazes in the original post, with only a few walls different and mostly identical?

[tfinniga]

It depends on the pseudorandom number generator that you're using, but you'd be hard pressed to find a standard library prng where similar seeds produced similar random numbers. That would be pretty bad design.

For example, here is some code I wrote to test my own prng:

srand(1000000); for( int i = 0; i < 10; i++ ) printf( "%d\n", rand() );

printf("====\n");

srand(1000001); for( int i = 0; i < 10; i++ ) printf( "%d\n", rand() );

And here is the result:

21585 18586 29373 4301 3304 21158 23657 21142 2144 26110 ==== 21589 29335 14469 28364 13618 25085 26770 18215 18656 19962

As you can see, they diverge really quickly.

[chton]

I'm aware of how prngs work, and of how often they are misused. What I was mostly wondering was how big an effect that would give in the final product. Do typical maze generation algorithms use it extensively, or sparingly so the differences are minor? How different would the maze look if the seed was different, and is it likely that you could get very similar mazes from completely different seeds?

[tfinniga]

I think the short answer is that the maze will look very different. It's very possible that the verts of the maze would be in exactly the same position, since that's a regular pattern. But the maze walls will be extremely random.

Maybe the best way to get a feel for it is to take a look at this page of maze generators: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...

[chton]

That's a great page. I learned a lot, thanks!