/*
 * For the benefit of novice programmers, I've listed
 * the various bitmasks used to the best of my ability
 * (I don't use Java, I'm assuming it uses standard coordinates where 0,0 is the top left)
 * I've commented on the drawing code as well
 *
 *  1: Wall above
 *  2: Wall below
 *  4: Wall left
 *  8: Wall right
 * 16: queued to be added
 * 32: "in" the maze
 *
 *  - quin/10-24-06
 *	-	translated to Actionscript 3 by John Winkelman, 2008.08.25
 */
package {
	import flash.display.BitmapData;
	import flash.geom.Rectangle;
	import flash.geom.Point;
	
	public class MazeConstructor {
		private var mazeBitmapData:BitmapData;
		private var cellsX:Number;
		private var cellsY:Number;
		private var cellWidth:Number;
		private var cellHeight:Number;
		private var isRandom:Boolean = false;
		private var seed:Number;
		private var wallThickness:Number;
		private var hasExits:Boolean;

		private var maze:Array;		
		private var mx:Number = 0;
		private var my:Number = 0;
		private var nextCell:Number = 0;
		private var d:Number = 0;
		private var dx:Array = [ 0, 0, -1, 1 ];
		private var dy:Array = [ -1, 1, 0, 0 ];
		private var todo:Array = [];
		private var todonum:Number = 0;
		
		public function MazeConstructor() {}
		public function initMaze($mazeBitmapData:BitmapData,$cellsX:Number,$cellsY:Number,$cellWidth:Number,$cellHeight:Number,$wallThickness:Number=1,$seed:Number=0,$hasExits:Boolean=false):void {
			mazeBitmapData = $mazeBitmapData;
			cellsX = $cellsX;
			cellsY = $cellsY;
			cellWidth = $cellWidth;
			cellHeight = $cellHeight;
			wallThickness = $wallThickness;
			seed = $seed;
			hasExits = $hasExits;
			if(seed==0) isRandom = true;
			createMaze();
		}
		private function createMaze():void {
			mx = 0;
			my = 0;
			nextCell = 0;
			d = 0;
			dx = [ 0, 0, -1, 1 ];
			dy = [ -1, 1, 0, 0 ];
			todo = [];
			todonum = 0;

			/* We want to create a maze on a grid. */
			maze = [];
		
			/* We start with a grid full of walls. */
			for(mx = 0; mx < cellsX; mx++) {
				maze[mx] = [];
				for(my = 0; my < cellsY; my++) {
					if(mx == 0 || mx == cellsX-1 || my == 0 || my == cellsY-1) {
						maze[mx][my] = 32;
					} else {
						maze[mx][my] = 63;
					}
				}
			}
			/* Select any square of the grid, to start with. */

			/*	RANDOM CHECK	*/
			if(isRandom==true) {	//	start at a random cell
				mx =  (Math.floor(Math.random() * (cellsX-2)))+1;
				my =  (Math.floor(Math.random() * (cellsY-2)))+1;
			} else {	//	start at the center-most cell
				mx = Math.floor(cellsX/2);
				my = Math.floor(cellsY/2);
			}
			/*	RANDOM CHECK	*/

			/* Mark this square as connected to the maze. */
			maze[mx][my] &= ~48;

			/* Remember the surrounding squares, as we will */
			for(d = 0; d < 4; d++) {
				if((maze[mx + dx[d]][my + dy[d]] & 16) != 0) {
					todo[todonum++] = ((mx + dx[d]) << 16) | (my + dy[d]);
					maze[mx + dx[d]][my + dy[d]] &= ~16;
				}
			}
			
			// We won't be finished until all is connected. 
			while(todonum > 0) {// We select one of the squares next to the completed parts of the maze. 
				

				/*	RANDOM CHECK	*/
				if(isRandom==true) {
					nextCell = (Math.floor(Math.random() * todonum));
				} else {
					seed++;
					nextCell = seed % todonum;
				}
				/*	RANDOM CHECK	*/

				mx = todo[nextCell] >> 16; // the top 2 bytes of the data 
				my = todo[nextCell] & 65535; // the bottom 2 bytes of the data 
				// We will connect it, so remove it from the queue. 
				todo[nextCell] = todo[--todonum];
				// Select a direction, which leads to the maze. 
				do{
					/*	RANDOM CHECK	*/
					if(isRandom==true) {
						d = Math.floor(Math.random()*4);
					} else {
						seed++;
						d = seed%4;
					}
					/*	RANDOM CHECK	*/
				} while((maze[mx + dx[d]][my + dy[d]] & 32) != 0);

				// Connect this square to the maze. 
				maze[mx][my] &= ~((1 << d) | 32);
				maze[mx + dx[d]][my + dy[d]] &= ~(1 << (d ^ 1));
				
				// Remember the surrounding squares, which aren't 
				for(d = 0; d < 4; d++) {
					if((maze[mx + dx[d]][my + dy[d]] & 16) != 0) {
						// connected to the maze, and aren't yet queued to be. 
						todo[todonum++] = ((mx + dx[d]) << 16) | (my + dy[d]);
						maze[mx + dx[d]][my + dy[d]] &= ~16;
					}
				}
				// Repeat until finished.
			}

			/* One may want to add an entrance and exit. */
			if(hasExits==true) {
				maze[1][1] &= ~1; 
				maze[cellsX-2][cellsY-2] &= ~2;
			}
			
			renderMaze();
		}

		private function renderMaze():void {
			var i:int;
			var j:int;

			for(i = 1; i < cellsX-1; i++) {
				for(j = 1; j < cellsY-1; j++) {
					if((maze[i][j] & 1) != 0) {/* This cell has a top wall */
						mazeBitmapData.fillRect (new Rectangle(i * cellWidth, j * cellHeight, cellWidth+wallThickness, wallThickness),0xff000000);
					}
					if((maze[i][j] & 2) != 0) {/* This cell has a bottom wall */
						mazeBitmapData.fillRect(new Rectangle(i * cellWidth, j * cellHeight + cellHeight, cellWidth+wallThickness, wallThickness),0xff000000);
					}
					if((maze[i][j] & 4) != 0) {/* This cell has a left wall */
						mazeBitmapData.fillRect(new Rectangle(i * cellWidth, j * cellHeight, wallThickness, cellHeight+wallThickness),0xff000000);
					}
					if((maze[i][j] & 8) != 0) {/* This cell has a right wall */
						mazeBitmapData.fillRect(new Rectangle(i * cellWidth+cellWidth, j * cellHeight, wallThickness, cellHeight+wallThickness),0xff000000);
					}
				}
			}
		}
	}
}

