Mind elaborating why? I'm not versed in maze generation, but I am a software dev, and reinventing an existing algorithm does happen. It might be very unlikely in this case, but I'd just like to know why.
I wouldn't say I'm an expert in maze generation either, but I would agree that it would be nearly impossible for the following reasons:
1.) The specific maze style used, with the semi-random angled lines within a circle shape, isn't the most mathematically simple form of a maze. If it was a grid pattern in a rectangle, there might be a tiny chance of two people making the same maze, but to create a maze of that style would require more creative programming, with more tune-able parameters, and more decisions left to the implementer.
2.) In order to choose from the vast number of possible mazes that fit a certain pattern, the algorithm is almost certainly going use some random number generation. Even if two people were using the exact same maze algorithm, they would have to also have to use the same randomization process, and start with the same seed in order to arrive at the same maze. I guess it wouldn't be impossible for both people to explicitly choose the same initial seed, (or arrive at it randomly) but that would be very unlikely.
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.
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.)
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?
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() );
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?
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.
1.) The specific maze style used, with the semi-random angled lines within a circle shape, isn't the most mathematically simple form of a maze. If it was a grid pattern in a rectangle, there might be a tiny chance of two people making the same maze, but to create a maze of that style would require more creative programming, with more tune-able parameters, and more decisions left to the implementer.
2.) In order to choose from the vast number of possible mazes that fit a certain pattern, the algorithm is almost certainly going use some random number generation. Even if two people were using the exact same maze algorithm, they would have to also have to use the same randomization process, and start with the same seed in order to arrive at the same maze. I guess it wouldn't be impossible for both people to explicitly choose the same initial seed, (or arrive at it randomly) but that would be very unlikely.