News for hackers. Stuff that matters.
Re:Maze Generator and Solver by jschulenklopper on Tuesday May 26, 2015 @07:13AM (#9603959)
For a great collection of maze generation algorithms, see the blog of Jamis Buck. On http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit... he recaps the algorithms discussed in earlier posts, and he's publishing a book on the topic: Maze for Programmers. It's currently in beta on the Pragmatic Bookshelf: https://pragprog.com/book/jbmaze/mazes-for-programmers. Can't wait for the hardcover book, currently planned for September 2015.
Re:Maze Generator and Solver by ChicagoDave on Tuesday May 26, 2015 @04:17AM (#9603482)
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.
Re:Maze Generator and Solver by stwe on Tuesday May 26, 2015 @07:10AM (#9603944)
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.
Re:Maze Generator and Solver by lovegraphs on Tuesday May 26, 2015 @10:14AM (#9604962)
Thanks! Pull request merged.
Re:Maze Generator and Solver by LanceH on Tuesday May 26, 2015 @10:55AM (#9605239)
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.

Re:Maze Generator and Solver by s-macke on Tuesday May 26, 2015 @04:07AM (#9603461)
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.
Re:Maze Generator and Solver by shoo on Tuesday May 26, 2015 @05:13AM (#9603634)
this kind of idea has been explored under the name "collaborative diffusion".

e.g. http://sgd.cs.colorado.edu/wiki/Collaborative_Diffusion

Re:Maze Generator and Solver by s-macke on Tuesday May 26, 2015 @05:40AM (#9603693)
Thanks. Indeed, the idea looks similar.
Re:Maze Generator and Solver by leni536 on Tuesday May 26, 2015 @05:52AM (#9603721)
I assume Neumann 0 boundary condition at the walls. Would it always solve the maze though? It seems intuitively true but hard to prove.
Re:Maze Generator and Solver by s-macke on Tuesday May 26, 2015 @03:48PM (#9607184)
Hacked something together. Seems to work.

http://simulationcorner.net/maze/

Re:Maze Generator and Solver by s-macke on Tuesday May 26, 2015 @08:11AM (#9604211)
Yes, open boundary conditions at the walls.

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.

Re:Maze Generator and Solver by jsweojtj on Tuesday May 26, 2015 @04:46AM (#9603554)
I really like this idea!
Re:Maze Generator and Solver by 33a on Tuesday May 26, 2015 @10:39AM (#9605150)
If you want to see a faster maze solver, here is one that I submitted some time back:

https://github.com/mikolalysenko/l1-path-finder

In this demo page you can click on the title and the little dots will chase your mouse around:

http://mikolalysenko.github.io/l1-path-finder/www/

Re:Maze Generator and Solver by tempodox on Tuesday May 26, 2015 @08:46AM (#9604392)
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.
Re:Maze Generator and Solver by ctdonath on Tuesday May 26, 2015 @09:55AM (#9604834)
Tricycle with square wheels: https://www.youtube.com/watch?v=FayemJb2-w4
Re:Maze Generator and Solver by tempodox on Tuesday May 26, 2015 @11:06AM (#9605304)
Which goes to show that with a floor in the right shape, almost anything is possible :)
Re:Maze Generator and Solver by lovegraphs on Wednesday May 27, 2015 @03:25AM (#9609855)
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.
Re:Maze Generator and Solver by tempodox on Wednesday May 27, 2015 @07:28AM (#9610585)
Glad you took it this way, I'll have another look :)
Re:Maze Generator and Solver by RodgerTheGreat on Tuesday May 26, 2015 @09:15AM (#9604568)
I'm not sure if it's the only problem, but main.css contains a C-style "//" single-line comment. This is not valid CSS syntax.
Re:Maze Generator and Solver by lovegraphs on Tuesday May 26, 2015 @10:12AM (#9604952)
Thanks! Removed.
Re:Maze Generator and Solver by vermooten on Tuesday May 26, 2015 @04:19AM (#9603489)
Tough to solve on iOS http://i.imgur.com/zzb3nMJ.jpg
Re:Maze Generator and Solver by lovegraphs on Tuesday May 26, 2015 @04:32AM (#9603516)
Lamentable. Must be some missing cross-browser CSS.. I'll look into it tomorrow! In the meanwhile try it in Chrome if you have a chance :)
Re:Maze Generator and Solver by stevenh on Tuesday May 26, 2015 @04:33AM (#9603521)
FYI, it has the exact same issue on Safari on OS X.
Re:Maze Generator and Solver by lovegraphs on Wednesday May 27, 2015 @02:41AM (#9609686)
Safari is fixed! I need to get a Macbook so testing is faster than waiting for a screenshot online...
Re:Maze Generator and Solver by stevenh on Thursday May 28, 2015 @01:05AM (#9616156)
Now I get this error in the console as soon as the page loads in each browser I try:

    [Error] ReferenceError: Can't find variable: css
            generateMaze (mazeEventHandling.js, line 30)
Re:Maze Generator and Solver by lovegraphs on Thursday May 28, 2015 @06:34PM (#9621626)
Thank you, sorry about that. I changed some references around and caught that error only after having deployed.
Re:Maze Generator and Solver by lovegraphs on Tuesday May 26, 2015 @10:16AM (#9604976)
Thanks! It now works on iOS. Still working on Safari...
Re:Maze Generator and Solver by harel on Tuesday May 26, 2015 @04:12AM (#9603474)
I'm interested see how the maze is generated so that there Is a solution to it (ie, no exit point without an open way)
Re:Maze Generator and Solver by lovegraphs on Tuesday May 26, 2015 @04:27AM (#9603504)
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.
Re:Maze Generator and Solver by white-flame on Tuesday May 26, 2015 @04:18AM (#9603485)
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.
Re:Maze Generator and Solver by shultays on Tuesday May 26, 2015 @04:13AM (#9603476)
Not OP but you can always generate a fully random maze and then merge the unconnected blocks by simply removing a wall that can connect them
Re:Maze Generator and Solver by zentiggr on Tuesday May 26, 2015 @11:23AM (#9605404)
As a novice in this whole arena, are there any decent algorithms for determining longest path between two adjacent cells?
Re:Maze Generator and Solver by bananasbandanas on Tuesday May 26, 2015 @11:49AM (#9605573)
Sounds a lot like the longest path problem [1], which is NP-hard.

[1] http://en.wikipedia.org/wiki/Longest_path_problem

Re:Maze Generator and Solver by rosstex on Tuesday May 26, 2015 @03:28AM (#9603364)
Cool! How does it instantly recognize when a path would lead into a trap?
Re:Maze Generator and Solver by ahmetmsft on Tuesday May 26, 2015 @03:35AM (#9603377)
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.
Re:Maze Generator and Solver by lovegraphs on Tuesday May 26, 2015 @03:58AM (#9603433)
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.
Re:Maze Generator and Solver by je42 on Tuesday May 26, 2015 @08:15AM (#9604227)
Not using A* ?
Re:Maze Generator and Solver by vishaldpatel on Tuesday May 26, 2015 @09:01PM (#9608650)
Great work, Mike! :)
Re:Maze Generator and Solver by lovegraphs on Wednesday May 27, 2015 @02:40AM (#9609676)
Hey Vishal, thanks! Small world!
Re:Maze Generator and Solver by arrc on Tuesday May 26, 2015 @02:51AM (#9603283)
great work.
Re:Maze Generator and Solver by lovegraphs on Tuesday May 26, 2015 @03:54AM (#9603423)
Thanks!