/*
 * For the benefit of novice programmers, I've listed
 * the various bitmasks used to the best of my ability
 * (I don't use Java, I'm assuming it uses standard coordinates where 0,0 is the top left)
 * I've commented on the drawing code as well
 *
 *  1: Wall above
 *  2: Wall below
 *  4: Wall left
 *  8: Wall right
 * 16: queued to be added
 * 32: "in" the maze
 *
 *  - quin/10-24-06
 */
package {
	import flash.display.*;
	import flash.geom.*;
	import flash.events.*;
	[SWF(backgroundColor="0xffffff",width="400",height="400",frameRate="10")]
	
	public class Maze extends Sprite {
		private var maze:Array;
		private var mazeBitmapData:BitmapData;
		private var mazeBitmap:Bitmap;
		private var cellsX:Number = 50
		private var cellsY:Number = 50;
		private var cellWidth:Number = 8;
		private var cellHeight:Number = 8;
		private var debugPane:TextField;
		public function Maze() {
			addEventListener(Event.ENTER_FRAME,init);
			stage.addEventListener(MouseEvent.CLICK,init);
		}
		private function init(e:Event):void {
			if(!stage) return;
			removeEventListener(Event.ENTER_FRAME,init);
			var mx:Number = 0;
			var my:Number = 0;
			var n:Number = 0;
			var d:Number = 0;
			var dx:Array = [ 0, 0, -1, 1 ];
			var dy:Array = [ -1, 1, 0, 0 ];
			var todo:Array = [];
			var todonum:Number = 0;

			/* We want to create a maze on a grid. */
			maze = [];

			/* We start with a grid full of walls. */
			for(mx = 0; mx < cellsX; mx++) {
				maze[mx] = [];
				for(my = 0; my < cellsY; my++) {
					if(mx == 0 || mx == cellsX-1 || my == 0 || my == cellsY-1) {
						maze[mx][my] = 32;
					} else {
						maze[mx][my] = 63;
					}
				}
			}
			/* Select any square of the grid, to start with. */
			mx =  (Math.floor(Math.random() * (cellsX-2)))+1;
			my =  (Math.floor(Math.random() * (cellsY-2)))+1;
	  
			/* Mark this square as connected to the maze. */
			maze[mx][my] &= ~48;

			/* Remember the surrounding squares, as we will */
			for(d = 0; d < 4; d++) {
				if((maze[mx + dx[d]][my + dy[d]] & 16) != 0) {
					todo[todonum++] = ((mx + dx[d]) << 16) | (my + dy[d]);
					maze[mx + dx[d]][my + dy[d]] &= ~16;
				}
			}
			
			// We won't be finished until all is connected. 
			while(todonum > 0) {
				// We select one of the squares next to the maze. 
				n = (Math.floor(Math.random() * todonum));
				mx = todo[n] >> 16; // the top 2 bytes of the data 
				my = todo[n] & 65535; // the bottom 2 bytes of the data 
			// We will connect it, so remove it from the queue. 
				todo[n] = todo[--todonum];
				// Select a direction, which leads to the maze. 
				do{
					d = Math.floor(Math.random() * 4);
				} while((maze[mx + dx[d]][my + dy[d]] & 32) != 0);

				// Connect this square to the maze. 
				maze[mx][my] &= ~((1 << d) | 32);
				maze[mx + dx[d]][my + dy[d]] &= ~(1 << (d ^ 1));
				// Remember the surrounding squares, which aren't 
				for(d = 0; d < 4; d++) {
					if((maze[mx + dx[d]][my + dy[d]] & 16) != 0) {
						// connected to the maze, and aren't yet queued to be. 
						todo[todonum++] = ((mx + dx[d]) << 16) | (my + dy[d]);
						maze[mx + dx[d]][my + dy[d]] &= ~16;
					}
				}
			// Repeat until finished.
			}

			/* One may want to add an entrance and exit. */
			//maze[1][1] &= ~1; 
			//maze[cellsX-2][cellsY-2] &= ~2;
			
			mazeBitmapData = new BitmapData(400,400);			
			paint(mazeBitmapData);
		}

		public function paint(g:BitmapData):void {
			var mx:int;
			var my:int;

			for(mx = 1; mx < cellsX-1; mx++) {
				for(my = 1; my < cellsY-1; my++) {
					if((maze[mx][my] & 1) != 0) {/* This cell has a top wall */
						g.fillRect (new Rectangle(mx * cellWidth, my * cellHeight, cellWidth+1, 1),0xff000000);
					}
					if((maze[mx][my] & 2) != 0) {/* This cell has a bottom wall */
						g.fillRect(new Rectangle(mx * cellWidth, my * cellHeight + cellHeight, cellWidth+1, 1),0xff000000);
					}
					if((maze[mx][my] & 4) != 0) {/* This cell has a left wall */
						g.fillRect(new Rectangle(mx * cellWidth, my * cellHeight, 1, cellHeight+1),0xff000000);
					}
					if((maze[mx][my] & 8) != 0) {/* This cell has a right wall */
						g.fillRect(new Rectangle(mx * cellWidth+cellWidth, my * cellHeight, 1, cellHeight+1),0xff000000);
					}
				}
			}
			mazeBitmap = new Bitmap(mazeBitmapData);
			addChild(mazeBitmap);
		}
	}
}