<?php
# Maze generation script
# Authored by Ronny Cook (ronny on domain ronnycook.org) in August 2013
# For practical purposes, consider this as covered by the GNU Public Licence.
# If you want to borrow or steal the code for reasons not permitted by
# the GPL, please ask. I'll probably OK it.
#
# NOTE - the 3D stuff is done in a slab of javascript within the render3D fn.
#$render = "debug";		# "png" or "svg"
$render = "png";		# "png" or "svg"

if ($render == "debug") {
	header("content-type: text/plain");
}

if ($render == "debug") {
	print phpversion() . "\n";
}

# Seed, if any
if ($_GET["seed"]>0) {
	mt_srand($_GET["seed"]);
}

# Maze dimensions

# Horizontal dimension of maze (maximum)
$maze_x = ($_GET["maze_x"]>=2 && $_GET["maze_x"]<9999)
	  ? floor($_GET["maze_x"]) : 30;
# Vertical (north/south) dimension
$maze_y = ($_GET["maze_y"]>=2 && $_GET["maze_y"]<9999)
	  ? floor($_GET["maze_y"]) : 20;

# Maze generation parameters
# Type of maze to be generated
# hex is hexagonal
# hexpara is a parallelogram
# hexrect is a rectangle (hex grid shaped like a rectangle)
$maze_type = $_GET["maze_type"];
if ($maze_type != "hex" && $maze_type != "hexpara" && $maze_type != "hexrect") {
	$maze_type = "rectangular";
}

# Vertical (up/down) dimension - Defaults to 1
$maze_z = ($_GET["maze_z"]>=1 && $_GET["maze_z"]<9999 && $maze_type == "rectangular")
	  ? floor($_GET["maze_z"]) : 1;

# Biases are not used for now
$bias_x = 1;			# Default bias in first direction (horizontal)
$bias_y = 1;			# Bias in 2nd dimension (up/down)
$bias_z = 0;			# Bias in 3rd dimension (up/down)
$bias_d = 1;			# Bias in 3rd dimension (hex diagonal)

# Probability that cell chosen will be a run from the previous cell
$chance_run = ($_GET["chance_run"]>=0 && $_GET["chance_run"]<=1)
              ? $_GET["chance_run"] : 0.9;

# Probability that a continuous run will retain direction
$chance_straight = ($_GET["chance_straight"]>=0 && $_GET["chance_straight"]<=1)
                   ? $_GET["chance_straight"] : 0.9;

# View from above or 3D view
$maze_view = ($_GET["maze_view"]=="3D" && $maze_type=="rectangular")
             ? "3D" : "2D";

# Graphical rendering parameters
# Keep these fixed for now
$cell_x = 20;			# Height of each maze cell in pixels
$cell_y = $cell_x;		# Width of each cell in pixels
$boundary_x = 2;		# Height of dividers
$boundary_y = 2;		# Width of dividers 

$xwindow = 400;			# X and Y dimensions of 3D window
$ywindow = 400;

class Maze {
	private $type = "rectangular";
	private $x = 0;
	private $y = 0;
	private $z = 0;	# For 3D mazes in future
	private $offset = array();
	private $gates = array();
	private $available = array();
	private $mask = array();
	private $debug = 0;

