flash on 2010-4-13

/**
 * Copyright kihon ( http://wonderfl.net/user/kihon )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/uM2L
 */

package
{
	import flash.display.Sprite;
	import flash.geom.Point;
	import flash.text.TextField;
	import flash.text.TextFormat;
	
	public class Main extends Sprite
	{
		private var map:String = 
		"***************************" +
		"*S        *   *   *      G*" +
		"* ******* *       *       *" +
		"*         *   *   *       *" +
		"* *********   *   *       *" +
		"*             *           *" +
		"***************************";

		private var WIDTH:int = 27;
		private var HEIGHT:int = 7;

		private var open /*Node*/:Array = [];
		private var close/*Node*/:Array = [];

		private var nodes:Array;

		private var start:Point;
		private var goal:Point;
		
		public function Main()
		{
			start = new Point(int(map.indexOf("S") % WIDTH), int(map.indexOf("S") / WIDTH));
			goal  = new Point(int(map.indexOf("G") % WIDTH), int(map.indexOf("G") / WIDTH));

			nodes = new Array(HEIGHT);
			for (var y:int = 0; y < HEIGHT; y++)
			{
				nodes[y] = new Array(WIDTH);
				for (var x:int = 0; x < WIDTH; x++)
				{
					var node:Node = new Node();
					node.x = x;
					node.y = y;
					nodes[y][x] = node;
				}
			}
			
			open.push(nodes[start.y][start.x]);
			
			while (true)
			{
				open.sortOn("f", Array.NUMERIC);
				node = open.shift();
				
				if (node == null) return;
				close.push(node);
				if (node.x == goal.x && node.y == goal.y) break;
				
				var dir:Array = 
				[
					[ 0,  1, 1.0],
					[ 0, -1, 1.0],
					[ 1,  0, 1.0],
					[-1,  0, 1.0]
				];
				
				for (var i:int = 0; i < dir.length; i++)
				{
					var tx:int = node.x + dir[i][0];
					var ty:int = node.y + dir[i][1];
					
					if (tx < 0 || WIDTH  <= tx ||
						ty < 0 || HEIGHT <= ty) continue;
					if (map.charAt(ty * WIDTH + tx) == "*") continue; 　// 壁だったら
					
					var next:Node = nodes[ty][tx];
					var g:Number = node.g + dir[i][2];
					var h:Number = Math.abs(goal.x - next.x) + Math.abs(goal.y - next.y);
					var f:Number = g + h;
					
					if (open.indexOf(next) != -1 || close.indexOf(next) != -1)
					{
						if (next.f > f)
						{
							next.g = g;
							next.h = h;
							next.f = f;
							next.prev.x = node.x;
							next.prev.y = node.y;
						}
					}
					else
					{
						next.g = g;
						next.h = h;
						next.f = f;
						next.prev.x = node.x;
						next.prev.y = node.y;
						open.push(next);
					}
				}
			}
			
			var array:Array = map.split("");
			while (true)
			{
				node = nodes[node.prev.y][node.prev.x];
				if (node.prev.x == -1) break;
				array[node.y * WIDTH + node.x] = "O";
			}
			
			var tf:TextField = new TextField();
			var format:TextFormat = new TextFormat("_typeWriter", 16, 0x0, true);
			format.leading = -6;
			tf.defaultTextFormat = format;
			tf.autoSize = "left";
			addChild(tf);

			for (i = 0; i < array.length; i++)
			{
				tf.appendText(array[i]);
				if ((i + 1) % WIDTH == 0)
				{
					tf.appendText("\n");
				}
			}
		}
	}
}
import flash.geom.Point;

class Node
{
	public var x:int;
	public var y:int;
	public var prev:Point = new Point(-1);
	
	public var g:Number = 0;
	public var h:Number;
	public var f:Number;
}