« Added a CAPTCHA Test for Comment Spam | Home | Nopaste App Design, Revisited »
Javascript Maze
By Jacob Cohen | March 28, 2007
Last night I was thinking it would be cool to see if I could use HTML tables and Javascript to generate and solve a maze. I figured I could control the borders of the table cells to form the walls, then use a standard maze solving algorithm.
It turns out this is actually quite doable. This generates a maze using a depth-first algorithm, and solves it in similar fashion. The difference is that when it is generating the maze, it randomly selects a neighboring cell to explore. When it’s solving the maze, it always prefers to go east, then south, then west, finally north in order when selecting candidate paths.
It currently uses recursion, both to generate the maze and to solve it, but I’ll probably switch to managing the stack externally so I can generate larger mazes. I also want to figure out a way to draw a continuous path as the solution instead of shading the background of the cells. Then by varying the thickness of the path I should be able to optimize how easy it is to see where the path goes.
Topics: Tech |
March 30th, 2007 at 6:50 am
that’s pretty neat.
Rather than keeping the border set to white, why not set it to none? And when solving it, set the border to the color of the path.
That should make the solution a little more prominent.
I’d also set the border to ‘none’ or 0px rather than white when generating the maze. it’ll look less like ascii art, I think.
when generating the maze, how do you know it’ll have a solution?
…spike
March 30th, 2007 at 12:31 pm
Good ideas.
It always generates a solveable maze because it is a depth-first traversal of the maze cells. That means there’s always a path from the starting point to any other node in the graph. The graph’s vertices are predefined by the dimensions of the maze, and the edges are defined by the randomization of choosing an adjacent vertex to try next.
So I guess it’s not a matter of knowing if it will have a solution or not.. By virtue of the way the graph traversal visits every cell in the maze exactly once, and it generates edges by creating a path (removing a wall), it has to have a solution.
April 2nd, 2007 at 12:29 am
As a matter of being technical, DFS guarantees that there is exactly one path between any two nodes across the entire maze.
Spike: the day depth-first search works is to follow literally every path available, one by one. To use it to maze a maze, you start with a full-wall grid, pick a random spot, then depth-first search paths away from it. The tricks are two-fold: 1) you pick the next cell to search from the ones available at random, and 2) cells that have already been reached somewhere else are not valid options.
Given those two criteria, you can get a pretty surprisingly reasonable maze, although it will have long runs and be generally relatively easy to solve. The key to understanding that type of maze is to observe that DFS is quite literally just rendering a maze as an unbalanced tree, shown on a 2d grid; it’s just making children, then walking back up the tree until there’s room for more and doing those too, etc. Because you know that it’s a tree, then seeing why there’s exactly one path between any two points should suddenly be obvious.
Technically, this is true of any “perfect” maze (a singly connected maze with no loops, braids, under/over tesseracts, jump points, and where every cell is reachable.) However, in the case of depth-first search, the reason why it should be so becomes relatively obvious, as well as why it doesn’t matter where start and finish are for purposes of generating a valid maze.