[Котяра]

во вложении astar.zipтестовая флэшка по Badim'овскому алгоритму - переделан в класс Astra
Собственно сам класс (AS2)

// Поиск кратчайшего пути по алгоритму A*

class Astar 
{	

	var map:Array;
	var mapStatus:Array;
	var openList:Array;
		
	var mapH:Number;
	var mapW:Number;
	
	// подсчет времени выполнения
	var startFind:Number;
	var stopFind:Number;
	
	 // Constants/configuration - change here as needed! --------------------------------
	var HV_COST = 10; // "Movement cost" for horizontal/vertical moves
	var D_COST = 14; // "Movement cost" for diagonal moves
	
	var log='';
	
	function Astar(_map)
	{
		map = _map;
	}
	
		  
		  
	function  isOpen(y, x) {
			// Return TRUE if the point is on the open list, false if otherwise
			return mapStatus[y][x].open;
		  }
	
	function isClosed(y, x) {
			// Return TRUE if the point is on the closed list, false if otherwise
			return mapStatus[y][x].closed;
		  }
		  
	function nearerSquare() {
			// Returns the square with a lower movementCost + heuristic distance
			// from the open list
			var minimum = 999999;
			var indexFound = 0;
			var thisF = undefined;
			var thisSquare = undefined;
			var i = openList.length;
			// Finds lowest
			while (i-->0) {
			  thisSquare = mapStatus[openList[i][0]][openList[i][1]];
			  thisF = thisSquare.heuristic + thisSquare.movementCost;
			  if (thisF <= minimum) {
				minimum = thisF;
				indexFound = i;
			  }
			}
			// Returns lowest
			return indexFound;
		  }
		  
		  
	function  closeSquare(y, x) {
			// Drop from the open list
			var len = openList.length;
			for (var i=0; i < len; i++) {
			  if (openList[i][0] == y) {
				if (openList[i][1] == x) {
				  openList.splice(i, 1);
				  break;
				}
			  }
			}
			// Closes an open square
			mapStatus[y][x].open = false;
			mapStatus[y][x].closed = true;
		  }
		  
		  
	function  openSquare(y, x, parent, movementCost, heuristic, replacing) {
			// Opens a square
			if (!replacing) {
			  openList.push([y,x]);
			  mapStatus[y][x] = {heuristic:heuristic, open:true, closed:false};
			}
			mapStatus[y][x].parent = parent;
			mapStatus[y][x].movementCost = movementCost;
		  }
		  
		  
		  
	
	function findPath( startX, startY, endX, endY) {
		startFind = new Date().getTime().valueOf();
			
		if (startY == undefined || startX == undefined) return null; // Error: no starting point
		if (endY == undefined || endX == undefined) return null; // Error: no ending point
		
			// Error: Closed start/end point
		
		if (map[startY][startX]==0 || map[endY][endX]==0) 
		{
			log = "Closed start/end point: " + map[startY][startX] + "," + map[endY][endX];
			trace(log);
			return null;
		
		}
		
	

		
		
			// Caches dimensions
			mapH = map.length;
			mapW = map[0].length;
			
			//trace (map);
			// New status arrays
			mapStatus = [];
			for (var i=0; i<mapH; i++){
				mapStatus[i] = [];
				for (var j=0; j<mapW; j++){
					mapStatus[i][j]={};
				}
			}
			// Finds the way given a certain path
			// Ok, now go back to our regular schedule. Find the path! 
			
			// Now really starts
			openList = new Array();
			openSquare (startY, startX, undefined, 0);
		  
			// Loops until there's no other way to go OR found the exit
			while (openList.length > 0 && !isClosed(endY, endX)) {
				// Browse through open squares
				var i = nearerSquare();
				
				var nowY = openList[i][0]/1;
				var nowX = openList[i][1]/1;
				
				// Closes current square as it has done its purpose...
				closeSquare (nowY, nowX);
				// Opens all nearby squares, ONLY if:
				//trace('__now:['+nowX+","+nowY+"]");
				for (var j=nowY-1; j<(nowY+2); j++) {
				for (var k=nowX-1; k<(nowX+2); k++) {
					if (j >= 0 && j < mapH && k >= 0 && k < mapW && map[j][k] != 0) 
					{

					// If not outside the boundaries or at the same point or a diagonal (if disabled) or a diagonal (with a wall next to it)...
					// And if not a wall...
							if (!isClosed(j,k)) {
								// And if not closed... THEN open.

								var movementCost = mapStatus[nowY][nowX].movementCost + ((j==nowY || k==nowX ? HV_COST : D_COST) * map[j][k]);
									if (isOpen(j,k)) {
										// Already opened: check if it's ok to re-open (cheaper)
										if (movementCost < mapStatus[j][k].movementCost) {
										  // Cheaper: simply replaces with new cost and parent.
										  //trace('__replace:('+k+','+j+') for ('+nowX+','+nowY+")");
										  openSquare (j, k, [nowY, nowX], movementCost, undefined, true); // heuristic not passed: faster, not needed 'cause it's already set
										}
									} 
									else 
									{
										// Empty: open.
										var heuristic = (Math.abs (j - endY) + Math.abs (k - endX)) * 10;
										openSquare (j, k, [nowY, nowX], movementCost, heuristic, false);
									}
							} else {
								// Already closed, ignore.
							}
					}
				}
			}
		}
			//Ended
			var pFound = isClosed(endY, endX); // Was the path found?
		  if (pFound) {
			// Ended with path found; generates return path
			var returnPath = [];
			var nowY = endY;
			var nowX = endX;
			var movCost=mapStatus[nowY][nowX].movementCost;
			while ((nowY != startY || nowX != startX)) {
			  returnPath.push([nowX,nowY,movCost]);
			  var newY = mapStatus[nowY][nowX].parent[0];
			  var newX = mapStatus[nowY][nowX].parent[1];
			  nowY = newY;
			  nowX = newX;
			  movCost=mapStatus[nowY][nowX].movementCost;
			}
			returnPath.push([startX,startY,0]);
			var path_xy=[];
			for(var i=returnPath.length-1;i>-1;i--){
				path_xy.push(returnPath[i]);
			}
			stopFind = new Date().getTime().valueOf();
			log="finding time:" + (stopFind - startFind)+"\npath:" + path_xy.join('|');
			trace (log);
			return path_xy;
		  } 
		  else 
		  {
			log="Ended with 0 open squares; ran out of squares, path NOT found";
			trace (log);
			return null;
		  }
		}

}