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;
		
		var map 		: Array;
		var mapSprite 	: Sprite;
		var pathSprite	: Sprite;
		
		
		public function Main() : void {
			
			map = new Array(COLS * ROWS);
			for (var i = 0; i < map.length; i++) map[i] = i >= COLS && i < ROWS*(COLS-1) && i%COLS != 0 && i%COLS != COLS-1;
			
			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((END%COLS)*SIZE, int(END/COLS)*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[py*COLS+px] = true;
			} else {
				color = 0x999999;
				map[py*COLS+px] = 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*ROWS; i++) {
				if (map[i] && paths[i]) drawArrow(new Point((i%COLS)*SIZE, int(i/COLS)*SIZE), new Point((paths[i]%COLS)*SIZE, int(paths[i]/COLS)*SIZE));
			}
		}
		
		private function relax(p1 : int, p2 : int, p3 : int) : int {
			if (p2 == END) return p2;
			var p1x = p1%COLS;
			var p1y = int(p1/COLS);
			var dx = p3%COLS - p1x;
			var dy = int(p3/COLS) - p1y;
			if (!dx || !dy) return p2;
			dx = dx > 0 ? 1 : -1;
			dy = dy > 0 ? 1 : -1;
			
			var nx = p1x + dx*Math.abs(int(p2/COLS) - p1y);
			var ny = p1y + dy*Math.abs(p2%COLS - p1x);
			
			if (map[ny*COLS + nx]) return (p1y + dy)*COLS + p1x + dx;
			return p2;
		}
		
		private function findPath(e : MouseEvent) : void {
			var t = getTimer();
			
			const DX = [1, -1, 0, 0];
			const DY = [0, 0, 1, -1];
			
			var queue = new Array((COLS-2)*(ROWS-2));
			
			var node : int = END;
			var paths : Array = new Array(COLS * ROWS);
			var p, px, py : int;
			var tail, head : int;
			tail = head = 0;
			
			do {
				px = node%COLS;
				py = int(node/COLS);
				for (var i = 0; i < 4; i++) {
					p = (py+DY[i])*COLS+px+DX[i];
					if (!paths[p] && map[p]) {
						queue[tail++] = p;
						if (e.ctrlKey) paths[p] = relax(p, node, paths[node]);
						else paths[p] = node;
					}
				}
				node = queue[head++];
			} while (tail != head);
			
			timeTextBox.text = "Time: " + (getTimer() - t) + "ms";
			
			drawPaths(paths);
		}
		
	}
	
}