Anyone that hand draws mazes as a hobby knows these auto-generated mazes leave something to be desired. There's an art to designing a maze and I've yet to see an auto-generator mimic that art. First step, curved and multi-length branches. Next step, add complex and very long teaser dead-ends. Block-style mazes are way too simple.
GitHub Pages supports HTTPS, so please include your JS/CSS schema-relative (//) or directly with HTTPS. Otherwise people who force HTTPS on that domain get mixed content warnings and nothing loads.
I mostly wrote this: https://github.com/LanceH/Maze
while on conference calls before I started using that time to learn to draw.
I only ever ran it from within eclipse, I can't remember if it would run from the command line. It's a depth first search with solution also printed.
The only thing I added that I hadn't seen elsewhere is the "twisty" variable, which weights the random direction to either going straight or turning. I liked straight hallways on large mazes because it makes things blur together.
I would like to see a code, which solves a maze by calculating the Poisson equation for pressure. As boundary condition set high pressure at the start of the maze and low pressure at the end and follow the steepest decent.
I am not sure what happens if you have two possible paths to the exit but one of them is wider, but longer. It might not always find the shortest path.
I like this main idea, because it is independent on the dimension and structure of the maze.
Whatever it was built for, it doesn't run in Safari. And “but it runs in browser X” is almost as acceptable a retort as “it would run with square wheels”, in 2015, on the front page of HN.
By the way, thank you for your colorful simile--it really spurred me to fix this issue this morning, and I've definitely learned to take cross-browser compatibility more seriously. Cheers.
The particular generation algorithm that you see is called "Randomized Prim's algorithm" on Wikipedia. It starts at a random cell in a grid, marks it as discovered, and adds all of that cell's adjacent walls to a queue. It then selects a random wall from the queue and, if the cell on the other side of the wall has not yet been discovered, opens up that wall. It adds all of the adjacent cell's walls to the queue, marks the adjacent cell as discovered, and selects the next random wall in the queue until all the cells have been discovered. It's kind of a modified BFS. This algorithm guarantees that all cells are connected.
Most maze generators build a giant tree, starting from an arbitrary point and sending out branching corridors until the area is full. By its nature everything's connected.
It probably calculates the path in advance (note the "please wait" indicator appears just after you hit 'Solve') then it follows the path with an animation that gives you exactly the impression that it never falls into a trap as it goes.
That's right, it does a breadth-first-search from the end-point immediately upon clicking the end-point; it then traces the path from the start-point, following the parent-pointers set during the BFS, painting the DOM in the process.
