/*
 * お題と全然関係ないコードですが、何となく思いついたので作成。
 * 
 * 画面をクリックすると壁を追加/削除することが出来ます。
 * ゴールまでの道が閉ざされてしまうとロボが止まってしまいます。
 *
 **/
package
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.geom.Point;
	import flash.geom.Matrix;
	import org.libspark.betweenas3.BetweenAS3;
	
	[SWF(backgroundColor="0xEDEDED")]
	public class Main extends Sprite
	{
		private var roboX:int = 1;
		private var roboY:int = 1;
		private var nodes:Array;
		private var count:int = 0;
		private var robo:Robo;
		
		private var direction:Array = 
		[
			[ 1,  0],
			[-1,  0],
			[ 0,  1],
			[ 0, -1]
		];
		
		public function Main()
		{
			Board.init();
			
			nodes = new Array(Board.HEIGHT);
			for (var y:int = 0; y < Board.HEIGHT; y++)
			{
				nodes[y] = new Array(Board.WIDTH);
				for (var x:int = 0; x < Board.WIDTH; x++)
				{
					var node:Node = new Node();
					node.pos.y = y, node.pos.x = x;
					node.status = Board.map[y][x];
					
					nodes[y][x] = node;
					
					if (node.status == Status.WALL)
					{
						var matrix:Matrix = new Matrix();
						matrix.createGradientBox(Board.SW, Board.SH, 45 * Math.PI / 180, x * Board.SW, y * Board.SH);
						graphics.beginGradientFill("linear", [0x0, 0x393939], [1.0, 1.0], [0, 255], matrix);
						graphics.drawRect(x * Board.SW, y * Board.SH, Board.SW, Board.SH);
						graphics.endFill();
					}
				}
			}
			
			robo = new Robo(8, true, true);
			robo.load();
			robo.scaleX = 0.8;
			robo.scaleY = 0.8;
			robo.x = roboX * Board.SW;
			robo.y = roboY * Board.SH;
			addChild(robo);
			
			drawTarget(1, 1);
			
			addEventListener(Event.ENTER_FRAME, solve);
			stage.addEventListener(MouseEvent.MOUSE_DOWN, onMouseDown);
		}
		
		private function onMouseDown(event:MouseEvent):void
		{
			if (mouseX < 0 || Board.SW * Board.WIDTH <= mouseX || mouseY < 0 || Board.SH * Board.HEIGHT <= mouseY) return;
			
			var x:int = mouseX / Board.SW;
			var y:int = mouseY / Board.SH;
			
			if (x == Board.targetX && y == Board.targetY) return;
			
			if (nodes[y][x].status == Status.WALL)
			{
				nodes[y][x].status = Status.FIELD;
				
				graphics.beginFill(0xEDEDED);
				graphics.drawRect(x * Board.SW, y * Board.SH, Board.SW, Board.SH);
				graphics.endFill();
			}
			else
			{
				nodes[y][x].status = Status.WALL;
				
				var matrix:Matrix = new Matrix();
				matrix.createGradientBox(Board.SW, Board.SH, 45 * Math.PI / 180, x * Board.SW, y * Board.SH);
				graphics.beginGradientFill("linear", [0x0, 0x393939], [1.0, 1.0], [0, 255], matrix);
				graphics.drawRect(x * Board.SW, y * Board.SH, Board.SW, Board.SH);
				graphics.endFill();
			}
		}
		
		private function drawTarget(bx:int, by:int):void
		{
			graphics.beginFill(0xEDEDED);
			graphics.drawRect(bx * Board.SW, by * Board.SH, Board.SW, Board.SW);
			graphics.endFill();
			
			var matrix:Matrix = new Matrix();
			matrix.createGradientBox(Board.SW, Board.SH, 45 * Math.PI / 180, x * Board.SW, y * Board.SH);
			graphics.beginGradientFill("linear", [0xFFC800, 0xFF9900], [1.0, 1.0], [0, 255], matrix);
			graphics.drawRect(Board.targetX * Board.SW, Board.targetY * Board.SH, Board.SW, Board.SW);
			graphics.endFill();
		}
		
		private function solve(event:Event = null):void
		{
			if (count++ % 10) return;

var data:Array = new Array();
			for (var y:int = 0; y < Board.HEIGHT; y++)
			{
				for (var x:int = 0; x < Board.WIDTH; x++)
				{
					nodes[y][x].count = Status.UNKNOWN;
					if (nodes[y][x].status == Status.FIELD) data.push(nodes[y][x]);
				}
			}
			
			if (roboY == Board.targetY && roboX == Board.targetX)
			{
				robo.stop();
				if (data.length != 0)
				{
					Board.map[Board.targetY][Board.targetX] = Status.FIELD;
					nodes[Board.targetY][Board.targetX].status = Status.FIELD;
					var n:Node = data[int(Math.random() * data.length)];
					
					var tempX:int = Board.targetX;
					var tempY:int = Board.targetY;
					Board.targetX = n.pos.x;
					Board.targetY = n.pos.y;
					drawTarget(tempX, tempY);
					robo.play();
				}
				return;
			}
			
			nodes[Board.targetY][Board.targetX].status = Status.GOAL;
			Board.map[Board.targetY][Board.targetX] = Status.GOAL;
			var search:Array = new Array();
			search.push(nodes[roboY][roboX]);
			
			do
			{
				search.sortOn("count", Array.NUMERIC | Array.DESCENDING);
				
				var node:Node = search.pop();
				if (node == null) return;
				if (nodes[node.pos.y][node.pos.x] == Status.WALL) continue;
				
				for (var i:int = 0; i < 4; i++)
				{
					var py:int = node.pos.y + direction[i][1];
					var px:int = node.pos.x + direction[i][0];
					
					if (py < 0 || Board.HEIGHT <= py || px < 0 || Board.WIDTH <= px) continue;
					if (nodes[py][px].status == Status.GOAL)
					{
						nodes[py][px].bpos.x = node.pos.x;
						nodes[py][px].bpos.y = node.pos.y;
						break;
					}
					
					if (nodes[py][px].status == Status.WALL) continue;
					
					if (nodes[py][px].count == Status.UNKNOWN)
					{
						nodes[py][px].count = node.count + 1;
						nodes[py][px].bpos.x = node.pos.x;
						nodes[py][px].bpos.y = node.pos.y;
						search.push(nodes[py][px]);
					}
					else if (node.count + 1 < nodes[py][px].count)
					{
						nodes[py][px].count = node.count + 1;
						nodes[py][px].bpos.x = node.pos.x;
						nodes[py][px].bpos.y = node.pos.y;
					}
				}
				
				if (px < 0 || Board.WIDTH <= px || py < 0 || Board.HEIGHT <= py) px = node.pos.x, py = node.pos.y;
			}
			while (Board.map[py][px] != Status.GOAL);
			
			var bpos:Point = new Point();
			bpos.y = Board.targetY;
			bpos.x = Board.targetX;
			
			do
			{
				node = nodes[bpos.y][bpos.x];
				if (node.bpos.y == roboY && node.bpos.x == roboX)
				{
					BetweenAS3.tween(robo, { x:node.pos.x * Board.SW, y:node.pos.y * Board.SH }, null, 0.3 ).play();
					roboY = node.pos.y;
					roboX = node.pos.x;
					break;
				}
				bpos = node.bpos;
			}
			while (true);
		}
	}
}

