//------------------------------ 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;
For instance, if the cell value is 1, there is a door to the North. If the cell value is 8, there is a door to the South. It the cell value is 9, then there are doors in both the N and S sides. This technique lets me represent any combination of walls and doors with a single integer value. If you want to learn more about using bit flags in your programming, see
<img HEIGHT=28 src='images/w1.bmp"><img HEIGHT=28 src='images/w2.bmp"><img HEIGHT=28 src='images/w2.bmp"> ... <br>
<img HEIGHT=28 src='images/w3.bmp"><img HEIGHT=28 src='images/w5.bmp"><img HEIGHT=28 src='images/w4.bmp"> ... <br>
...etc...
When done, I insert the entire string as the innerHTML of a <TD> element. It would also be possible to create the IMG elements directly, but I find that generating HTML strings is easier to code and easier to debug.
<html>
<!-- HexMaze, version 1.0, by Dan Rollins -->
<!-- Creates a maze of hexagonal cells, similar to a honeycomb -->
<body onload='DoStartup();'>
Width:<input id='ctrlWide' type='text' size='3' value='10'/>
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();' />
<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 v1 -- By Dan Rollins";
//-------------- used in incremental Create/Solve
var ganIntervalIds;
var CNUM_TIMERCNT=1;
var gnX;
var gnY;
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;
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 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);
}
//===================================================
</script>
</html>
=-=-=-=-=-=-=-=-=-=-=-=-=-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.
Comments (1)
Commented: