Remarkably simple with great results. I recommend checking out the author’s book Mazes for Programmers: one of the best programming books I’ve ever read. Incredibly clearly explained, and very interesting, which is an excellent combination.
I was about to comment the same. Very good book, reading it and implementing its mazes with my own features on top has been my long term casual project for a while.
I posted some examples on Mastodon. I added several features, one being running the algorithms “by step” so that not only can it be easier to debug but it can be animated too.
Very nice! Running by step is a fantastic idea, I might steal that for my own implementations :)
I also liked the idea of finding the two furthest-apart points within the maze to use as start and end points. My app just picks two opposite corners. Completely arbitrary. I was never satisfied with it. Yours is much better.
It would be kind of cool to generate an 'infinite' maze this way by starting the process and only recursing to max depth only for the nodes closest to the exits.
My favorite maze generation algorithm was the really simple one where you have a cursor, you push your coordinates to the stack, then remove a wall to a random unvisited square that's adjacent to the cursor. When you run out of possible choices for an unvisited square, you pop coordinates from the stack. Mazes generated by this algorithm tend be easy to solve, with long paths and short dead ends.
One problem with all these maze algorithms is how they are completely random.
When a human creates a maze, he might start with the solution, then add a few false paths that end near the finish but just fail at the last step. Maybe a few loops are added, or a picture or special features are integrated. Only at the very end, the leftovers are filled in with random data. The process is a design, not a random generation.
Are there any algorithms available that do similar things?
My favorite maze algorithm is this one: https://cs.wellesley.edu/~pmwh/papers-fcpcg/presentation/sli...
Live demo at: https://cs.wellesley.edu/~pmwh/hydrodendron/
It allows generating an infinite maze looking at any arbitrary area of the maze, without any loops, using fractal coordinates
Oh I loath how that first link hijacks the back button.
Good news, found it as a more normal paper too:
https://cs.wellesley.edu/~pmwh/papers-fcpcg/FDG2021-Mawhorte...
Yeah its a weird format for a paper ngl
The webpage under the first link is an annoying maze too, as if they couldn't make a typical one-dimensional page :D
Its an exciting experiment in non linear communication ;)
Remarkably simple with great results. I recommend checking out the author’s book Mazes for Programmers: one of the best programming books I’ve ever read. Incredibly clearly explained, and very interesting, which is an excellent combination.
I was about to comment the same. Very good book, reading it and implementing its mazes with my own features on top has been my long term casual project for a while.
I posted some examples on Mastodon. I added several features, one being running the algorithms “by step” so that not only can it be easier to debug but it can be animated too.
https://mastodon.social/@lloydjatkinson/media
Very nice! Running by step is a fantastic idea, I might steal that for my own implementations :)
I also liked the idea of finding the two furthest-apart points within the maze to use as start and end points. My app just picks two opposite corners. Completely arbitrary. I was never satisfied with it. Yours is much better.
Reminds me a little of Hilbert curves.
It would be kind of cool to generate an 'infinite' maze this way by starting the process and only recursing to max depth only for the nodes closest to the exits.
My favorite maze generation algorithm was the really simple one where you have a cursor, you push your coordinates to the stack, then remove a wall to a random unvisited square that's adjacent to the cursor. When you run out of possible choices for an unvisited square, you pop coordinates from the stack. Mazes generated by this algorithm tend be easy to solve, with long paths and short dead ends.
One problem with all these maze algorithms is how they are completely random.
When a human creates a maze, he might start with the solution, then add a few false paths that end near the finish but just fail at the last step. Maybe a few loops are added, or a picture or special features are integrated. Only at the very end, the leftovers are filled in with random data. The process is a design, not a random generation.
Are there any algorithms available that do similar things?