Archive | May 2006

A* Pathfinding algorithm AS2 version

Learining A* Pathfinding algorithm for some days.This Class could be used in Cross(4 direction path finding).
See all the Public method for usage.

import mx.events.EventDispatcher;
/**
* @author rison
* @data 2006-05-03
* @version 1.1
* @usage A* Pathfinding 
*/
class AStar extends EventDispatcher
{
	//init var
	private static var COST:Number = 10;
	
	private var path:Array;
	private var openList:Array;
	private var closeList:Array;
	private var map:Array;
	private var pointType:Array;
	private var directData:Array;
	private var owner:Object;
	private var isSearching:Boolean;
	//
	public function AStar()
	{
		owner = this;
		path = [];
		pointType = [];
		openList = [];
		closeList = [];
		directData = [];
		map = [];
		initDirectData();
	}
	public function setMap(map_t:Array)
	{
		map = map_t;
		setPointType(map);
	}
	public function findPath(startX:Number,startY:Number,endX:Number,endY:Number)
	{
		initData();
		isSearching = true;
		var startPoint:Object = {};
		var endPoint:Object = {};
		var prePoint:Object = {};
		startPoint.X = startX;
		startPoint.Y = startY;
		endPoint.X = endX;
		endPoint.Y = endY;
		startPoint.parent = null;
		startPoint.G = 0;
		startPoint.H = manhattanDis(startPoint,endPoint);
		startPoint.F = startPoint.G + startPoint.H;
		prePoint = startPoint;
		send2List(startPoint,closeList);
		while (isSearching == true)
		{
			for (var i = 0; i < directData.length; i++)
			{
				var tempPoint:Object = {};
				tempPoint.X = prePoint.X + directData[i][0];
				tempPoint.Y = prePoint.Y + directData[i][1];
				if (isOut(tempPoint) == true)
				{
				}
				else
				{
					if (tempPoint.Y == endPoint.Y && tempPoint.X == endPoint.X)
					{
						//found
						isSearching = false;
						send2List(tempPoint,closeList);
						tempPoint.parent = prePoint;
						tempPoint.G = prePoint.G + directData[i][2];
						tempPoint.H = manhattanDis(tempPoint,endPoint);
						tempPoint.F = tempPoint.G + tempPoint.H;
						//trace(closeList[closeList.length-1].X+" "+closeList[closeList.length-1].Y);
						trace("path found! inner trace");
						drawPath();
						dispatchEvent( {type:"onPathFound",obj:owner});
						return;
					}
					if (getPointType(tempPoint) == "road" && isInList(tempPoint,closeList) == false)
					{
						//is not in closelist and it is road
						if (isInList(tempPoint,openList) == false)
						{
							//not open yet
							send2List(tempPoint,openList);
							//trace( "ol:"+openList[0].X+"=="+openList[0].Y);
							tempPoint.parent = prePoint;
							tempPoint.G = prePoint.G + directData[i][2];
							tempPoint.H = manhattanDis(tempPoint,endPoint);
							tempPoint.F = tempPoint.G + tempPoint.H;
						}
						else
						{
							//already in open list
							var tempG:Number = prePoint.G + directData[i][2];
							for (var j = 0; j < openList.length; j++)
							{
								if (tempPoint.X == openList[j].X && tempPoint.Y == openList[j].Y)
								{
									if (tempG < openList[j].G)
									{
										//now is better
										openList[j].G = tempG;
										openList[j].F = openList[j].G + openList[j].H;
										openList[j].parent = prePoint;
									}
									break;
								}
							}
						}
					}
				}
			}
			if (openList.length == 0)
			{
				isSearching = false;
				dispatchEvent({type:"onPathBlock",obj:owner});
				return;
			}
			sortList(openList);
			prePoint = openList.shift();
			send2List(prePoint,closeList);
			//trace(closeList[closeList.length-1].X+" "+closeList[closeList.length-1].Y);
		}
	}
	public function getPath():Array
	{
		path.reverse();
		return path;
	}
	private function initData():Void
	{
		openList = [];
		closeList = [];
		path = [];
	}
	private function drawPath()
	{
		//trace("set path");
		closeList.reverse();
		var currentPathPoint:Object = {};
		currentPathPoint = closeList[0];
		send2List(currentPathPoint,path);
		//trace(currentPathPoint.X+" "+currentPathPoint.Y);
		for (var i = 1; i < closeList.length; i++)
		{
			if (currentPathPoint.parent == null)
			{
				break;
			}
			//trace(currentPathPoint.parent.X+" "+currentPathPoint.parent.Y); 
			send2List(currentPathPoint.parent,path);
			currentPathPoint = currentPathPoint.parent;
		}
	}
	private function getPointType(point_t:Object):String
	{
		return pointType[point_t.X][point_t.Y];
	}
	private function setPointType(map_t:Array)
	{

		for (var i = 0; i < map_t.length; i++)
		{
			pointType[i] = [];
			for (var j = 0; j < map_t[0].length; j++)
			{
				if (map_t[i][j] != 0)
				{
					pointType[i].push("wall");
				}
				else if (map_t[i][j] == 0)
				{
					pointType[i].push("road");
				}
			}
		}
	}
	private function initDirectData():Void
	{
		//down,right,up,left
		directData[0] = [1,0,10];
		directData[1] = [0,1,10];
		directData[2] = [-1,0,10];
		directData[3] = [0,-1,10];
	}
	private function sortList(list_t:Array):Void
	{
		list_t.sortOn("F",Array.NUMERIC);
	}
	private function isOut(point_t:Object):Boolean
	{
		if (point_t.X < 0 || point_t.Y < 0 || point_t.X > 16 || point_t.Y > 16)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	private function isInList(point_t:Object,list_t:Array):Boolean
	{
		if (list_t.length == 0)
		{
			return false;
		}
		for (var i = 0; i < list_t.length; )
		{
			if (list_t[i].X == point_t.X && list_t[i].Y == point_t.Y)
			{
				return true;
				break;
			}
			i++;
			if (i == list_t.length)
			{
				return false;
			}
		}
	}
	private function manhattanDis(start_t:Object,end_t:Object):Number
	{
		var dis:Number;
		dis = Math.abs(start_t.X - end_t.X) + Math.abs(start_t.Y - end_t.Y);
		return dis * COST;
	}
	private function send2List(point_t:Object,list_t:Array):Void
	{
		list_t.push(point_t);
	}
}