Penrose Mazes (2020) | Hacker News Reader

Penrose Mazes (2020)

justinpombrio.net

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.

But how does that improve the maze?

This is an efficient way to shuffle a maze, but you need a maze to start with.

>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.

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.

I confirm it works. Blue becomes pink at some point, but you should prioritize blue.

I still can't see it, and I'm not colorblind.

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.

That blue and that green are... not very different.

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.

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.

Make it 3D and you'll be really really lost.

Neat!

Reply on news.ycombinator.com