Maze Solver

This is entirely gratuitous, but I couldn’t let go of the maze generator without adding in the code that actually solved the maze also. The solution code uses the same depth-first search algorithm as the generator, leaving a trail of “breadcrumbs” as it goes and rolling them back up when it hits a dead-end.

Generator: here. Source code here.

As before, I was forced to use an iterative algorithm in place of the more natural recursive one because of browser limitations. The major difference in behavior between the solver and the generator is that I wanted the search path to be displayed dynamically on the screen as it worked through the solution.

A solved 30 by 70 maze on a 6 by 6 pixel grid

The only major change from the generation code is that the outer while{} loop had to be replaced with a timer. Each iteration of the logical loop then is done on an interval, which gives the browser the chance to reflow the page. IE was the only browser with any real issues: for whatever reason it is very slow when solving the maze. I may take a look at that if I get the chance, but I think I’m done with this exercise for now.

Update: The issue with IE has been resolved.

» Posted: Friday, July 6, 2007 | Comments (6) | Permanent Link

Comments

C O N G R A T U L A T I O N S
B R A V O

Really a amazing job before holiday on beach !

» Posted by Michel on July 7, 2007 01:50 PM

I stumbled upon your maze solver - it looks good, however several times i noticed that it turns into obviously blind areas, and at times makes poor direction choices (eg, it hit the wall 2 steps above the exit, and turned up, rather than down). This behavior might be solved by pushing the neighbors onto the stack in a (left, down, up, right) order, rather than using dirs.shuffle() to put them in on a random order - that way, if in doubt you head towards where the exit is known to be, and if you are wrong, the other options are still considered.

a second improvement could be to visually display segments of the maze that have been explored.

(some examples of maze visalisation at http://www.janthor.com/maze/index.html, and a maze generator/solver similar to yours at http://www.math.com/students/puzzles/mazegen/mazegen.html)

2c worth,
Andrew

» Posted by Andrew on July 10, 2007 12:30 AM

Andrew thanks for your comments.

Certainly the solver could be made more intelligent, but I was really going for the simplest and most visually interesting mechanism more than anything else.

I’ll try a version that records backtracks and see how that goes, but I want the interface to be simple and the results visually appealing.

» Posted by winter on July 10, 2007 11:49 AM

I’ve tried to generate the puzzle but it only displays as straight lines. What might be happening? Using IE.

» Posted by Anna on July 12, 2007 04:36 PM

Hi Anna,

You’re using IE version 6 which doesn’t have the full standards support that version 7 has (and which is required by the generator.)

If you want to stick with IE, you should upgrade to version 7 anyway. Since you’re on Windows, you could also try Firefox or Opera which are both very good.

» Posted by winter on July 12, 2007 11:05 PM

Freaking awesome! Watching this thing solve is memorizing.

» Posted by Matt Cox on July 26, 2007 03:29 PM

Maze Solver

Comments

Post a comment