Community Pick: Many members of our community have endorsed this article.
Editor's Choice: This article has been selected by our editors as an exceptional contribution.

Hex Maze Part 2

DanRollins
CERTIFIED EXPERT
Published:
In Part 1 we covered the hexagonal maze basics -- how the cells are represented in a JavaScript array and how the maze is displayed.  In this part, we'll add logic to find the solution to the maze using a depth-first search, and we'll animate the action to make it fun to watch.
Hex maze with solutionThink of a hedge maze (perhaps like the one in the movie The Shining or Harry Potter and the Goblet of Fire).  If you know that there is exactly one true path from start to finish, then it is pretty easy to solve.  Just put your left hand on one wall and keep touching that wall as you move forward.  That will force you to always make every available left turn.  When you reach a cul-de-sac (dead end), you'll circle around and retrace your path to a room has more than one exit and, this time, the left turn will be through a doorway you have not explored.
Winding through the mazeNow imagine that when you hit a cul-de-sac, you could zoom directly back to the room that had the most recent decision point.  Then you could resume with the "always turn left" routine and you would be exploring an uncharted path.  That's essentially the algorithm that I devised for solving this maze.

This is called a depth-first search because it goes as far as it can along one branch of the decision tree before it begins to explore a different branch.  The algorithm lends itself well to a stack-oriented implementation.  Upon entry into any cell, the program PUSHes all continuations (neighboring cells connected by a door with this cell).  Then it POPs one off the top, effectively moving into one of those rooms.  For instance, if there is only one exit, it PUSHes then immediately POPs that connecting room.  When it hits a cul-de-sac, a POP brings it back to a cell with multiple exits (the last decision point) and it continues the search.

My implementation is complicated by two requirements: 1) The animated action is more interesting to watch if you can see the program retrace its steps after a cul-de-sac -- it appears to be probing forward and backing out, almost like an organic life form.  2) I want to end up with a list that contains the solution.

To meet those goals, I made a small addition:  On entry to any cell, I PUSH the current location with a special code that means "This is a breadcrumb" and when I hit a cul-de-sac, I POP those breadcrumb entries to erase the cell highlight... animating the "jump" back to the earlier decision point as a series of steps.  When the maze is solved, the breadcrumbs that remain on the stack are a list of the cells that make up the solution.

All of this is complicated by the issue of the browser refusing to refresh the display until an event is ended.  In order to animate the action, I had to use the technique I described in Part 1:  Run the solving logic one step at-a-time, driven by a 1ms timer tick.


More to Explore

If you find yourself playing around with this code, here are a few things you might consider trying:

With the current maze generation logic, most cells end up with just two doors.  If you want a more complex maze (harder for a human to solve) you could modify the DoOneStepCreate() function as follows:  In the "Trapped!" scan, starting on line 319  rather than just accepting the first qualified branching point, you could make a pass to find a cell that already has three or more doors that is next to a cell with no doors.   The result would be more 4- and even 5-way decision points.  

Or rather than scanning (and creating branches) only after hitting a cul-de-sac, just force the "Trapped!" logic to do a scan after a random or pre-set sequence of normal steps.

Or change the "Trapped!" logic to bias it toward making more branching points in the top-left quadrant (near the starting cell).  That would tend to increase the solving difficulty for both human and machine.
The maze display graphics could be improved with regard to the highlighted rooms.  Rather than a red asterisk to highlight a cell, I think it would look better if the entire cell were filled red (or perhaps a honey hue of golden yellow).  This would entail creating additional versions of all six parts of the cell image -- not just the two central ones -- and modifying the SetCellImg() function.
The outer boundaries of the maze are rectangular, but it could be made to fit inside of a hexagon.  I think that would look cool, implemented on a transparent background (e.g., in a Win7 gadget; see Create a Win7 DropTarget Gadget for info on how to create a transparent background for a gadget.)
The display is not particularly attractive in the "Tiny" mode.  Creating a separate set of smaller images (rather than scaling the full-sized ones) could be a nice improvement.
 
Try your hand at tweaking the search algorithm.  Depth-first is rarely the most efficient way to traverse a large decision tree.  If nothing else, you could bias the algorithm to try to go down and right first, since that's the direction of the maze exit.  

