// jsmaze.js
// Copyright 2006 Dave Laplander 
// dlaplander@gmail.com 
// http://del.typepad.com/

// Defines a class for a maze cell

// Constructor for the MazeCell
function MazeCell(x,y)
{
	// Set the initial state for this cell
	this.twall = true;
	this.bwall = true;
	this.lwall = true;
	this.rwall = true;
	this.visited = false;
	this.x = x;
	this.y = y;
}

// Visited method
MazeCell.prototype.Visited = function()
{
	return this.visited;
}

MazeCell.prototype.Visit = function()
{
	this.visited = true;
}

MazeCell.prototype.HasWall = function(d)
{
	// Return the status of a specific wall
	switch (d)
	{
		case "t":
			return this.twall;
			break;
		case "l":
			return this.lwall;
			break;
		case "b":
			return this.bwall;
			break;
		case "r":
			return this.rwall;
			break;
	}
}

// Constructor for a Coordinate class
function Coordinate(x,y)
{
	this.x = x;
	this.y = y;
}

// Shuffles an array and returns the shuffled array
function ShuffleArray(arr)
{
	// Make a copy of the input array so we don't modify the original
	var tArray = new Array();	
	for (var n=0; n < arr.length; n++) 
		tArray.push(arr[n]);
	
	var shuffledArray = new Array();
	
	// Pull random elements out of tArray and add to shuffledArray until tArray is empty
	while ( tArray.length > 0 )
	{
		var len = tArray.length;
		var ran = Math.round( Math.random() * (len-1) );
		shuffledArray.push( tArray.splice(ran,1)[0] );
	}
	
	// Return shuffled array
	return shuffledArray;
}

// Returns a dimx x dimy multidimmensional array of MazeCell objects.
function InitMaze(dimx, dimy)
{
	// Initialize the array of arrays
	var t = new Array(dimx);
	var i;
	for (i=0; i < dimx; i++)
	{
		t[i] = new Array(dimy);
	}
	
	for (i=0; i < dimx; i++)
	{
		var j;
		for (j=0; j < dimy; j++)
		{
			t[i][j] = new MazeCell(i, j);
		}
	}
	
	return t;
}

// Returns true if cell (x,y) in maze m has already been visited, otherwise false
function AlreadyVisited(m, x, y)
{
	return m[x][y].Visited();
}

// Returns an array of coordinates (column,row) near (x,y) in maze m that we have not visited yet.
function FindValidCells(m, x,y)
{
	var valid_cells = new Array();
	
	// Above?
	if ( (y-1) >= 0 && m[x][y-1].Visited() == false )
		{
			valid_cells.push( new Coordinate(x, y-1) );
		}
		
	// Below?
	if ( (y+1) < m[0].length && m[x][y+1].Visited() == false )
		valid_cells.push( new Coordinate(x, (y+1)) );
		
	// Right?
	if ( (x+1) < m.length && m[x+1][y].Visited() == false )
		valid_cells.push( new Coordinate((x+1), y) ); 
		
	// Left?
	if ( (x-1) >= 0 && m[x-1][y].Visited() == false )
		valid_cells.push( new Coordinate((x-1), y) );
		
	return valid_cells;
}

// Knocks down the walls between two cells specified by (x1,y1) and (x2,y2) in maze m. Returns
// true wether it works or not.
function KnockDownWall(m, x1,y1, x2,y2)
{

	if (x2 > x1)
	{
		// cell2 is to the right cell1
		m[x1][y1].rwall = false;
		m[x2][y2].lwall = false;
	}
	else if (x2 < x1)
	{
		// cell2 is to the left of cell1
		m[x1][y1].lwall = false;
		m[x2][y2].rwall = false;
	}
	else if (y2 < y1)
	{
		// cell2 is above cell1
		m[x1][y1].twall = false;
		m[x2][y2].bwall = false;
	}
	else if (y2 > y1)
	{
		// cell2 is below cell1
		m[x1][y1].bwall = false;
		m[x2][y2].twall = false;
	}
	
	return true;
}

// Carves out a "perfect" maze using the recursive backtracker algorithm. Returns the maze.

function CarveMaze(m, x1,y1, x2,y2)
{	
	// If we've been here before then bail
	if ( AlreadyVisited(m, x1,y1) == true )
		return m;
		
	// Knock out the wall between us and the previous cell
	KnockDownWall(m, x1,y1, x2,y2);
	
	// Tag current cell as visited
	m[x1][y1].Visit();
	
	// Recurse down into all available neighbor cells
	var cells = ShuffleArray( FindValidCells(m, x1,y1) );
	for ( var n=0; n < cells.length; n++ )
	{
		if ( AlreadyVisited(m, cells[n].x, cells[n].y) == false )
		{
			m = CarveMaze(m, cells[n].x, cells[n].y, x1, y1);
		}
	}
	
	return m;
}

// Returns an <img src="..." /> tage for a given maze cell
function ImageTag(m, x, y)
{
	var img = "";
	
	if ( m[x][y].twall == true )
		{ img = img + "t"; }
	
	if ( m[x][y].bwall == true )
		{ img = img + "b"; }
	
	if ( m[x][y].lwall == true )
		{ img = img + "l"; }
	
	if ( m[x][y].rwall == true )
		{ img = img + "r"; }
	
	if ( img == "" )
		{ return '<img src="maze_images/none.gif" />'; }
	else
		{ return '<img src="maze_images/' + img + '.gif" width="8" height="8" />'; }
}

// Returns a <table> with the maze inside
function PrintMaze(m)
{
	var t = ""
	
	t = '<table border="0" cellspacing="0" cellpadding="0">';
	
	for (var r=0; r < m[0].length; r++)
	{
		t += "<tr>";
		
		for (var c = 0; c < m.length; c++)
		{
			t += '<td height="8" width="8" id="c' + c + 'x' + r + '">';
			t += ImageTag(m, c, r);
			t += "</td>";
		}
		t += "</tr>";
	}
	
	t += "</table>";
	
	return t;
}