Show HN: Solve and generate mazes with JavaScript on HTML Canvas 96 points by davidim 27 days ago | hide | past | web | favorite | 30 comments

 https://bost.ocks.org/mike/algorithms/#maze-generation has some visualizations for various different maze generation algorithms.
 Great link. Here's another good one.
 And here's another one. It introduces maze building ideas in a simple way.
 I used that book to design mazes that were rendered as thick-walled SVGs so I could make them out of plywood on my laser cutter!
 It would be cool to see the cells checked as well. To someone unfamiliar with BFS, the demo makes it seem like the process of finding the solution doesn't involve exploring any other tiles than the solution itself.
 A pretty neat example of this is mbostock's A* search: https://beta.observablehq.com/@mbostock/best-first-search
 I explored the test site and tried different maze sizes with values in the 50s, 70s, 110s, 150 (including odd numbers). Curiously, I found the maze could be visually divided into four Cartesian-like quadrants. Consistently the middle divider had only one gap, and other major quadrants also consistently have only one gap. So, when I wondered if BFS solution might be different if I ran it multiple times, I couldn't tell. Because of the curious constraint I just mentioned, all paths had to traverse these major divisions through the same gap. In other words, if there was variance, it would be constrained to a very small movement in a corner.I imagine if I dived into the code I would realize if my hypothesis that multiple runs of the BFS would always result in the same solution, was plausible or not. And it might also be the case if I understood BFS more, I would also know if it would always result in the same solution.But how much fun if I could see it visually with a few clicks in the GUI.Thanks and Good luck.
 Thanks so much for the compliment. This is probably a bi-product of the maze generation algorithm I used. Essentially, at every step, the algorithm bisects the maze horizontally or vertically - then, it chooses a random cell along this bisection to leave open (that way the 2 resulting regions are still connected). Then, the same algorithm is performed on the 2 new regions. Recursion continues until it no longer makes sense to continue bisecting.Wikipedia has an article on maze generation that explains the algorithm - https://en.m.wikipedia.org/wiki/Maze_generation_algorithm
 You’ll have fun if you implement all the generation algorithms in that article. If you want to get rid of the visible bisect structure, you can use your solver with only slight modifications to generate your maze.
 I can confirm that that's exactly what happened, different generation algorithms have a different "texture" to them in precisely this way and those textures do sometimes have a byproduct of making the maze easier or harder to solve.The algorithm with the least helpful "texture" is probably Wilson's algorithm, which basically says: choose a point at random out in the unsolved territory and begin a random walk: when you reach the solved territory (the maze as it is already known), add those points back to the maze; when you self-intersect you should delete the random walk back to where you self-intersected. (For the very first walk, furthermore, there is only one "solved" point in the maze so you may wish to speed up maze generation by doing a different random walk that just "busts down walls" into the as-yet-unknown area; this is called Aldous-Broder and it has the opposite problem where it tries to randomly walk into unsolved space so it takes forever when the unsolved space becomes rare.) So one would start from,`````` function* randomWalkPoints({ x, y }, height, width) { const incr = [{dx: -1, dy: 0}, {dx: 1, dy: 0}, {dx: 0, dy: -1}, {dx: 0, dy: 1}]; while (true) { const { dx, dy } = incr[Math.floor(4 * Math.random())]; const new_x = x + dx, new_y = y + dy; if (new_x >= 0 && new_x < width && new_y >= 0 && new_y < width) { x = new_x; y = new_y; yield { x, y }; } } } `````` Now, the algorithm might get a bit weird because it looks like you are using block mazes rather than conventional thin-walled mazes; every n-by-m thin-walled maze has an embedding as a block maze of size (2n+1)-by-(2m+1) simply by making (0, y) and (x, 0) all walls, every (odd, odd) point is empty space representing one of the squares of the original maze, every (even, even) point is a block, and (odd, even) and (even, odd) points are blocks if and only if there is a vertical/horizontal wall between the corresponding squares in the original maze. So all of the resources you will find are talking about mazes that look like,`````` ╔═══════════╦═══════╗ ║ ║ ║ ║ ╔═══ ═══╣ ║ ║ ║ ║ ║ ═══╗ ═══╣ ║ ║ ║ ║ ║ ╚═══════╣ ║ ║ ║ ║ ║ ║ ╠═══════ ╚═══╣ ║ ║ ║ ║ ╚═══════════════╩═══╝ `````` and then in your context this becomes:`````` X X X X X X X X X X X X . . . . . X . . . X X . X X X . X . X X X X . X . . . . . . . X X . X . X X X . X X X X . X . . . X . . . X X . X X X X X . X . X X . . . . . X . X . X X X X X X . X X X . X X . . . . . . . X . X X X X X X X X X X X X `````` So I'm not 100% sure whether you would want to just restrict yourself to block mazes of this type, or whether you would want to just try something like "I modify Wilson's to keep track of walls I have already placed, too, and then when I intersect with myself on a path that already hit a block wall, I discard back to the open-space which placed that block" to get a slightly more general vision of the problem... I am not sure how you'd want to handle that.
 +1 for the ascii art alone. HN never ceases to amaze me
 It's a very noticeable pattern and detrimental to the beauty of the maze but the solver works well.
 Yeah, currently it seems large mazes are generated in 7x7 or similar blocks which are then combined to fill the area. A good example of this visually is a 29x29 or a 49x49 maze.
 Nice. I created a maze solver in js and canvas as well, solving using the A* and Tremaux algorithms.You can even create your own mazes by passing json in the url.Simple Maze Solver in HTML5 and Js http://www.primaryobjects.com/maze/
 This will be an interesting book to read... also showcasing multiple maze generation algorithms: https://pragprog.com/book/jbmaze/mazes-for-programmers
 I love this book. It's on my retirement pile! (Hopefully mazes will still be relevant by then.)
 Bug Report: http://prntscr.com/mcyc1bWhen the website loads, if I put in a large number such as 500 and hit the generate button, it does not clear the previous puzzle and overlays on top. Second click still shows it bit now its a but transparent. Third click removes it altogether. I tried to skim through the code but not sure what the cause is given that you create a new Maze every single time. It seems to be some sort of canvas rendering bug as if I clear the canvas [1] it seems to work.
 Thanks a lot for the bug report! You're right - I was forgetting to clear the canvas on render. So I added ctx.clearRect(0, 0, WIDTH, HEIGHT); to the start of the render method.
 I'm surprised it doesn't allow you to "draw" on it to solve the maze. That seems like an essential (and easy to add) feature.
 What sort of drawing are you thinking? Dragging the mouse around on the screen or navigating with the arrows?
 Well I would pick drawing with a mouse, but arrow keys would work in a pinch.
 Very cool! I started making a very unpolished game based on a similar sort of map design a few months ago for ludum dare -- caution that there are sounds on this link and no volume control: https://wcarss.ca/maze_of_sacrifice/
 It's cool, but I expected some explanation about the steps, challenges. Luckily the HN crowd filled that in :)
 The solutions for mazes of size 50-200 look quite like a river on a map; which is pleasant to me.
 Nice work!Seems to freeze if you put a number too high though. Perhaps you should add a limit?
 Thanks for checking it out! I am wondering how big is the number you are putting in? If the number is really high, it's probably causing a stack overflow. I would limit the size, but each browser has its own recursion limits so that would be quite a pain. In retrospect, I probably should not have used a recursive algorithm for this task :).
 I put in a value of 500, and while it didn't freeze completely, it really struggled to respond.
 Recursive division may be elegant, but it seems that may also have its disadvantages.
 One trick you could use is to add a setTimeout or asnyc/await somewhere during the recursion. By forcing a step to be asynchronous, the stack count will be reset.