Editor's Choice: This article has been selected by our editors as an exceptional contribution.

# Hex Maze Part 2

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.
Think 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.
Now 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 -->
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/>
</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;

//----------------------------- 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() {
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
// 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
//===================================================
ganIntervalIds= new Array( CNUM_TIMERCNT );
for (j=0; j< CNUM_TIMERCNT; j++ ) {
ganIntervalIds[j]= window.setInterval( "DoOneStepCreate();", 1 );
}
}
ganIntervalIds= new Array( CNUM_TIMERCNT );
for (j=0; j< CNUM_TIMERCNT; j++ ) {
ganIntervalIds[j]= window.setInterval( "DoOneStepAutoSolve();", 1 );
}
}
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 ) {
return( false );
}
SetupForAutoSolve();
}
//---------------------------------------------------------
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() {
gfSolveDone = true;
}

//---------------------------------------------------------
function DoOneStepAutoSolve() {
if ( gfErasing ) {
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
}

//---------------------------------------------------------
while( true ) {
gtStack.Pop(); // sets  gnX, gnY, gnEntryDoor
if ( gnEntryDoor == BREAD_CRUMB ) {
HiliteCell( gnX, gnY, false );
}
else {
gtStack.Push( gnX, gnY, gnEntryDoor );
break;
}
}
}

//---------------------------------------------------------
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>
``````

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

CERTIFIED EXPERT

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

Commented: