//the actual in-memory maze object
var Mz = new Array();

//the size of the maze
var _mRows = 6;
var _mCols = 6;

//constants used during maze generation
var _BW_ = 0;
var _RW_ = 1;
var _V_ = 2;

//key constants used for navigation
//var LEFT = 37;
//var UP = 38;
//var RIGHT = 39;
//var DOWN = 40;

//these are used for navigation
var _GO_ = false;
var _userCol = 0;
var _userRow = 0;

// push doesn't exist in IE5 (it's 5.5+ only)
Array.prototype.push = function (aObject)
{
  this[this.length] = aObject;
}

// pop doesn't exist in IE5 (it's 5.5+ only)
Array.prototype.pop = function pop()
{
  var val = null;
  if (this.length >= 1)
  {
    val = this[this.length - 1];
    delete this[this.length - 1];
    this.length--;
  }
  return val;
}

/**
  Initialize the maze, pick a random starting point, and begin generating paths.
*/
function __D_MM_(mR, mC)
{
	_mRows = mR;
	_mCols = mC;
  //setup the hedge array - initially all walls are intact
  var i, j;
  for (i=0; i<_mRows; i++)
  {
    Mz[i] = new Array();
    for (j=0; j<_mCols; j++)
    {
      Mz[i][j] = new Array();
      Mz[i][j][_BW_] = 1;
      Mz[i][j][_RW_] = 1;
      Mz[i][j][_V_] = false;
    }
  }

  //choose a random starting point
  var currCol = (Math.random()*100) % (_mCols-1);
  currCol = Math.round(currCol);
  var currRow = (Math.random()*100) % (_mRows-1);
  currRow = Math.round(currRow);

  //recursively remove walls from the maze using a Depth First algorithm
  __D_MP_(currRow, currCol);
}

/**
  Recursive function - generate the maze.

  @param R The current Row
  @param C The current Col
  @param D The Direction the previous call moved in (initial call has no D)
*/
function __D_MP_(R,C,D)
{
  //mark this cell as having been visited
  Mz[R][C][_V_] = true;

  //knock out the wall between this cell and the previous cel
  switch(D)
  {
    case "N": //if i am traveling north (came from the south), my bottom wall has been knocked out
      Mz[R][C][_BW_] = 0;
    break;

    case "S": //if i am traveling south (came from the north), my top wall has been knocked out
      Mz[R-1][C][_BW_] = 0;
    break;

    case "E": //if i am traveling east (came from the west), my left wall has been knocked out
      Mz[R][C-1][_RW_] = 0;
    break;

    case "W": //if i am traveling west (came from the east), my right wall has been knocked out
      Mz[R][C][_RW_] = 0;
    break;

    default:
      //will only get here the first time.  coming from no direction; do nothing
    break;
  }

  //build an array of directions that can be traveled in from the current position
  var directions = new Array();
  if (R > 0) directions[directions.length] = "N";
  if (R < _mRows-1) directions[directions.length] = "S";
  if (C > 0) directions[directions.length] = "W";
  if (C < _mCols-1) directions[directions.length] = "E";

  //randomly shuffle the directions array
  var i, j, dirLen = directions.length;
  var temp;
  for (i=0; i<dirLen; i++)
  {
    j = (Math.random()*100) & (dirLen-1);
    j = Math.round(j);
    temp = directions[i];
    directions[i] = directions[j];
    directions[j] = temp;
  }

  //for each possible direction that can be traveled in from this cell, recursively make a path
  // from here to there (unless the cell has already been visited).
  var d;
  for (d=0; d<dirLen; d++)
  {
    if (directions[d] == "N" && Mz[R-1][C][_V_] == false)
      __D_MP_(R-1, C, "N");
    else if (directions[d] == "S" && Mz[R+1][C][_V_] == false)
      __D_MP_(R+1, C, "S");
    else if (directions[d] == "E" && Mz[R][C+1][_V_] == false)
      __D_MP_(R, C+1, "E");
    else if (directions[d] == "W" && Mz[R][C-1][_V_] == false)
      __D_MP_(R, C-1, "W");
  }
}

/**
  Visually render the maze.
*/
function __D_GMH_()
{
  var i, j;
  //var HtmlStr = '<TABLE id="TMaze" cellspacing="0" cellpadding="0" onkeydown="Navigate()" >\n';
  var HtmlStr = '<TABLE id="_D_TM_" cellspacing="0" cellpadding="0" >\n';

  for (i=0; i<_mRows; i++)
  {
    HtmlStr += "\t<TR>\n";
    for (j=0; j<_mCols; j++)
    {
      HtmlStr += '\t\t<TD align="center" width="20" style="';

      //if we're at an outer border of the maze, draw the outside border
      if (i == 0) HtmlStr += 'border-top: 2px black solid;';
      else if (i == _mRows-1) HtmlStr += 'border-bottom: 2px black solid;';

      if (j == 0) HtmlStr += 'border-left: 2px black solid;';
      else if (j == _mCols-1) HtmlStr += 'border-right: 2px black solid;';

      //draw the walls of the cell
      if (Mz[i][j][_BW_] == 1) HtmlStr += 'border-bottom: 2px black solid;';
      if (Mz[i][j][_RW_] == 1) HtmlStr += 'border-right: 2px black solid;';

      HtmlStr += '">';

      //draw the starting and ending positions
      if (i==0 && j==0) HtmlStr += 'S';
      else if (i==_mRows-1 && j==_mCols-1) HtmlStr += 'E';
      else HtmlStr += '&nbsp;';

      HtmlStr += '</TD>\n';
    }
    HtmlStr += '\t</TR>\n';
  }

  return HtmlStr;
}

/**
  Handle user keypresses on the maze
*/
/*
function Navigate()
{
  if (_gameOver) return;

  switch (event.keyCode)
  {
    case LEFT:
      if (_userCol > 0 && Maze[_userRow][_userCol-1][RIGHTWALL] == 0)
      {
        _userCol--;
        ChangeCell('L');
      }
    break;

    case RIGHT:
      if (_userCol < _mCols-1 && Maze[_userRow][_userCol][RIGHTWALL] == 0)
      {
        _userCol++;
        ChangeCell('R');
      }
    break;

    case UP:
      if (_userRow > 0 && Maze[_userRow-1][_userCol][BOTTOMWALL] == 0)
      {
        _userRow--;
        ChangeCell('U');
      }
    break;

    case DOWN:
      if (_userRow < _mRows-1 && Maze[_userRow][_userCol][BOTTOMWALL] == 0)
      {
        _userRow++;
        ChangeCell('D');
      }
    break;
  }

  event.cancelBubble = true;
}
*/
/**
  Visually show the movement and determine if the end of the maze has been reached
*/
function __D_CC_(fromDir)
{
  var table = document.getElementById("__MD__").firstChild;

  var cell = table.rows[_userRow].cells[_userCol];

  //if moving to a new cell, change bg color to red
  if (cell.style.backgroundColor == '')
    cell.style.backgroundColor = 'red';
  else //backing up over an old cell; remove the red from the previous cell
  {
    switch (fromDir)
    {
      case 'L':
        table.rows[_userRow].cells[_userCol+1].style.backgroundColor='';
      break;

      case 'R':
        table.rows[_userRow].cells[_userCol-1].style.backgroundColor='';
      break;

      case 'U':
        table.rows[_userRow+1].cells[_userCol].style.backgroundColor='';
      break;

      case 'D':
        table.rows[_userRow-1].cells[_userCol].style.backgroundColor='';
      break;
    }
  } //else

  //determine if user is at last cell
  if (_userRow == _mRows-1 && _userCol == _mCols-1)
  {
    var i, j;
    for (i=0; i<_mRows; i++)
      for (j=0; j<_mCols; j++)
      {
        cell = table.rows[i].cells[j];
        if (cell.style.backgroundColor == 'red')
          cell.style.backgroundColor = 'blue';
      }
    _GO_ = true;
  }
}

//at each decision point, store the path.length so we know where to backup to if a dead-end is encountered
var __STK_ = new Array();

//store the row/col of each computer move
var __PTH_ = new Array();

//as each cell is visited, mark it as true so paths are only explored 1 time
var __VST_ = new Array();

//how many moves have been made
var __NM_;

/**
	Have the computer solve the maze
*/
function __D_SLV_()
{
  //setup the visited array - initially no cells visited, and the stack
  var i, j;
  for (i=0; i<_mRows; i++)
  {
    __VST_[i] = new Array();
    for (j=0; j<_mCols; j++)
    	__VST_[i][j] = false;
  }

  //programatically setup the first move (to 0,0)
  __VST_[0][0] = true; //first cell visited
  __PTH_[0] = new __D_P_(0,0); //first path
  __NM_ = 0; //0 moves have been made (1 move, 0 based)
	document.getElementById("__MD__").firstChild.rows[0].cells[0].style.backgroundColor='red';

	__D_MCM_();
}

/**
	Have the computer make a move
*/
function __D_MCM_()
{
	if (_GO_ == true) return;

	//determine which directions can be traveled in from the current position
  var directions = new Array();
  if (_userRow > 0 && Mz[_userRow-1][_userCol][_BW_] == 0 && __VST_[_userRow-1][_userCol] == false)
  	directions[directions.length] = "N";

  if (_userRow < _mRows-1 && Mz[_userRow][_userCol][_BW_] == 0 && __VST_[_userRow+1][_userCol] == false)
  	directions[directions.length] = "S";

  if (_userCol > 0 && Mz[_userRow][_userCol-1][_RW_] == 0 && __VST_[_userRow][_userCol-1] == false)
  	directions[directions.length] = "W";

  if (_userCol < _mCols-1 && Mz[_userRow][_userCol][_RW_] == 0 && __VST_[_userRow][_userCol+1] == false)
  	directions[directions.length] = "E";

  //randomly shuffle the directions array
  var i, j, dirLen = directions.length;
  var temp;
  for (i=0; i<dirLen; i++)
  {
    j = (Math.random()*100) & (dirLen-1);
    j = Math.round(j);
    temp = directions[i];
    directions[i] = directions[j];
    directions[j] = temp;
  }

	//there is somewhere to go
	if (directions.length > 0)
	{
		switch (directions[0])
		{
			case "N":
				_userRow--;
				__VST_[_userRow][_userCol] = true;
				__D_CC_("U");
			break;

			case "S":
				_userRow++;
				__VST_[_userRow][_userCol] = true;
				__D_CC_("D");
			break;

			case "E":
				_userCol++;
				__VST_[_userRow][_userCol] = true;
				__D_CC_("R");
			break;

			case "W":
				_userCol--;
				__VST_[_userRow][_userCol] = true;
				__D_CC_("L");
			break;
		}

		if (directions.length > 1)
			__STK_.push(__NM_);

		//store this move
		__NM_++;
		__PTH_[__NM_] = new __D_P_(_userRow, _userCol);

		setTimeout("__D_MCM_()", 250);
	}
	else //there is nowhere to go; backup
	{
		//remove color from current cell
		document.getElementById("__MD__").firstChild.rows[_userRow].cells[_userCol].style.backgroundColor='orange';

		__D_EP_(__STK_.pop());
	}
}

function __D_EP_(ldp)
{
	if (__NM_ > ldp)
	{
		__NM_--;

		_userRow = __PTH_[__NM_].x;
		_userCol = __PTH_[__NM_].y;

		//remove color from current cell
		if (__NM_ > ldp)
			document.getElementById("__MD__").firstChild.rows[_userRow].cells[_userCol].style.backgroundColor='orange';

		setTimeout("__D_EP_("+ldp+")", 250);
	}
	else
		setTimeout("__D_MCM_()", 250);
}

// a data container
function __D_P_(x,y)
{
	this.x = x;
	this.y = y;
}