Hex Maze Part 2

AID: 7850
  • Status: Published

9900 points

  • By
  • TypeTutorial
  • Posted on2011-09-24 at 01:01:32
Awards
  • Experts Exchange Approved
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.
Fig2-1.jpg
  • 327 KB
  • Hex maze with solution
Hex maze with solution

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.
Fig2-2.jpg
  • 34 KB
  • Winding through the maze
Winding through the maze

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
  • 10 KB
  • Includes th images folder
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>
                                    
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382:
383:
384:
385:
386:
387:
388:
389:
390:
391:
392:
393:
394:
395:
396:
397:
398:
399:
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:
410:
411:
412:
413:
414:
415:
416:
417:
418:
419:
420:
421:
422:
423:
424:
425:
426:
427:
428:
429:
430:
431:
432:
433:
434:
435:
436:
437:
438:
439:
440:
441:
442:
443:
444:
445:
446:
447:
448:
449:
450:
451:
452:
453:
454:
455:
456:
457:
458:
459:
460:
461:
462:
463:
464:
465:
466:
467:
468:
469:
470:
471:
472:
473:
474:
475:
476:
477:
478:
479:
480:
481:
482:
483:
484:
485:
486:
487:
488:
489:
490:
491:
492:
493:
494:
495:
496:
497:
498:
499:
500:
501:
502:
503:
504:
505:
506:
507:
508:
509:
510:
511:
512:
513:
514:
515:
516:
517:
518:
519:
520:
521:
522:
523:
524:
525:
526:
527:
528:
529:
530:
531:
532:
533:
534:
535:
536:
537:
538:
539:
540:
541:
542:
543:
544:
545:
546:
547:
548:
549:
550:
551:
552:
553:
554:
555:
556:
557:
558:
559:
560:
561:
562:
563:
564:
565:
566:
567:
568:
569:
570:
571:
572:
573:
574:
575:
576:
577:
578:
579:
580:
581:
582:
583:
584:
585:
586:
587:
588:
589:
590:
591:
592:
593:
594:
595:
596:
597:
598:
599:
600:
601:
602:
603:
604:
605:

Select allOpen 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!
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
    Asked On
    2011-09-24 at 01:01:32ID7850
    Tags

    JavaScript

    ,

    hexagonal maze

    ,

    maze solution algorithm

    ,

    HTML

    ,

    depth-first searching

    ,

    Dan Rollins

    Topic

    JavaScript

    Views
    5157

    Comments

    Expert Comment

    by: WaterStreet on 2011-10-01 at 19:21:29ID: 31958

    Nice high-quality work.  Voted Yes, above

    Author Comment

    by: DanRollins on 2011-10-07 at 21:14:44ID: 32165

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

    Expert Comment

    by: WaterStreet on 2011-10-08 at 20:35:40ID: 32173


    Really neat

    Add your Comment

    Please Sign up or Log in to comment on this article.

    Join Experts Exchange Today

    Gain Access to all our Tech Resources

    Get personalized answers

    Ask unlimited questions

    Access Proven Solutions

    Search 3.2 million solutions

    Read In-Depth How-To Guides

    1000+ articles, demos, & tips

    Watch Step by Step Tutorials

    Learn direct from top tech pros

    And Much More!

    Your complete tech resource

    See Plans and Pricing

    30-day free trial. Register in 60 seconds.

    Loading Advertisement...

    Top JavaScript Experts

    1. leakim971

      511,289

      Sage

      2,168 points yesterday

      Profile
      Rank: Genius
    2. mplungjan

      291,279

      Guru

      2,800 points yesterday

      Profile
      Rank: Savant
    3. nap0leon

      195,491

      Guru

      0 points yesterday

      Profile
      Rank: Sage
    4. Proculopsis

      182,948

      Guru

      0 points yesterday

      Profile
      Rank: Sage
    5. COBOLdinosaur

      157,309

      Guru

      0 points yesterday

      Profile
      Rank: Genius
    6. chaituu

      130,684

      Master

      0 points yesterday

      Profile
      Rank: Sage
    7. Ray_Paseur

      130,217

      Master

      330 points yesterday

      Profile
      Rank: Savant
    8. tommyBoy

      125,345

      Master

      0 points yesterday

      Profile
      Rank: Genius
    9. StingRaY

      114,318

      Master

      0 points yesterday

      Profile
      Rank: Wizard
    10. DaveBaldwin

      80,081

      Master

      336 points yesterday

      Profile
      Rank: Genius
    11. ansudhindra

      79,054

      Master

      2,000 points yesterday

      Profile
      Rank: Wizard
    12. ChrisStanyon

      62,768

      Master

      800 points yesterday

      Profile
      Rank: Sage
    13. hielo

      61,266

      Master

      0 points yesterday

      Profile
      Rank: Savant
    14. HainKurt

      59,030

      Master

      0 points yesterday

      Profile
      Rank: Genius
    15. BuggyCoder

      54,739

      Master

      0 points yesterday

      Profile
      Rank: Sage
    16. mroonal

      54,339

      Master

      10 points yesterday

      Profile
      Rank: Sage
    17. tagit

      54,093

      Master

      1,600 points yesterday

      Profile
      Rank: Genius
    18. gurvinder372

      52,824

      Master

      10 points yesterday

      Profile
      Rank: Genius
    19. basicinstinct

      52,586

      Master

      0 points yesterday

      Profile
      Rank: Genius
    20. JonNorman

      45,158

      2,200 points yesterday

      Profile
      Rank: Master
    21. Lalit-Chandra

      44,420

      0 points yesterday

      Profile
      Rank: Master
    22. xmediaman

      36,450

      3,800 points yesterday

      Profile
      Rank: Guru
    23. kozaiwaniec

      33,100

      0 points yesterday

      Profile
      Rank: Guru
    24. Kravimir

      32,700

      0 points yesterday

      Profile
      Rank: Genius
    25. designatedinitializer

      32,300

      0 points yesterday

      Profile
      Rank: Master

    Hall Of Fame