	# Constructor method
	function __construct ($t, $x, $y, $z) {
		$this->mask = array(1, 2, 4, 8, 16, 32);
		if ($t == "hex" || $t == "hexrect" || $t == "hexpara") {
			$this->type = $t;
			$this->offset = array(array(1,0,0),array(-1,0,0),
			                      array(0,1,0),array(0,-1,0),
			                      array(1,1,0),array(-1,-1,0),);
			# East, west, southwest, northeast, southeast, northwest
		}
		elseif ($t == "rectangular") {
			$this->type = $t;
			$this->offset = array(array(1,0,0),array(-1,0,0),
			                      array(0,1,0),array(0,-1,0),
			                      array(0,0,1),array(0,0,-1),);
			# East, west, south, north, down, up
		}
		else {
			throw new Exception('Invalid maze type');
		}
		if ($y>0 && $y<999) {
			$this->y = $y;
		}
		else {
			throw new Exception('Invalid Y dimension');
		}
		if ($x>0 && $x<999) {
			#$this->x = $x + (substr($this->type, 0, 3) == "hex" ? $this->y : 0);
			$this->x = $x;
		}
		else {
			throw new Exception('Invalid X dimension');
		}
		if ($z>0 && $z<999) {
			$this->z = $z;
		}
		else {
			throw new Exception('Invalid Z dimension');
		}
		# Fill maze out as completely blocked
		for ($x=0; $x<$this->x; $x++) {
			for ($y=0; $y<$this->y; $y++) {
				for ($z=0; $z<$this->z; $z++) {
					# Zero = no gates open
					$this->gates[$x][$y][$z] = 0;
					$this->available[$x][$y][$z] = 1;
				}
			}
		}
		# Shape hex mazes
		# Chop off top right and bottom left of a paralellogram maze
		if ($this->type == "hex") {
			if ($this->debug) {
				print "Initialise availability for hex\n";
			}
			for ($y=0; $y<floor(($this->y-1)/2); $y++) {
				for ($x=0; $x<floor(($this->y-1)/2)-$y; $x++) {
					for ($z=0; $z<$this->z; $z++) {
						if ($this->debug) {
							print "($x,$y) Block [".($this->x-$x-1).",$y,$z]\n";
							print "Block [$x,".($this->y-$y-1).",$z]\n";
						}
						$this->available[$x][$this->y-$y-1][$z] = 0;
						$this->available[$this->x-$x-1][$y][$z] = 0;
					}
				}
			}
		}
		# Hexrect looks sort of like a standard wargame hex map
		else if ($this->type == "hexrect") {
			for ($y=2; $y<$this->y; $y++) {
				for ($x=0; $x<floor($y/2); $x++) {
					for ($z=0; $z<$this->z; $z++) {
						$this->available[$x][$y][$z] = 0;
						$this->available[$this->x-$x-1][$this->y-$y-1][$z] = 0;
					}
				}
			}
		}
		if ($this->debug) {
			for ($z=0; $z<$this->z; $z++) {
				for ($y=0; $y<$this->y; $y++) {
					for ($x=0; $x<$this->x; $x++) {
						print " " . $this->available[$x][$y][$z];
					}
					print "\n";
				}
			}
		}
	}

	function populate($bias_x, $bias_y, $bias_z, $bias_d, $chance_run, $chance_straight) {
		$bias_total = $bias_x + $bias_y + (substr($this->type, 0, 3) == "hex" ? $bias_d : 0) + $bias_z;
		# Pick a seed to start from
		$escape_check = 1000;
		do {
			$x = mt_rand(0, $this->x-1);
			$y = mt_rand(0, $this->y-1);
			$z = mt_rand(0, $this->z-1);
		} while ($this->available[$x][$y][$z]==0 && $escape_check>0);

		if ($escape_check==0) {
			throw new Exception('Could not find seed location');
		}

		# Add our seed entry to the pool and mark as unavailable.
		$this->available[$x][$y][$z] = 0;
		$poolsize = $this->x*$this->y*$this->z - 1;
		# Note - candidates is an array, each element is a 3-tuple
		# Candidate 0 is always the most recently added candidate,
		# unless it had previously been excluded
		$candidates = array(array($x, $y, $z),);
		$cand_count = 1;
		$cand = 0;
		$force_new_candidate = 0;
		$dir = -1;	# Force choice of new direction

		$offset_size = sizeof($this->offset);

		while ($cand_count>0) {
			# Pick a direction to expand
			# For now we'll ignore bias
			$dir_pool = array();
			$dir_available = 0;
			
			for ($d=0; $d<$offset_size; $d++) {
				# Figure out location of neighbour candidate
				$off_x = $candidates[$cand][0]+$this->offset[$d][0];
				$off_y = $candidates[$cand][1]+$this->offset[$d][1];
				$off_z = $candidates[$cand][2]+$this->offset[$d][2];
				# Exclude it if it's taken or outside maze
				if ($off_x>=0 && $off_x<$this->x &&
				    $off_y>=0 && $off_y<$this->y &&
				    $off_z>=0 && $off_z<$this->z &&
				    $this->available[$off_x][$off_y][$off_z]) {
					$dir_pool[$dir_available++] = $d;
				}
				else if ($d == $dir) {
					# Disable direction continuation
					# if direction is blocked
					$dir = -1;
				}
			}
			if ($dir_available == 0) {
				# No directions available, remove candidate
				$cand_count--;
				$candidates[$cand] = $candidates[$cand_count];
				$force_new_candidate = 1;
			}
			else {
				if ($this->debug>1) {
					print "Directions: [";
					for ($i=0; $i<$dir_available; $i++) {
						print " " . $dir_pool[$i];
					}
					print " ]\n";
				}
				# At this point $dir_pool contains a list
				# of open directions
				# When bias is implemented, here is where
				# we'll need to do it
				if ($dir<0 || mt_rand()/mt_getrandmax() > $chance_straight) {
					$dir = $dir_pool[mt_rand(0, $dir_available-1)];
				}
				if ($this->debug>1) {
					print "Direction $dir - offsets [ " . $this->offset[$dir][0] . ", " . $this->offset[$dir][1] . ", " . $this->offset[$dir][2] . " ] Candidate [" . $candidates[$cand][0].",".$candidates[$cand][1].",".$candidates[$cand][2]."]\n";
				}
				# Calculate location of neighbouring cell
				$off_x = $candidates[$cand][0]+$this->offset[$dir][0];
				$off_y = $candidates[$cand][1]+$this->offset[$dir][1];
				$off_z = $candidates[$cand][2]+$this->offset[$dir][2];
				if ($this->debug>1) {
					print "Offset: [$off_x, $off_y, $off_z]\n";
				}
				# Mark new cell as unavailable & reduce poolsize
				$this->available[$off_x][$off_y][$off_z] = 0;
				$poolsize--;
				# Open relevant gates in maze
				$this->gates[$candidates[$cand][0]][$candidates[$cand][1]][$candidates[$cand][2]] += $this->mask[$dir];
				# Don't forget neighbour...
				$this->gates[$off_x][$off_y][$off_z] += $this->mask[$dir^1];
				# Add new cell to candidates pool
				if ($this->debug) {
					print $candidates[$cand][0].",".$candidates[$cand][1].",".$candidates[$cand][2]."(".$this->gates[$candidates[$cand][0]][$candidates[$cand][1]][$candidates[$cand][2]].") -> $off_x,$off_y,$off_z(" . $this->gates[$off_x][$off_y][$off_z] . ")\n";
				}
				$candidates[$cand_count++] = $candidates[0];
				$candidates[0] = array($off_x, $off_y, $off_z);
				
			}
			# Pick a candidate from our connected pool for next loop
			if (mt_rand()/mt_getrandmax() < $chance_run
			    && !$force_new_candidate) {
				$cand = 0;
			}
			else {
				if ($cand_count>0) {
					$cand = mt_rand(0, $cand_count-1);
				}
				$force_new_candidate = 0;
				$dir = -1;
			}
		}
	}

	# We don't care about sqaured off ends, so we brute force it
	# PHP has a more elegant method which is probably more CPU intensive
	private function linethick($image, $x1, $y1, $x2, $y2, $colour, $xthick, $ythick) {
		for ($x=0; $x<$xthick; $x++) {
	    		for ($y=0; $y<$ythick; $y++) {
				if ($this->debug>5) {
					print "LINE FROM ".($x1+$x).",".($y1+$y)." TO ".($x2+$x).",".($y2+$y)." COLOUR ".$colour;
				}
				@imageline($image, $x1+$x, $y1+$y, $x2+$x, $y2+$y, $colour);
			}
		}
	}

	# Draw X at specified pixel location
	private function draw_x($image, $x1, $y1, $colour, $xpixel, $ypixel, $xthick, $ythick) {
		if ($this->debug) {
			print "X at $x1, $y1\n";
		}
		$scale = 4;
		$this->linethick($image, $x1-floor(($xpixel-$xthick)/$scale), $y1-floor(($ypixel-$ythick)/$scale), $x1+floor(($xpixel-$xthick)/$scale), $y1+floor(($ypixel-$ythick)/$scale), $colour, $xthick, $ythick);
		$this->linethick($image, $x1+floor(($xpixel-$xthick)/$scale), $y1-floor(($ypixel-$ythick)/$scale), $x1-floor(($xpixel-$xthick)/$scale), $y1+floor(($ypixel-$ythick)/$scale), $colour, $xthick, $ythick);
	}

	# Draw O at specified pixel location
	private function draw_o($image, $x1, $y1, $colour, $xpixel, $ypixel, $xthick, $ythick) {
		if ($this->debug) {
			print "O at $x1, $y1\n";
		}
		$scale = 4;
		$this->linethick($image, $x1-floor(($xpixel-$xthick)/$scale), $y1-floor(($ypixel-$ythick)/$scale), $x1+floor(($xpixel-$xthick)/$scale), $y1-floor(($ypixel-$ythick)/$scale), $colour, $xthick, $ythick);
		$this->linethick($image, $x1+floor(($xpixel-$xthick)/$scale), $y1-floor(($ypixel-$ythick)/$scale), $x1+floor(($xpixel-$xthick)/$scale), $y1+floor(($ypixel-$ythick)/$scale), $colour, $xthick, $ythick);
		$this->linethick($image, $x1-floor(($xpixel-$xthick)/$scale), $y1-floor(($ypixel-$ythick)/$scale), $x1-floor(($xpixel-$xthick)/$scale), $y1+floor(($ypixel-$ythick)/$scale), $colour, $xthick, $ythick);
		$this->linethick($image, $x1-floor(($xpixel-$xthick)/$scale), $y1+floor(($ypixel-$ythick)/$scale), $x1+floor(($xpixel-$xthick)/$scale), $y1+floor(($ypixel-$ythick)/$scale), $colour, $xthick, $ythick);
	}