import flash.display.Sprite;
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Loader;
import flash.events.Event;
import flash.geom.Point;
import flash.geom.Matrix;
import flash.net.URLRequest;
import flash.system.LoaderContext;

class Board
{
	public static const WIDTH:int = 20;
	public static const HEIGHT:int = 20;
	
	public static var targetY:int = 19;
	public static var targetX:int = 19;
	
	public static var SW:int = int(465 / 20);
	public static var SH:int = int(465 / 20);
	
	public static var map:Array;
	
	public static function init():void
	{
		map = new Array(HEIGHT);
		for (var y:int = 0; y < HEIGHT; y++)
		{
			map[y] = new Array(WIDTH);
			for (var x:int = 0; x < WIDTH; x++)
			{
				map[y][x] = 0;
			}
		}
		
		createMaze();
	}
	
	private static function createMaze():void
	{
		for (var y:int = 0; y < HEIGHT; y++)
		{
			for (var x:int = 0; x < WIDTH; x++)
			{
				if (y == 0 || x == 0 || y == SH - 1 || x == SW - 1 || y % 2 == 0 && x % 2 == 0) map[y][x] = Status.WALL;
				else map[y][x] = Status.FIELD;
			}
		}
		
		for (y = 2; y < HEIGHT - 1; y += 2)
		{
			var dx:int = 2;
			var dy:int = y;
			
			switch (Math.floor(Math.random() * 4))
			{
				case 0:
					dx++;
					break;
				case 1:
					dx--;
					break;
				case 2:
					dy++;
					break;
				case 3:
					dy--;
					break;
			}
			
			if (!map[dy][dx]) map[dy][dx] = Status.WALL;
			else y -= 2;
		}
		
		for (x = 4; x < WIDTH - 1; x += 2)
		{
			for (y = 2; y < HEIGHT - 1; y += 2)
			{
				dx = x;
				dy = y;
				
				switch (Math.floor(Math.random() * 3))
				{
					case 0:
						dy++;
						break;
					case 1:
						dy--;
						break;
					case 2:
						dx++;
						break;
				}
				
				if (!map[dy][dx]) map[dy][dx] = Status.WALL;
				else y -= 2;
			}
		}
	}
	
