package {
	import flash.display.Sprite;
	import flash.display.SimpleButton;
	import flash.events.MouseEvent;
	import flash.geom.Point;
	import flash.text.TextField;
	import flash.utils.getTimer;
	
	
	public class Main extends Sprite {
		
		const COLS 	= 37;
		const ROWS 	= 37;
		const SIZE 	= 10;
		const END	= COLS*int(ROWS/2)-2;
		const ENDX	= COLS-2;
		const ENDY	= int(ROWS/2);
		
		var map 		: Array;
		var mapSprite 	: Sprite;
		var pathSprite	: Sprite;
		
		
		public function Main() : void {
			
			map = new Array(COLS);
			for (var i = 0; i < COLS; i++) {
				map[i] = new Array(ROWS);
				for (var j = 0; j < ROWS; j++)
					map[i][j] = i != 0 && j != 0 && i != COLS-1 && j != ROWS-1; //create 1-tile border
			}
			
			pathSprite = new Sprite();
			pathSprite.x = SIZE/2;
			pathSprite.y = SIZE/2;
			pathSprite.mouseEnabled = false;
			
			mapSprite = new Sprite();
			mapSprite.x = 1-SIZE;
			mapSprite.y = 1-SIZE;
			mapSprite.graphics.lineStyle(0, 0x000000);
			mapSprite.graphics.beginFill(0xFFFFFF);
			mapSprite.graphics.drawRect(SIZE-1, SIZE-1, (COLS-2)*SIZE+1, (ROWS-2)*SIZE+1);
			mapSprite.graphics.endFill();
			mapSprite.graphics.lineStyle();
			mapSprite.graphics.beginFill(0x00FF00);
			mapSprite.graphics.drawRect(ENDX*SIZE, ENDY*SIZE, SIZE, SIZE);
			mapSprite.graphics.endFill();
			
			mapSprite.addEventListener(MouseEvent.MOUSE_DOWN, drawTile);
			mapSprite.addEventListener(MouseEvent.MOUSE_MOVE, drawTile);
			mapSprite.addChild(pathSprite);
			
			findPathButton.addEventListener(MouseEvent.CLICK, findPath);
			
			addChild(mapSprite);
			
		}
		
		private function drawTile(e : MouseEvent) : void {
			if (!e.buttonDown) return;
			
			var px = int(e.localX/SIZE);
			var py = int(e.localY/SIZE);
			
			if (px >= COLS-1 || py >= ROWS-1 || py*COLS+px == END) return;
			
			var color : int
			if (e.ctrlKey) {
				color = 0xFFFFFF;
				map[px][py] = true;
			} else {
				color = 0x999999;
				map[px][py] = false;
			}
			
			mapSprite.graphics.lineStyle();
			mapSprite.graphics.beginFill(color);
			mapSprite.graphics.drawRect(px * SIZE, py * SIZE, SIZE, SIZE);
			mapSprite.graphics.endFill();
		}
		
		private function drawArrow(p1 : Point, p2 : Point) : void {
			pathSprite.graphics.lineStyle(1, 0xFF0000);
			
			pathSprite.graphics.moveTo(p1.x, p1.y);
			pathSprite.graphics.lineTo(p2.x, p2.y);
			
			var m = Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
			var u = new Point(3*(p1.x - p2.x)/m, 3*(p1.y - p2.y)/m);
			
			var sx = p1.x + (p2.x - p1.x)/1.5;
			var sy = p1.y + (p2.y - p1.y)/1.5;
			
			pathSprite.graphics.moveTo(sx, sy);
			pathSprite.graphics.lineTo(sx + u.x*0.866 - u.y/2, sy + u.x/2 + u.y*0.866);
			
			pathSprite.graphics.moveTo(sx, sy);
			pathSprite.graphics.lineTo(sx + u.x*0.866 + u.y/2, sy - u.x/2 + u.y*0.866);
		}
		
		private function drawPaths(paths : Array) : void {
			pathSprite.graphics.clear();
			for (var i = 0; i < COLS; i++)
				for (var j = 0; j < ROWS; j++) 
					if (map[i][j] && paths[i][j]) 
						drawArrow(new Point(i*SIZE, j*SIZE), new Point(paths[i][j].x*SIZE, paths[i][j].y*SIZE));
		}
		
		private function relax(p1 : Point, p2 : Point, p3 : Point) : Point {
			if (p2.x == ENDX && p2.y == ENDY) return p2;
			var dx = p3.x - p1.x;
			var dy = p3.y - p1.y;
			if (dx == 0 || dy == 0) return p2;
			
			dx /= Math.abs(dx);
			dy /= Math.abs(dy);
			
			var nx = p1.x + dx*Math.abs(p2.y - p1.y);
			var ny = p1.y + dy*Math.abs(p2.x - p1.x);

			if (map[nx][ny]) return new Point(p1.x + dx, p1.y + dy);
			return p2;
		}
		
		private function findPath(e : MouseEvent) : Array {
			var t = getTimer();
			
			const DX = [1, -1, 0, 0];
			const DY = [0, 0, 1, -1];
			
			var queue = new Array((COLS-2)*(ROWS-2));
			var head, tail : int
			head = tail = 0;
			
			var node : Point;
			var paths : Array = new Array(COLS);
			for (var i = 0; i < COLS; i++) paths[i] = new Array(ROWS);
			
			node = new Point(ENDX, ENDY);
			
			do {
				for (i = 0; i < 4; i++) {
					if (!paths[node.x+DX[i]][node.y+DY[i]] && map[node.x+DX[i]][node.y+DY[i]]) {
						queue[tail++] = new Point(node.x + DX[i], node.y + DY[i]);
						if (e.ctrlKey) {paths[node.x+DX[i]][node.y+DY[i]] = relax(new Point(node.x+DX[i], node.y+DY[i]), node, paths[node.x][node.y]);
						else paths[node.x+DX[i]][node.y+DY[i]] = node;
					}
				}
				node = queue[head++];
			} while(tail != head);
			
			timeTextBox.text = "Time: " + (getTimer() - t) + "ms";
			
			drawPaths(paths);
			return paths;
		}
		
	}
	
}