Dijkstra(A*)

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

/**
 * A*経路探索
 * http://gingama.hp.infoseek.co.jp/java/a_star.html
 */
package 
{
	import flash.display.Bitmap;
	import flash.display.BitmapData;
	import flash.display.Sprite;
	import flash.events.Event;
	
	/**
	 * Dijkstra
	 * @author svartalf
	 */
	[SWF(width='300',height='300')]
	public class Main extends Sprite 
	{	
		private var startNode:Node;
		private var goalNode:Node;
		
		private var openList:Array;
		private var closeList:Array;
		
		private var dir4:Array = [[0, -1], [-1, 0], [0, 1], [1, 0]];
		private var map:Array =    [[1,1,1,1,1,1,1,1,1,1],
									[1,1,1,1,1,1,1,1,1,1],
									[1,1,1,1,1,1,1,1,1,1],
									[1,0,0,0,0,0,0,1,1,1],
									[1,1,1,1,1,1,0,1,1,1],
									[1,1,1,1,1,1,0,1,1,1],
									[1,1,1,1,1,1,0,1,1,1],
									[1,1,1,1,1,1,0,1,1,1],
									[1,1,1,1,1,1,0,1,1,1],
									[1,1,1,1,1,1,1,1,1,1]
		];
		
		private var nodeMap:Array;
									
		public function Main():void 
		{
			if (stage) init();
			else addEventListener(Event.ADDED_TO_STAGE, init);
		}
		
		private function init(e:Event = null):void 
		{
			removeEventListener(Event.ADDED_TO_STAGE, init);
			// entry point
			
			startNode = new Node(0,9,0,null)
			goalNode = new Node(9,0,0,null);
			
			openList = [startNode];
			closeList = [];
			
			makeNodeMap();
			
			searchMap();
		}
		
		/**
		 * mapからnodeMapを作成
		 */
		private function makeNodeMap():void
		{
			nodeMap = [];
			for (var y:int = 0; y < map.length; y++ )
			{
				nodeMap[y] = [];
				for (var x:int = 0; x < map[0].length; x++)
				{
					nodeMap[y][x] = new Node(x,y,0,null);//配列だとxyが逆になるので注意！
				}
			}
		}
		
		/**
		 * A*経路探索
		 */
		private function searchMap():void
		{
			var totalCost:int = 0;
			while (openList.length != 0)
			{
				openList.sortOn(["cost"], Array.NUMERIC | Array.DESCENDING);
				var cnode:Node = openList.pop();
				
				closeList.push(cnode);
				
				if (cnode.x == goalNode.x && cnode.y == goalNode.y)
				{
					prevNodeSearch();
					break;
				}
				
				var diffX:int;
				var diffY:int;
				var posX:int;
				var posY:int;
				var targetNode:Node;
				
				for (var i:int = 0; i < dir4.length; i++ )
				{
					diffX = dir4[i][0];
					diffY = dir4[i][1];
					posX = cnode.x + diffX;
					posY = cnode.y + diffY;
					
					if ( posX >= 0 && posX < 10 && posY >= 0 && posY < 10)
					{
						targetNode = nodeMap[posY][posX];
						
						if ( targetNode.cost == 0 && map[posY][posX] == 1)
						{
							targetNode.cost = Math.sqrt( Math.pow((goalNode.x - targetNode.x), 2) + Math.pow((goalNode.y - targetNode.y), 2)) + totalCost;
							targetNode.prevNode = cnode;
							nodeMap[posY][posX] = targetNode;
							openList.push(targetNode);
						}
					}
				}
				totalCost++;
			}
		}
		
		/**
		 * 結果出力
		 */
		private function prevNodeSearch():void
		{
			var bmd:BitmapData = new BitmapData(10, 10, true);
			for (var y:int = 0; y < 10;y++ )
			{
				for (var x:int = 0; x < 10; x++)
				{
					if (map[y][x] == 1)
					{
						bmd.setPixel32(x, y, 0x33000000);
					}
				}
			}
			
			var node:Node = closeList.pop();
			
			bmd.setPixel32(node.x,node.y,0xFF000000);
			while (node.prevNode != null)
			{
				bmd.setPixel32(node.x,node.y,0xFF000000);
				node = node.prevNode;
			}
			bmd.setPixel32(node.x,node.y,0xFF000000);
			
			var bm:Bitmap = addChild(new Bitmap(bmd)) as Bitmap;
			bm.scaleX = bm.scaleY = 5;
			
		}
	}
}

/**
 * ノードクラス
 */
class Node
{
	private var _x:int;
	public function get x():int
	{
		return _x;
	}
	
	private var _y:int;
	public function get y():int
	{
		return _y;
	}
	
	private var _cost:Number;
	public function get cost():Number
	{
		return _cost;
	}
	public function set cost(value:Number):void
	{
		_cost = value;
	}
	
	private var _prevNode:Node;
	public function get prevNode():Node
	{
		return _prevNode;
	}
	public function set prevNode(value:Node):void
	{
		_prevNode = value;
	}
	
	public function Node(x:int, y:int, cost:Number = 0, prevNode:Node = null):void
	{
		_x = x;
		_y = y;
		_cost = cost;
		_prevNode = prevNode;
	}
}