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 (8) | 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

Hi,

At the outset; thank u very much for taking time out and putting down ur idea into something so constructive. It would have been so easy to jst kill the idea and move on.

Also, I noticed the fact that u created this algo for ur kids fun and as plaything,..

Let me assure u that many Kids (around the world )and Some quite big ones 2 (!) are having fun with the thing.

So Kudos 2 u !

regards,

Pratik Saptarshi
India

» Posted by Pratik Saptarshi on January 7, 2009 11:03 AM

i dont understand the mechanism of the solver, why it can trace the obstacle in front of it. Can it possible to apply on a graph map?

» Posted by mumu on October 11, 2009 11:42 PM