Tag Archive | Mood
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); } }