	# Render view of maze from above
	function render($xpixel, $ypixel, $boundary_x, $boundary_y, $zlayer) {
		# Create blank canvas (all gates blocked)
		if ($this->type == "rectangular") {
			# Create image
			$im = @imagecreate(($xpixel+$boundary_x)*$this->x + $boundary_x, ($ypixel+$boundary_y)*$this->y + $boundary_y);
			# Assign colours (white back, black fore)
			$back = @imagecolorallocate($im, 255, 255, 255);
			$front = @imagecolorallocate($im, 0, 0, 0);
			# Backfill with white
			@imagefilledrectangle( $im, 0, 0, ($xpixel+$boundary_x)*$this->x + $boundary_x -1, ($ypixel+$boundary_y)*$this->y + $boundary_y - 1, $back);
			# Fill left and top borders
			@imagefilledrectangle( $im, 0, 0, ($xpixel+$boundary_x)*$this->x + $boundary_x - 1, $boundary_y-1, $front);
			@imagefilledrectangle( $im, 0, 0, $boundary_x-1, ($ypixel+$boundary_y)*$this->y + $boundary_y - 1, $front);
			# Could do X + Y in one run, but splitting up allows
			# for efficiencies to be introduced later
			# Fill horizontal gates
			for ($y=0; $y<$this->y; $y++) {
				for ($x=0; $x<$this->x; $x++) {
					if ((($this->gates[$x][$y][$zlayer])&($this->mask[2]))==0) {
						@imagefilledrectangle( $im, ($xpixel+$boundary_x)*$x, ($ypixel+$boundary_y)*($y+1), ($xpixel+$boundary_x)*($x+1)+$boundary_x-1, ($ypixel+$boundary_y)*($y+1)+$boundary_y-1, $front);
					}
				}
			}
			# Fill vertical gates
			for ($x=0; $x<$this->x; $x++) {
				for ($y=0; $y<$this->y; $y++) {
					if ((($this->gates[$x][$y][$zlayer])&($this->mask[0]))==0) {
						@imagefilledrectangle( $im, ($xpixel+$boundary_x)*($x+1), ($ypixel+$boundary_y)*($y), ($xpixel+$boundary_x)*($x+1)+$boundary_x-1, ($ypixel+$boundary_y)*($y+1)+$boundary_y-1, $front);
					}
				}
			}
			$this->draw_x($im, $boundary_x+floor($xpixel/2), $boundary_y+floor($ypixel/2), $front, $xpixel, $ypixel, $boundary_x, $boundary_y);
			$this->draw_o($im, ($boundary_x+$xpixel)*($this->x-1)+floor($xpixel/2), ($boundary_y+$ypixel)*($this->y-1)+floor($ypixel/2), $front, $xpixel, $ypixel, $boundary_x, $boundary_y);
			return $im;
		}
		else {
			if ($this->debug) {
				print "Create hex image : size ".(($xpixel+$boundary_x)*($this->x+floor(($this->y+1)/2)) + $boundary_x).",".(($ypixel+$boundary_y)*$this->y + $boundary_y)."\n";
			}
			# Create image
			$im1 = @imagecreate(($xpixel+$boundary_x)*($this->x+floor(($this->y+1)/2)) + $boundary_x, ($ypixel+$boundary_y)*$this->y + $boundary_y);
			# Assign colours (white back, black fore)
			$back = @imagecolorallocate($im1, 255, 255, 255);
			$front = @imagecolorallocate($im1, 0, 0, 0);
			# Create array with relative locations of hex vertices
			# Top
			$x1 = floor(($xpixel+$boundary_x)/2); $y1 = 0;
			# Bottom
			$x2 = floor(($xpixel+$boundary_x)/2); $y2 = $ypixel+$boundary_y;
			# Northwest
			$x3 = 0; $y3 = floor(($ypixel+$boundary_y)/3);
			# Southeast
			$x4 = $xpixel+$boundary_x; $y4 = $ypixel+$boundary_y - floor(($ypixel+$boundary_y)/3);
			# Southwest
			$x5 = 0; $y5 = $ypixel+$boundary_y - floor(($ypixel+$boundary_y)/3);
			# Northeast
			$x6 = $xpixel+$boundary_x; $y6 = floor(($ypixel+$boundary_y)/3);
			# Backfill with white
			@imagefilledrectangle( $im1, 0, 0, ($this->x+floor(($this->y+1)/2)) + $boundary_x -1, ($ypixel+$boundary_y)*$this->y + $boundary_y - 1, $back);
			# Don't fill borders as border locations vary
			# East, west, southwest, northeast, southeast, northwest
			# 0@4-6 1@3-5 2@5-2      3@1-6      4@2-4      5@1-3
			
			$xmin = 1000000; $xmax = 0;
			for ($y=0; $y<$this->y; $y++) {
				for ($x=0; $x<$this->x; $x++) {
					if ($this->gates[$x][$y][$zlayer]==0) {
						continue;
					}
					$xbase = floor(($xpixel+$boundary_x)*($x+($this->y-$y)/2));
					$xmin = min($xbase, $xmin);
					$xmax = max($xbase+$x4+$boundary_x, $xmax);
					$ybase = ($ypixel+$boundary_y - floor(($ypixel+$boundary_y)/3))*$y;
					if ($this->debug > 2) {
						print "Render hex ($x,$y) at ($xbase,$ybase)\n";
					}
					if ((($this->gates[$x][$y][$zlayer])&($this->mask[0]))==0) {
						@$this->linethick( $im1, $xbase+$x4, $ybase+$y4, $xbase+$x6, $ybase+$y6, $front, $boundary_x, $boundary_y);
					}
					if ((($this->gates[$x][$y][$zlayer])&($this->mask[1]))==0) {
						@$this->linethick( $im1, $xbase+$x3, $ybase+$y3, $xbase+$x5, $ybase+$y5, $front, $boundary_x, $boundary_y);
					}
					if ((($this->gates[$x][$y][$zlayer])&($this->mask[2]))==0) {
						@$this->linethick( $im1, $xbase+$x5, $ybase+$y5, $xbase+$x2, $ybase+$y2, $front, $boundary_x, $boundary_y);
					}
					if ((($this->gates[$x][$y][$zlayer])&($this->mask[3]))==0) {
						@$this->linethick( $im1, $xbase+$x1, $ybase+$y1, $xbase+$x6, $ybase+$y6, $front, $boundary_x, $boundary_y);
					}
					if ((($this->gates[$x][$y][$zlayer])&($this->mask[4]))==0) {
						@$this->linethick( $im1, $xbase+$x4, $ybase+$y4, $xbase+$x2, $ybase+$y2, $front, $boundary_x, $boundary_y);
					}
					if ((($this->gates[$x][$y][$zlayer])&($this->mask[5]))==0) {
						@$this->linethick( $im1, $xbase+$x1, $ybase+$y1, $xbase+$x3, $ybase+$y3, $front, $boundary_x, $boundary_y);
					}
				}
			}
			$this->draw_x($im1, floor(($xpixel+$boundary_x)*($this->y+1)/2), $boundary_y+floor($ypixel/2), $front, $xpixel, $ypixel, $boundary_x, $boundary_y);
			$this->draw_o($im1, $xbase+$boundary_x+floor($xpixel/2), $ybase+$boundary_y+floor($ypixel/2), $front, $xpixel, $ypixel, $boundary_x, $boundary_y);
			# Crop image
			$im = imagecreatetruecolor($xmax-$xmin+1, ($ypixel+$boundary_y - floor(($ypixel+$boundary_y)/3))*($this->y+1));
			imagecopy($im, $im1, 0, 0, $xmin, 0, $xmax-$xmin+1,  ($ypixel+$boundary_y - floor(($ypixel+$boundary_y)/3))*($this->y+1));
			imagedestroy($im1);
			return $im;
		}
	}

