There is an efficient way to generate a random maze!
First you create an initial maze, and randomly remove a wall. This generates a loop in your maze. Then in the loop you randomly add one wall, this removes the loop in the maze while keeping all cells reachable. As you iterate this operation your maze will get more and more different.
Etherlord87 16 days ago [-]
This is an efficient way to shuffle a maze, but you need a maze to start with.
LorenPechtel 16 days ago [-]
But how does that improve the maze?
trimethylpurine 17 days ago [-]
>It is colored to make the solution apparent.
Not apparent enough. I spent five or ten minutes finding dead ends in the green area and gave up.
justinpombrio 17 days ago [-]
Walk with a green wall to your right, and a blue or white wall to your left. It's a long path, but shouldn't be too hard to see?
I remember being amused that Paint's flood fill could be used to solve mazes. It shows that flood fill is, worst case, as hard as solving a maze, so it needs to do something like DFS or BFS.
Etherlord87 16 days ago [-]
I confirm it works. Blue becomes pink at some point, but you should prioritize blue.
teraflop 17 days ago [-]
Dead ends "in the green area" don't matter.
The green walls are contiguous (connected), and the blue walls are also contiguous, but green and blue don't touch anywhere. So the border between the green and blue sections defines the path.
If you made the maze into a physical model, with walls but no floor or ceiling, the green and blue sections would "pull apart" from each other along that border.
gcanyon 17 days ago [-]
That blue and that green are... not very different.
michaelcampbell 17 days ago [-]
I still can't see it, and I'm not colorblind.
Y_Y 17 days ago [-]
I wonder if you could simplify the result by removing the floating stars? They might be interesting for blocking sightlines in a hedge maze but seem extraneous from above.
justinpombrio 17 days ago [-]
I'm away tonight, but the source code is there if anyone wants to make that change. I imagine it would make the mazes a lot smoother.
First you create an initial maze, and randomly remove a wall. This generates a loop in your maze. Then in the loop you randomly add one wall, this removes the loop in the maze while keeping all cells reachable. As you iterate this operation your maze will get more and more different.
Not apparent enough. I spent five or ten minutes finding dead ends in the green area and gave up.
I remember being amused that Paint's flood fill could be used to solve mazes. It shows that flood fill is, worst case, as hard as solving a maze, so it needs to do something like DFS or BFS.
The green walls are contiguous (connected), and the blue walls are also contiguous, but green and blue don't touch anywhere. So the border between the green and blue sections defines the path.
If you made the maze into a physical model, with walls but no floor or ceiling, the green and blue sections would "pull apart" from each other along that border.