Another thing you'll notice is that the algorithm can get itself into a long-term dead end that a sprinkling of oversight logic could avoid.  For instance, if it is exploring the lower left corner of the maze but there is no possible exit from that quadrant, then it could immediately pop back to a point where that is not true -- avoiding a lengthy exploration that is certain to be moot.

Here's an idea:  Try solving the maze from both ends simultaneously.  Make two copies of the TAutoSolveStack object and start timers to cycle both of them.  When the two paths meet, combine them for the solution.  This will almost certainly find the solution in a fraction of the time.
Explore and resolve the reasons that IE 9 is so much slower than Chrome and Firefox when creating and solving the maze, and discover ways to improve the speed.  One clue is that when the images are not scaled, IE seems to keep pace or even out-perform the others.


Conclusion

I had a lot of fun reworking this old program in JavaScript.  It brought back memories of the days when programming was fun and exciting.  I hope that the algorithms and techniques presented here might be useful, or at least vaguely interesting, to you.

The listing below contains the finished HTML and this link:
HexMaze2.zip
is a ZIP file that contains the HTML file and a folder with the required images.  Just unzip into a temporary folder, then double-click the HTML file.  

<html>
                      <!-- HexMaze, version 2.0, by Dan Rollins -->
                      <!-- Creates AND SOLVES a maze of hexagonal cells, similar to a honeycomb -->
                      <body onload='DoStartup();'>
                      Width:<input id='ctrlWide' type='text' size='3' value='8'/>
                      Height:<input id='ctrlHigh' type='text' size='3' value='8'/>
                      Size:<select id='ctrlScale' size='1' value='2'>
                                <option value="1"/>Tiny
                                <option value="2"/>Small
                                <option value="3" selected />Normal
                                <option value="4"/>Large
                      </select>
                      <input type='button' value='Create the Maze' onclick='DoCreate();' />
                      <input type='button' value='AutoSolve' onclick='DoAutoSolve();' />
                      <br/>
                      <table border='5' cellpadding='0' cellspacing='0'><tr><td id='mazeDisplay'></td></tr></table>
                      </body>
                      
                      <script type="text/javascript">
                      var gnWinWide= 700;
                      var gnWinHigh= 700;
                      var gsWinCaption= "HexMaze v2 -- By Dan Rollins";
                      
                      //-------------- used in incremental Create/Solve
                      var ganIntervalIds;
                      var CNUM_TIMERCNT=1;
                      
                      var gnX;
                      var gnY;
                      var gnEntryDoor; // used in AutoSolve
                      var gfCreateDone= false;
                      
                      function DoStartup() {  // called from BODY ONLOAD 
                      	SetWindowSize( gnWinWide, gnWinHigh ); // app init stuff
                      	document.title= gsWinCaption;
                      }
                      function SetWindowSize(w,h) {            // known bug in mshtml; try/catch fixes
                      	try     { window.resizeTo( w, h ); } 
                      	catch(e){ SetWindowSize(w,h); }      // do it until it works
                      }
                      
                      //---------------------------------------------------
                      var gtMaze;       // the TMaze object -- variables and functions
                      
                      //------------------------------ U/I input variables
                      var gnViewSize=2;  // 1=Tiny, 2=Small, 3=Normal, 4=Large
                      var gnHigh= 14;    // must be a multiple of 2 (use input value * 2)
                      var gnWide= 15;   // must be a multiple of 2 (use input value * 2)
                      
                      //------------------------------ CONSTANTS
                      DIR_N=0;   DIR_NE=1;  DIR_SE=2;  DIR_S=3;  DIR_SW=4;   DIR_NW=5;
                      DOOR_N=1;  DOOR_NE=2; DOOR_SE=4; DOOR_S=8; DOOR_SW=16; DOOR_NW=32;  DOOR_ALL=63;
                      CELL_LIT= 64;
                      BREAD_CRUMB= -1;
                      
                      
                      //----------------------------- delta arrays  00 offsets to add to 
                      //-----------------------------   X,Y when moving in any of 6 directions
                      var ganDeltaX= new Array(6);
                      var ganDeltaY= new Array(6);
                      
                      ganDeltaX[DIR_N]  = 0;  ganDeltaY[DIR_N]   =-2;  
                      ganDeltaX[DIR_NE] = 1;  ganDeltaY[DIR_NE]  =-1;
                      ganDeltaX[DIR_SE] = 1;  ganDeltaY[DIR_SE]  = 1;
                      ganDeltaX[DIR_S]  = 0;  ganDeltaY[DIR_S]   = 2;  
                      ganDeltaX[DIR_SW] =-1;  ganDeltaY[DIR_SW]  = 1;
                      ganDeltaX[DIR_NW] =-1;  ganDeltaY[DIR_NW]  =-1;  
                      
                      //=======================================================
                      // The 2-dimensional array that contains the cell information
                      //
                      function TMazeArray( nHigh, nWide ) {
                          a= new Array(nHigh);
                          for (var i=0; i < nHigh; i++) {
                              a[i]= new Array(nWide);
                              for (var j=0; j< nWide; j++) {	
                                  a[i][j]= 0; 
                              }
                          }
                          return a;
                      }
                      
                      //=======================================================
                      //=======================================================
                      //=======================================================
                      // The TMaze object
                      //------------------------------------------------------------------------------ Ctor
                      function TMaze( nHigh, nWide ) {
                          this.high= nHigh;
                          this.wide= nWide;
                          this.ary=  new TMazeArray( nHigh, nWide );
                      
                          var CellsPer2Lines= nWide-1;  // input width (cells on top) plus oddLine cells (one fewer)
                      
                          this.totRooms= (CellsPer2Lines * (nHigh/2) ) - ((nWide/2)-1);  // less (short) bottom line
                          this.curRoomCnt= 0;  // rooms that have been visited/door opened
                          
                          this.GetCell=      function(x,y)       { return (this.ary[y][x]); }
                          this.SetCell=      function(x,y,value) { this.ary[y][x]=value; }
                      
                          this.HasCellBit=   function(x,y,value) { return( (this.ary[y][x] & value) == value); }
                          this.SetCellBit=   function(x,y,value) { this.ary[y][x] |= value; }
                          this.ClearCellBit= function(x,y,value) { this.ary[y][x] &= ~value; }
                          this.ToggleCellBit=function(x,y,value) { this.ary[y][x] ^= value; }
                      
                          this.IsEmptyCellAt= IsEmptyCellAt;  // some member fns, defined below
                          this.IsValidXY=     IsValidXY;
                          this.GetNewXY=      GetNewXY;
                      }
                      
                      //----------- TRUE if cell in that direction is empty and valid
                      //
                      function IsEmptyCellAt( x,y, dir) {
                          var o= this.GetNewXY( x,y, dir);
                      
                          if ( !this.IsValidXY( o.newX, o.newY))   return (false); 
                          if (this.GetCell( o.newX, o.newY) != 0)  return (false);
                      
                          return (true);  // yes, it's possible to move into that cell
                      }
                      
                      //------------------------------------------------------------------------------
                      // return -1 if that would be an invalid move (off the board)
                      // true if X,Y is on the board
                      //
                      function IsValidXY( x,y ) {
                          if (y < 0) return (false);
                          if (y > this.high-1) return( false );
                      
                          if (x < 0)           return( false );
                          if (x > this.wide-1) return( false );
                      
                          if (y & 1) {  // on off Y, max X an maxY are 1 less
                              if (x > this.wide-2)  return( false );
                              if (y > this.high-2) return( false );
                          }
                          return ( true );  // possible to move into that direction
                      }
                      
                      //------------------------------------------
                      // If I move in a direction, what are the new X,Y values?
                      // Return an object with newX and newY properties
                      //
                      function GetNewXY( x,y, dir ) {
                          var oRet= {"newX":-1, "newY":-1, "isValid":false };
                      
                          var newX= x;
                          var newY= y;
                      
                          newX += ganDeltaX[dir];  // add the deltas
                          newY += ganDeltaY[dir];
                      
                          if ( this.IsValidXY(newX,newY) ) {
                              oRet.newX= newX;
                              oRet.newY= newY;
                              oRet.isValid= true;
                          }
                          return( oRet );
                      }
                      //=====================================================
                      //=====================================================
                      //===================================================== end of TMaze members
                      
                      //========================================= utils for generating the maze display
                      function ImgUrl( s ) {  // 28, 14, or 7
                          var sOut="images/" +s+ ".bmp";
                          return( sOut );
                      }
                      function ImgHtml( s, nHigh, x,y ) {  // 28, 14, or 7
                          var sOut="<img HEIGHT=" +nHigh+" src='" +ImgUrl(s)+ "'"
                          if (x != null ) {
                             sOut += " onclick='DoClick(" +x+ "," +y+ ");'";  // for (minimal) user interaction
                          }
                          sOut += ">";
                          return( sOut );
                      }
                      //------------------------------------------
                      // generate the inner HTML (all of the img objects)
                      //
                      function DrawMaze() {
                          var nImgHigh=28;
                          if (gnViewSize == 1) nImgHigh=7;   // tiny   25%
                          if (gnViewSize == 2) nImgHigh=14;  // small  50%
                          if (gnViewSize == 3) nImgHigh=28;  // normal 100%
                          if (gnViewSize == 4) nImgHigh=42;  // large  150%
                      
                          var s="";
                          var s1="";
                          var i="";   // image base name (eg, "d1" or "w1" -- door or wall )
                      
                          //-------------------------------------- draw the top line
                          for (x=0; x < gtMaze.wide; x+=2) {
                              s1 += ImgHtml("zt1", nImgHigh);
                              s1 += ImgHtml("zt2", nImgHigh);
                              s1 += ImgHtml("zt3", nImgHigh);
                              if ( x < gtMaze.wide-2 ) {
                                   s1 += ImgHtml("zt4", nImgHigh);
                              }
                          }
                          s1 += "<br>";  // finished with top line (special handling for top edge of maze)
                          s+= s1;
                      
                          for (y=0; y < gtMaze.high; y+=2) {
                              s1="";
                              for (x=0; x < gtMaze.wide; x+=2) {
                                  var v= gtMaze.GetCell(x, y);
                                  var v2= gtMaze.GetCell(x+1, y+1);
                      
                                  i= "w1"; if ( v & DOOR_NW ) i= "d1";   s1 += ImgHtml(i, nImgHigh);
                                  i= "w2"; if ( v & DOOR_N  ) i= "d2";   s1 += ImgHtml(i, nImgHigh, x,y);
                                  i= "w3"; if ( v & DOOR_NE ) i= "d3";   s1 += ImgHtml(i, nImgHigh);
                                  if ( x < gtMaze.wide-2 ) {  // don't show on the rightmost column
                                      i= "w5"; if ( v2 & DOOR_N ) i= "d5"; 
                                      if (y == 0 ) s1 += ImgHtml(i, nImgHigh);      // no onClick for these
                                      else         s1 += ImgHtml(i, nImgHigh, x+1,y-1);
                                  }
                              }
                              s1 += "<br>";     // done with first line (top part of hexagon)
                              s+= s1;
                              //----------------------- second line of images per cell row
                              s1="";
                              for (x=0; x < gtMaze.wide; x+=2) {
                                  var v=  gtMaze.GetCell(x, y);
                                  var v2= gtMaze.GetCell(x+1, y+1);
                      
                                  i= "w6"; if ( v & DOOR_SW ) i= "d6"; s1 += ImgHtml(i, nImgHigh);
                                  i= "w5"; if ( v & DOOR_S  ) i= "d5"; s1 += ImgHtml(i, nImgHigh, x,y);
                                  i= "w4"; if ( v & DOOR_SE ) i= "d4"; s1 += ImgHtml(i, nImgHigh);
                                  if ( x < gtMaze.wide-2 ) {  // don't show on the rightmost column
                                      i= "w2";  if ( v2 & DOOR_N ) i= "d2";  
                                      if ( y==gtMaze.high-2 )  s1 += ImgHtml(i, nImgHigh);   // no onClick for these
                                      else                     s1 += ImgHtml(i, nImgHigh, x+1,y+1);
                                  }
                              }
                              s1 += "<br>";  // done with second line (bottom part of hexagon)
                              s+= s1;
                          }
                          //-------------------------------------- draw the bottom line
                          s1="";
                          for (x=0; x < gtMaze.wide; x+=2) {
                              s1 += ImgHtml("zb1", nImgHigh);
                              s1 += ImgHtml("zb2", nImgHigh);
                              s1 += ImgHtml("zb3", nImgHigh);
                              if ( x < gtMaze.wide-2 ) {
                                   s1 += ImgHtml("zb4", nImgHigh);
                              }
                          }
                          s1 += "<br>";  // done with bottom line (special handling for bottom edge of maze)
                          s+= s1;
                      
                          document.getElementById('mazeDisplay').innerHTML= s;
                      }
                      
                      //==========================================
                      function ClearTheMaze() {
                          gtMaze=new TMaze( gnHigh, gnWide );
                          for (var y=0; y < gtMaze.high; y++) {
                              for (var x=0; x < gtMaze.wide; x++) {
                                  gtMaze.ary[y][x]= 0;
                              }
                          }
                      }
                      
                      //=========================================================
                      // Create the maze, using the incremental technique to enable 
                      // watching the creation process
                      //=========================================================
                      
                      function DoCreate() {
                          //-------------------------------- collect the use input
                          gnWide=     document.getElementById('ctrlWide' ).value * 2;
                          gnHigh=     document.getElementById('ctrlHigh' ).value * 2;
                          gnViewSize= document.getElementById('ctrlScale').value;
                       
                          ClearTheMaze();       // set all cells to 0
                          DrawMaze();           // add all of the IMG elements
                      
                          SetupForCreate();     // do some some setup
                          TimersStartCreate();  // do the incremental maze creation steps until done
                      }
                      
                      //---------------------------------------------------------
                      function SetupForCreate() {
                          gnX= RndmInt(0, (gtMaze.wide/2) ) * 2; // only even-numbered array elements ae valid   
                          gnY= RndmInt(0, (gtMaze.high/2) ) * 2;
                      
                          gfCreateDone= false;
                          gtMaze.curRoomCnt= 1;  // account for the entry room
                      }
                      
                      //---------------------------------------------------------
                      function DoFinishCreate() {
                          TimersStop();
                          gtMaze.SetCellBit( 0,0, DOOR_NW );  // put the entrance door in place
                          SetCellImg( 0, 0 );                 //============= draw the changed room
                      
                         var nExitX= gnWide-2;
                         var nExitY= gnHigh-2;
                      
                          gtMaze.SetCellBit(nExitX,nExitY, DOOR_SE );  // put the exit door in place
                          SetCellImg(nExitX,nExitY);                   //========= draw the changed room
                          gfCreateDone= true;
                          // DrawMaze();    // already drawn as you watched!
                      }
                      
                      //---------------------------------------------------------
                      // Perform one step of the creation process
                      // Add a door to a room and the adjacent room
                      // If stuck, scan for a place to branch
                      //
                      function DoOneStepCreate() {
                          if ( gtMaze.curRoomCnt >= gtMaze.totRooms ) { // all done!
                              DoFinishCreate();
                              return;
                          }
                          var anDirs= new Array(6);                 // N, WE, SE, S, SW, NW
                          var nDirCnt= GetDirs( gnX, gnY, anDirs ); // Fill anDirs with valid directions to move from here
                      
                          while( nDirCnt == 0 ) {          // Trapped! Look for a room I've been in
                              gnY++;                       //          that is next to a doorless one
                              if ( gnY > gtMaze.high-1 ) {
                                  gnY=0; gnX++;
                                  if ( gnX > gtMaze.wide-1 ) {
                                      gnX=0;
                                  }
                              }
                              if ( 0 == gtMaze.GetCell(gnX,gnY) ) {
                                  continue;
                              }
                             nDirCnt= GetDirs( gnX, gnY, anDirs );
                          }
                          //-------- It is now possible to move to another room
                          var nDirIdx= RndmInt(0, nDirCnt);       // 0 thru possible dirs -- pick one at random
                      
                          var nDir = anDirs[nDirIdx];              // 0, 1, 2, 3, 4,  or 5  (direction code)
                          var nDoorVal= (1 << nDir);               // 1, 2, 4, 8, 16, or 32 (door value)
                      
                          gtMaze.SetCellBit( gnX,gnY, nDoorVal );  // put the door in place
                          SetCellImg( gnX,gnY );                   //============= draw the changed room
                      
                          var o= GetNewXY( gnX,gnY, nDir);     
                          gnX= o.newX;                             // move into that room
                          gnY= o.newY;
                      		                                     //======= set door in this room, too
                          nDir= (nDir+3) % 6;                      //=== clockwize opposite (1->4, 2->5, 3->0, etc
                          nDoorVal= (1 << nDir);                   // 1, 2, 4, 8, 16, or 32 (door value)
                      
                          gtMaze.SetCellBit( gnX,gnY, nDoorVal );  // put the door in place
                          SetCellImg( gnX,gnY );                   //============= draw the changed room
                      
                          gtMaze.curRoomCnt++;
                          // done with this timer tick
                      }
                      
                      //------------------------------------------------------------------------------
                      // See which directions are possible; populate array anDirs
                      //
                      function GetDirs( x, y, anDirs ) {
                          var nCnt=0;
                      
                          var f= gtMaze.IsEmptyCellAt( x,y, DIR_N );
                          if (f) anDirs[nCnt++]= DIR_N;          // can go N
                      
                          f= gtMaze.IsEmptyCellAt( x,y, DIR_NE );
                          if (f) anDirs[nCnt++]=    DIR_NE;      // can go NE
                      
                          f= gtMaze.IsEmptyCellAt( x,y, DIR_SE );
                          if (f) anDirs[nCnt++]=    DIR_SE;      // can go SE
                      
                          f= gtMaze.IsEmptyCellAt( x,y, DIR_S );
                          if (f) anDirs[nCnt++]=    DIR_S;       // can go S
                      
                          f= gtMaze.IsEmptyCellAt( x,y, DIR_SW );
                          if (f) anDirs[nCnt++]=    DIR_SW;      // can go SW
                      
                          f= gtMaze.IsEmptyCellAt( x,y, DIR_NW );
                          if (f) anDirs[nCnt++]=    DIR_NW;      // can go NW
                      
                          return( nCnt );
                      }
                      
                      //------------------------------------------------------------------------------
                      // utility fn:  get a random integer in the specified range, inclusive
                      //
                      function RndmInt( min, max ) {
                          var tmp= Math.random() * (max-min);
                          return( Math.floor( tmp ) + min );
                      }
                      
                      //===================================================
                      // note: It is possible to set up multiple timers, in the hopes of faster completion
                      //       But experience shows that even a single a 1ms timer outpaces the screen updating
                      //===================================================
                      function TimersStartCreate() {
                      	ganIntervalIds= new Array( CNUM_TIMERCNT );
                      	for (j=0; j< CNUM_TIMERCNT; j++ ) {
                      		ganIntervalIds[j]= window.setInterval( "DoOneStepCreate();", 1 );
                      	}
                      }
                      function TimersStartAutoSolve() {
                      	ganIntervalIds= new Array( CNUM_TIMERCNT );
                      	for (j=0; j< CNUM_TIMERCNT; j++ ) {
                      		ganIntervalIds[j]= window.setInterval( "DoOneStepAutoSolve();", 1 );
                      	}
                      }
                      function TimersStop() {
                      	for (j=0; j< CNUM_TIMERCNT; j++ ) {
                      		window.clearInterval( ganIntervalIds[j] );
                      	}
                      }
                      
                      //===========================================================
                      // Draw all of the parts of a cell after a change
                      // This could be more efficient (update only the changed images)
                      // Assumes that the maze grphaics are the only (or first) IMG elements
                      //
                      function SetCellImg( x,y ) {
                          var nRowWide= (2*gnWide) - 1;        // this many images per row
                          var nImgIdx=  (y*nRowWide) + (x*2);  // 
                      
                          nImgIdx += (2*gnWide) - 1;  // account for top line
                      
                          var i= "";
                          var v= gtMaze.GetCell( x,y );
                      
                          i= "w1"; if ( v & DOOR_NW ) i= "d1";  document.images[nImgIdx+0].src= ImgUrl(i);
                          i= "w2"; if ( v & DOOR_N  ) i= "d2";  if ( v & CELL_LIT ) i= "x"+i;
                                                                document.images[nImgIdx+1].src= ImgUrl(i);
                          i= "w3"; if ( v & DOOR_NE ) i= "d3";  document.images[nImgIdx+2].src= ImgUrl(i);
                      
                          nImgIdx += nRowWide; // row below
                      
                          i= "w6"; if ( v & DOOR_SW ) i= "d6";  document.images[nImgIdx+0].src= ImgUrl(i);
                          i= "w5"; if ( v & DOOR_S )  i= "d5";  if ( v & CELL_LIT ) i= "x"+i;
                                                                document.images[nImgIdx+1].src= ImgUrl(i);
                          i= "w4"; if ( v & DOOR_SE ) i= "d4";  document.images[nImgIdx+2].src= ImgUrl(i);
                      
                         return;
                      }
                      //-------------------------------------------------
                      // Handle clicks in the maze -- adds or removes an * in the clicked cell
                      function DoClick(x,y) {
                          gtMaze.ToggleCellBit( x,y,CELL_LIT );
                          SetCellImg(x,y);  
                      }
                      function HiliteCell( x, y, fHilite ) {
                      	if ( fHilite ) gtMaze.SetCellBit(  x,y, CELL_LIT);
                      	else           gtMaze.ClearCellBit(x,y, CELL_LIT);
                      	SetCellImg( x,y );
                      }
                      function IsCellHilited( x, y ) {
                      	if ( gtMaze.GetCell(x,y) >= CELL_LIT ) {
                      		return( true );
                      	}
                      	return( false );
                      }
                      function ClearAllHilites() {
                      	for (x=0; x< gnWide; x++ ) {
                      		for( y=0; y< gnHigh; y++ ) {
                      			if ( IsCellHilited( x, y ) ) {
                      				gtMaze.ClearCellBit(x,y,CELL_LIT);
                      				SetCellImg(x,y);
                      			}
                      		}
                      	}
                      }
                      
                      //===================================================
                      //===================================================
                      //===================================================
                      
                      // ================== Solution object
                      function Pop() {
                      	gnX= this.anX[this.nSP]; gnY= this.anY[this.nSP]; gnEntryDoor= this.anEntryDoor[this.nSP];
                      	this.nSP--;
                      }
                      function Push(x,y,door) {
                      	this.nSP++;	
                      	this.anX[this.nSP]= x; this.anY[this.nSP]= y; this.anEntryDoor[this.nSP]= door;
                      }
                      //------------------------------------------------------------------------------ Ctor
                      function TAutoSolveStack( nSize ) {
                      	this.nSP= 0;          // stack pointer
                      	this.anX=         new Array( nSize );
                      	this.anY=         new Array( nSize );
                      	this.anEntryDoor= new Array( nSize );
                      	for ( j=0; j< nSize; j++ ) {
                      		this.anX[j]=0;
                      		this.anY[j]=0;
                      		this.anEntryDoor[j]=0;
                      	}
                          this.Push= Push;
                          this.Pop= Pop;
                      }
                      
                      //=========================================================
                      // AutoSolve Maze
                      //=========================================================
                      function DoAutoSolve() {
                          if ( !gfCreateDone ) {
                      		alert("Please create the maze first!" )
                      		return( false );
                      	}
                      	SetupForAutoSolve();
                      	TimersStartAutoSolve();
                      }
                      //---------------------------------------------------------
                      function SetupForAutoSolve() {
                      	if ( gtMaze.HasCellBit(0,0, CELL_LIT) ) { // if a retry, clear old solution
                      		ClearAllHilites();
                      	}
                      	gnX= 0;
                      	gnY= 0;
                      	gnEntryDoor= DOOR_NW;
                      	gfErasing= false;
                      
                      	gtStack= new TAutoSolveStack( 100 );
                      	//--------------- prime the pump (so first Pop() puts cur loc at maze entry cell)
                      	if ( gtMaze.HasCellBit(0,0, DOOR_SE) ) gtStack.Push( 1,1, DOOR_NW );
                      	if ( gtMaze.HasCellBit(0,0, DOOR_S ) ) gtStack.Push( 0,2, DOOR_N  );
                      
                      	HiliteCell( gnX, gnY, true );           // enter the cell
                      }
                      //---------------------------------------------------------
                      function DoFinishAutoSolve() {
                          TimersStop();
                          gfSolveDone = true;
                      }
                      
                      //---------------------------------------------------------
                      function DoOneStepAutoSolve() {
                      	if ( gfErasing ) {
                      		DoOneEraseAfterDeadEnd();
                      		return;
                      	}
                      
                      	gtStack.Pop(); // sets  gnX, gnY, gnEntryDoor 
                      	var x=gnX;
                      	var y=gnY;
                      
                      	HiliteCell( gnX, gnY, true );           // enter the cell
                      
                      	if ( (x == gnWide-2) && (y == gnHigh-2) ) {
                      		alert( "Solution Found! Length: " + gtStack.nSP );
                      		DoFinishAutoSolve();
                      		return;
                      	}
                      
                          gtStack.Push( x, y, BREAD_CRUMB );  // save current location (used in erasing dead end paths)
                      
                          // look in all directions (except the entry) for an exit.
                          // save each exit on the stack, to be popped off after a dead end.
                      
                         	fHasExit= false;
                          for ( nDir=DIR_N; nDir <= DIR_NW; nDir++ ) {
                              nDoor= 1 << nDir;
                          	if ( gnEntryDoor == nDoor ) { // don't consider the entry door an exit
                                  continue;
                              } 
                              if ( gtMaze.HasCellBit( x,y, nDoor ) ) {  // if there is a door in this direction
                                  var o= GetNewXY( x,y, nDir );     
                                  var nOppDoor=  1 << ((nDir+3) % 6);  //=== door in opposite direction
                                  gtStack.Push( o.newX, o.newY, nOppDoor ); 
                                  fHasExit= true;        
                              }
                          }
                      	if ( !fHasExit ) {  // no other exits (aside from the entry)
                      		gfErasing= true;  // processing a dead end starts
                      	}
                      	return; // done with this timer tick
                      }
                      
                      //---------------------------------------------------------
                      function EraseDeadEnd() {
                      	while( true ) {
                      		gtStack.Pop(); // sets  gnX, gnY, gnEntryDoor 
                      		if ( gnEntryDoor == BREAD_CRUMB ) {
                      			HiliteCell( gnX, gnY, false );			
                      		}
                      		else {
                      			gtStack.Push( gnX, gnY, gnEntryDoor );
                      			break;
                      		}
                      	}
                      }
                      
                      //---------------------------------------------------------
                      function DoOneEraseAfterDeadEnd() {
                      	if ( !gfErasing ) {
                      		return;
                      	}
                      	gtStack.Pop(); // sets  gnX, gnY, gnEntryDoor 
                      	if ( gnEntryDoor == BREAD_CRUMB ) {
                      		HiliteCell( gnX, gnY, false );			
                      		return;
                      	}
                      	else {
                      		gtStack.Push( gnX, gnY, gnEntryDoor );
                      		gfErasing= false;
                      		return;
                      	}
                      }
                      
                      </script>
                      </html>

Open in new window


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
If you liked this article and want to see more from this author, please click the Yes button near the:
      Was this article helpful?
label that is just below and to the right of this text.   Thanks!
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
8
10,691 Views
DanRollins
CERTIFIED EXPERT

Comments (3)

CERTIFIED EXPERT

Commented:
Nice high-quality work.  Voted Yes, above
CERTIFIED EXPERT
Author of the Year 2009

Author

Commented:
If you want to see the program in action without doing a download, just click here.
CERTIFIED EXPERT

Commented:

Really neat

Have a question about something in this article? You can receive help directly from the article author. Sign up for a free trial to get started.