	public function Board(){}
}

class Node
{
	public var pos:Point = new Point();
	public var bpos:Point = new Point();
	public var count:int = Status.UNKNOWN;
	public var status:int;
}

class Status
{
	public static const FIELD:int = 0;
	public static const WALL:int = -1;
	public static const GOAL:int = 2;
	public static const UNKNOWN:int = 99999;
}

class Robo extends Sprite {
    public static const READY:String = "READY";
    public var imgSrc:String = "http://assets.dev.wonderfl.net/images/related_images/e/ea/ea8a/ea8a6b1d37c2cec12e07893c66f164a9da1e92c0";
    
    private var _loader:Loader;
    private var _frame:Bitmap;
    
    public var frames:Array;
    private var _currentFrame:int = 0;
    private var _totalFrames:int = 0;
    
    private var _frameRate:int = 8;
    private var _autoPlay:Boolean = false;
    public function Robo( frameRate:int = 8, autoPlay:Boolean = false, autoLoad:Boolean = false ){
        _frameRate = frameRate;
        _autoPlay = autoPlay;
        
       // if( autoLoad ) load();
    }
    public function load():void {
        _loader = new Loader();
        
        _loader.contentLoaderInfo.addEventListener( Event.COMPLETE, completeHandler );
        _loader.load( new URLRequest(imgSrc), new LoaderContext(true) );
    }
    private function completeHandler(e:Event):void {
        var bmp:BitmapData = Bitmap( _loader.content ).bitmapData;
        _loader.contentLoaderInfo.removeEventListener( Event.COMPLETE, completeHandler );
        _loader= null;
        
        _frame = new Bitmap();
        addChild( _frame );
        
        frames = [];
        
        const frameWidth:int = 20;
        const frameHeight:int = 34;
        
        var numFrames:int = bmp.width/frameWidth;
        for( var i:int=0; i< numFrames; ++i ) {
            for( var f:int=0; f<_frameRate; ++f ) {
                var frame:BitmapData = new BitmapData( frameWidth, frameHeight, true, 0 );
                var matrix:Matrix = new Matrix();
                matrix.translate( -i*frameWidth, 0 );
                frame.draw( bmp, matrix );
                frames.push( frame );
            }
        }
        _totalFrames = frames.length;
        
        update();
        
        dispatchEvent( new Event(READY) );
        
        if( _autoPlay ) play();
    }
    
    private function update(e:Event=null):void {
        _frame.bitmapData = frames[_currentFrame]
        _currentFrame = (_currentFrame+1) % _totalFrames;
    }
    
    public function play():void {
        if( isReady )
            addEventListener( Event.ENTER_FRAME, update );
    }
    public function stop():void {
        removeEventListener( Event.ENTER_FRAME, update );
    }
    
    public function get currentFrame():int { return _currentFrame+1; }
    public function get totalFrames():int { return _totalFrames; }
    
    public function get isReady():Boolean {
        return frames && frames.length>0;
    }
}

ロボと迷路