	# 3D view of maze - to be implemented later
	function render3D($xwindow, $ywindow, $x, $y, $z, $direction) {
		header("content-type: text/html" );
?>
		<!DOCTYPE html>
		<HTML>
		<HEAD><TITLE>3D Maze view</TITLE>
		</HEAD>
		<BODY>
		<CENTER>
		<TABLE BORDER=0>
		<TR>
<?php
if ($this->z==1) {
?>
		<TD style="width:20%"></TD>
<?php
}
?>
		<TD style="width:20%;text-align:left"><button id="TurnLeft" onclick="turn(1);">Turn Left</button></TD>
		<TD style="width:20%;text-align:CENTER"><button id="MoveForward" onclick="move_forward();">Move Forward</button></TD>
		<TD style="width:20%;text-align:RIGHT"><button id="TurnRight" onclick="turn(2);">Turn Right</button></TD>
		<TD style="width:20%"></TD>
<?php
if ($this->z>1) {
?>
		<TD style="width:20%;text-align:CENTER"><button id="TurnUp" onclick="turn(3);">Turn Up</button></TD>
<?php
}
?>
		</TR>
		<TR>
<?php
if ($this->z==1) {
?>
		<TD style="width:20%"></TD>
<?php
}
?>
		<TD style="width:20%;text-align:LEFT"><button id="MoveLeft" onclick="move_left();">Move Left</button></TD>
		<TD style="width:20%;text-align:CENTER"><button id="MoveBack" onclick="move_back();">Move Back</button></TD>
		<TD style="width:20%;text-align:RIGHT"><button id="MoveRight" onclick="move_right();">Move Right</button></TD>
		<TD style="width:20%"></TD>
<?php
if ($this->z>1) {
?>
		<TD style="width:20%;text-align:CENTER"><button id="TurnDown" onclick="turn(4);">Turn Down</button></TD>
<?php
}
?>
		</TR>
		</TABLE>
		<DIV style="width:100%;text-align:CENTER" id="status">Status</div>
<?php
print "<canvas id=\"3dview\" width=\"$xwindow\" height=\"$ywindow\"></canvas>\n"
?>
		</CENTER>
		<script>
		var offsets = new Array();
		offsets = [[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,1],[0,0,-1]];
			//X, Y, Z offsets for East, west, south, north, down, up
		var turns = new Array();
		// 24 possible orientations. Values in array represent:
		// - The baseline direction you are facing
		// - The orientation you get if you turn left
		// - The orientation you get if you turn right
		// - The orientation you get if you turn up
		// - The orientation you get if you turn down
		turns = [[0,3,2,5,4],		//  0 East, up=up
			 [1,2,3,11,10],		//  1 West, up=up
			 [2,0,1,17,16],		//  2 South, up=up
			 [3,1,0,23,22],		//  3 North, up=up
			 [4,15,14,0,7],		//  4 Down, up=E
			 [5,21,20,7,0],		//  5 Up, up=W
			 [0,8,9,10,11],		//  6 East, up=down
			 [1,9,8,4,5],		//  7 West, up=down
			 [2,7,6,22,23],		//  8 South, up=down
			 [3,6,7,16,17],		//  9 North, up=down
			 [4,20,21,1,6],		// 10 Down, up=W
			 [5,14,15,6,1],		// 11 Up, up=E
			 [0,22,17,21,14],	// 12 East, up=N
			 [1,17,22,15,20],	// 13 West, up=N
			 [2,4,11,12,19],	// 14 South, up=E
			 [3,11,4,18,13],	// 15 North, up=E
			 [4,18,19,2,9],		// 16 Down, up=S
			 [5,12,13,9,2],		// 17 Up, up=N
			 [0,23,16,20,15],	// 18 East, up=S
			 [1,16,23,14,21],	// 19 West, up=S
			 [2,5,10,13,18],	// 20 South, up=W
			 [3,10,5,19,12],	// 21 North, up=W
			 [4,13,12,3,8],		// 22 Down, up=N
			 [5,19,18,8,3]		// 23 Up, up=S
			];

		// Masks against wall info
		var mask = new Array();
		mask = [1, 2, 4, 8, 16, 32];

		// Initialise location and facing
<?php
		print "var x = $x;\n";
		print "var y = $y;\n";
		print "var z = $z;\n";
		print "var facing = $direction;\n\n";
		print "var xg = ".(mt_rand(0, $this->x-1)).";\n";
		print "var yg = ".(mt_rand(0, $this->y-1)).";\n";
		print "var zg = ".(mt_rand(0, $this->z-1)).";\n";

?>

		var gates = new Array();
		gates = [
<?php
		for ($x=0; $x<$this->x; $x++) {
			if ($x>0) {print ",";}
			print "[";
			for ($y=0; $y<$this->y; $y++) {
				if ($y>0) {print ",";}
				print "[";
				for ($z=0; $z<$this->z; $z++) {
					if ($z>0) {print ",";}
					print $this->gates[$x][$y][$z];
				}
				print "]";
			}
			print "]\n";
		}
?>
		];


		// This array is used to generate the offsets for the
		// perspective view
		var viewoff = new Array();
		viewoff[0] = 0;
		viewoff[1] = 0.1;
		for (var i=3; i<20; i+=2) {
			viewoff[i] = 1-((1-viewoff[i-2])*0.5);
			viewoff[i-1] = viewoff[i-2]*0.55+viewoff[i]*0.45;
		}

		function draw3d() {
			var canvas = document.getElementById("3dview");
			var c = canvas.getContext('2d');
			// Colours for each direction of wall
			var colours = [ "#811","#188","#181","#818","#444","#BBB" ];
			var w = window.innerWidth * 0.8;
			var h = window.innerHeight * 0.8;
			
			if (w<h) { h = w; } else { w = h ; }

			c.canvas.width = w;
			c.canvas.height = h;

			// We recalculate each time in case window resized

			var xs = x;
			var ys = y;
			var zs = z;

			var done = 0;
			var goal_radius = 0;

			// console.debug(facing);
			// Loop up to 8 steps away
			for (var d=0; d<8 && !done; d++) {
				var c1, c2, c3;
				// Fill in wall to our immediate left
				if (gates[xs][ys][zs] & mask[turns[turns[facing][1]][0]]) {
					// Main left block is "ahead"
					c.fillStyle = colours[turns[facing][0]];
					c.beginPath();
					// c.fillRect(w*viewoff[d*2]/2, h*viewoff[d*2+1]/2, w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]);
					c.moveTo(w*viewoff[d*2]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
					// Top kitty corner is "up"
					c.fillStyle = colours[turns[turns[facing][3]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2]/2, h*viewoff[d*2]/2);
					c.lineTo(w*viewoff[d*2]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
					// Bottom kitty corner is "down"
					c.fillStyle = colours[turns[turns[facing][4]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w*viewoff[d*2]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.fill();
				}
				else {
					// Wall filled, all "left" colour
					c.fillStyle = colours[turns[turns[facing][1]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2]/2, h*viewoff[d*2]/2);
					c.lineTo(w*viewoff[d*2]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
				}

				// Fill in wall to our immediate right
				if (gates[xs][ys][zs] & mask[turns[turns[facing][2]][0]]) {
					// Main right block is "ahead"
					c.fillStyle = colours[turns[facing][0]];
					c.beginPath();
					// c.fillRect(w*viewoff[d*2]/2, h*viewoff[d*2+1]/2, w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]);
					c.moveTo(w-w*viewoff[d*2]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
					// Top kitty corner is "up"
					c.fillStyle = colours[turns[turns[facing][3]][0]];
					c.beginPath();
					c.moveTo(w-w*viewoff[d*2]/2, h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
					// Bottom kitty corner is "down"
					c.fillStyle = colours[turns[turns[facing][4]][0]];
					c.beginPath();
					c.moveTo(w-w*viewoff[d*2]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.fill();
				}
				else {
					// Wall filled, all "right" colour
					c.fillStyle = colours[turns[turns[facing][2]][0]];
					c.beginPath();
					c.moveTo(w-w*viewoff[d*2]/2, h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
				}

				// Fill in wall above us
				if (gates[xs][ys][zs] & mask[turns[turns[facing][3]][0]]) {
					// Main upper block is "ahead"
					c.fillStyle = colours[turns[facing][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2+1]/2, h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
					// left kitty corner is "left"
					c.fillStyle = colours[turns[turns[facing][1]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2]/2, h*viewoff[d*2]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h*viewoff[d*2]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
					// Right kitty corner is "right"
					c.fillStyle = colours[turns[turns[facing][2]][0]];
					c.beginPath();
					c.moveTo(w-w*viewoff[d*2]/2, h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
				}
				else {
					// Wall filled, all "up" colour
					c.fillStyle = colours[turns[turns[facing][3]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2]/2, h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2]/2, h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.fill();
				}

				// Fill in wall below us
				if (gates[xs][ys][zs] & mask[turns[turns[facing][4]][0]]) {
					// Main upper block is "ahead"
					c.fillStyle = colours[turns[facing][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.fill();
					// left kitty corner is "left"
					c.fillStyle = colours[turns[turns[facing][1]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.fill();
					// Right kitty corner is "right"
					c.fillStyle = colours[turns[turns[facing][2]][0]];
					c.beginPath();
					c.moveTo(w-w*viewoff[d*2]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.fill();
				}
				else {
					// Wall filled, all "down" colour
					c.fillStyle = colours[turns[turns[facing][4]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2]/2, h-h*viewoff[d*2]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.fill();
				}

				if ((gates[xs][ys][zs] & mask[turns[facing][0]])==0) {
					// Direction ahead is blocked
					c.fillStyle = colours[turns[facing][0]];
					c.fillRect(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2, w-w*viewoff[d*2+1], h-h*viewoff[d*2+1]);
					done=1;
				}
				else {
					// Fill in details for walls immediately ahead
					// Wall left and ahead
					c.fillStyle = colours[turns[turns[facing][1]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w*viewoff[d*2+2]/2, h-h*viewoff[d*2+2]/2);
					c.lineTo(w*viewoff[d*2+2]/2, h*viewoff[d*2+2]/2);
					c.fill();
					// Wall right and ahead
					c.fillStyle = colours[turns[turns[facing][2]][0]];
					c.beginPath();
					c.moveTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+2]/2, h-h*viewoff[d*2+2]/2);
					c.lineTo(w-w*viewoff[d*2+2]/2, h*viewoff[d*2+2]/2);
					c.fill();
					// Wall up and ahead
					c.fillStyle = colours[turns[turns[facing][3]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+2]/2, h*viewoff[d*2+2]/2);
					c.lineTo(w*viewoff[d*2+2]/2, h*viewoff[d*2+2]/2);
					c.fill();
					// Wall down and ahead
					c.fillStyle = colours[turns[turns[facing][4]][0]];
					c.beginPath();
					c.moveTo(w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+1]/2, h-h*viewoff[d*2+1]/2);
					c.lineTo(w-w*viewoff[d*2+2]/2, h-h*viewoff[d*2+2]/2);
					c.lineTo(w*viewoff[d*2+2]/2, h-h*viewoff[d*2+2]/2);
					c.fill();
				}
				if (xs==xg && ys==yg && zs==zg) {
					goal_radius = w*(1-viewoff[d*2+1])/2;

				}
				// Move our virtual viewpoint forward 1
				xs += offsets[turns[facing][0]][0];
				ys += offsets[turns[facing][0]][1];
				zs += offsets[turns[facing][0]][2];
			}
			if (goal_radius > 0) {
				var goalfill = c.createRadialGradient(w/2,h/2,0, w/2, h/2, goal_radius);
				goalfill.addColorStop(0.0, "transparent");
				goalfill.addColorStop(0.3, "rgba(100,0,0,1)");
				goalfill.addColorStop(0.7, "rgba(100,100,0,1)");
				goalfill.addColorStop(1, "rgba(0,0,100,1)");
				c.fillStyle = goalfill;
				c.beginPath();
				c.arc(w/2,h/2,goal_radius, 0, Math.PI*2, false);
				c.closePath();
				c.fill();
			}
			var statusreport = "Location: ("+x+","+y+","+z+")    Goal: ("+xg+","+yg+","+zg+")";
			if (x==xg && y==yg && z==zg) {
				statusreport = "*** YOU ARE AT THE GOAL ***";
			}
			document.getElementById('status').innerHTML = statusreport;
		}

		function turn(direction)
		{
			facing = turns[facing][direction];
			draw3d();
		}

		function move_forward()
		{
			if (gates[x][y][z] & mask[turns[facing][0]]) {
				x += offsets[turns[facing][0]][0];
				y += offsets[turns[facing][0]][1];
				z += offsets[turns[facing][0]][2];
				draw3d();
			}
		}

		function move_back()
		{
			// This works because directions are paired opposites
			if (gates[x][y][z] & mask[1^turns[facing][0]]) {
				x -= offsets[turns[facing][0]][0];
				y -= offsets[turns[facing][0]][1];
				z -= offsets[turns[facing][0]][2];
				draw3d();
			}
		}

		function move_left()
		{
			if (gates[x][y][z] & mask[turns[turns[facing][1]][0]]) {
				x += offsets[turns[turns[facing][1]][0]][0];
				y += offsets[turns[turns[facing][1]][0]][1];
				z += offsets[turns[turns[facing][1]][0]][2];
				draw3d();
			}
		}

		function move_right()
		{
			if (gates[x][y][z] & mask[turns[turns[facing][2]][0]]) {
				x += offsets[turns[turns[facing][2]][0]][0];
				y += offsets[turns[turns[facing][2]][0]][1];
				z += offsets[turns[turns[facing][2]][0]][2];
				draw3d();
			}
		}

		draw3d();

		</script>
		</BODY>
		</HTML>
		<?php
	}
}

$maze = new Maze($maze_type, $maze_x, $maze_y, $maze_z);
$maze->populate($bias_x, $bias_y, $bias_z, $bias_d, $chance_run, $chance_straight);

if ($maze_view == "2D") {
	try {
		$maze_image = $maze->render($cell_x, $cell_y, $boundary_x, $boundary_y, 0);
		header("content-type: image/png" );
		imagepng($maze_image);
		imagedestroy($maze_image);
	} catch (Exception $e) {
		header("content-type: text/plain" );
		echo 'Caught exception: ', $e->getMessage(), "\n";
	}
}
else {
	$maze->render3D($xwindow, $ywindow, mt_rand(0, $maze_x-1), mt_rand(0, $maze_y-1), mt_rand(0, $maze_z-1), mt_rand(0, $maze_z>1 ? 23 : 3));
}

?>