Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Solve and generate mazes with JavaScript on HTML Canvas

github.com

Post reply on HN
Print view View original

11–20 of 33 posts

Re: Show HN: Solve and generate mazes with JavaScript on HTML Canvas

#14

Post by pmontra »

davidim wrote: post #6
xtiansimon wrote: post #4

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 tel…

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…

It's a very noticeable pattern and detrimental to the beauty of the maze but the solver works well.

Re: Show HN: Solve and generate mazes with JavaScript on HTML Canvas

#15

Post by dahart »

davidim wrote: post #6
xtiansimon wrote: post #4

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 tel…

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…

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.

Re: Show HN: Solve and generate mazes with JavaScript on HTML Canvas

#16

Post by tolien »

jere wrote: post #11

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

Re: Show HN: Solve and generate mazes with JavaScript on HTML Canvas

#17

Post by crdrost »

davidim wrote: post #6
xtiansimon wrote: post #4

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 tel…

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…

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 = 0 && new_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.

Re: Show HN: Solve and generate mazes with JavaScript on HTML Canvas

#18

Post by airstrike »

crdrost wrote: post #17
davidim wrote: post #6

Earlier quoted context omitted.

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…

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 y…

+1 for the ascii art alone. HN never ceases to amaze me
Post reply on HN