<

Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x

Hex Maze Part 2

Published on
19,252 Points
8,952 Views
8 Endorsements
Last Modified:
Awarded
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
Comment
Author:DanRollins
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
3 Comments
 
LVL 18

Expert Comment

by:WaterStreet
Nice high-quality work.  Voted Yes, above
0
 
LVL 49

Author Comment

by:DanRollins
If you want to see the program in action without doing a download, just click here.
0
 
LVL 18

Expert Comment

by:WaterStreet

Really neat
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Join & Write a Comment

The viewer will learn the basics of jQuery, including how to invoke it on a web page. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery.: (CODE)
The viewer will learn the basics of jQuery including how to code hide show and toggles. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery…
Next Article:

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month