метод, реализация А*.
Код:
/*
===============================================================================
= PATHFINDING FUNCTION
=------------------------------------------------------------------------------
= Version: 1.1.4
= Last changes: jul 15 (1.0.0) - first version
= aug 09 (1.0.1) - several speed improvements, thanks tonypa
= aug 10 (1.0.2) - even more speed improvements by tonypa (again)
= aug 31 (1.0.3) - return NULL if error (instead of error string)
= aug 31 (1.1.3) - added cornering option. thanks for LAlex for
= his suggestions
= 2004 may 28 (1.1.4) - fixed "undefined != 0" error on MX 2004 when
= compiling as flash 7. Thanks Inkog for finding
= the error and the solution
=------------------------------------------------------------------------------
= This function finds the path between two points (the START and the END point)
= on a given map, taken into account walls/obstacles and terrain costs.
=
= It uses an A* ("a star") algorithm with heuristic approximation for a faster
= result. Much of this function is basic on theory learnt from this language
= independent tutorial:
= http://www.policyalmanac.org/games/aStarTutorial.htm
=------------------------------------------------------------------------------
= How to use:
=
= my_path_array = findPath (map, start_y, start_x, end_y, end_x)
=
= Parameters:
= map = bidimensional array with rows and columns. Each cell contains a value
= of 0 (wall) or 1+ (terrain - the higher, the more expensive to ride)
===============================================================================
*/
findPath = function(map, startY, startX, endY, endX) {
if (startY == undefined || startX == undefined) return null; // Error: no starting point
if (endY == undefined || endX == undefined) return null; // Error: no ending point
// Caches dimensions
var mapH = map.length;
var mapW = map[0].length;
// New status arrays
var 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
// 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 ALLOW_DIAGONAL = false; // If diagonal movements are allowed at all
var ALLOW_DIAGONAL_CORNERING = false; // If diagonal movements over corners are allowed
// Complimentary functions =========================================================
isOpen = function (y, x) {
// Return TRUE if the point is on the open list, false if otherwise
return mapStatus[y][x].open;
};
isClosed = function (y, x) {
// Return TRUE if the point is on the closed list, false if otherwise
return mapStatus[y][x].closed;
};
nearerSquare = function() {
// 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;
};
closeSquare = function(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;
};
openSquare = function(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;
};
// Ok, now go back to our regular schedule. Find the path! -------------------------
// Now really starts
var 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 (j >= 0 && j < mapH && k >= 0 && k < mapW && !(j==nowY && k==nowX) && (ALLOW_DIAGONAL || j==nowY || k==nowX) && (ALLOW_DIAGONAL_CORNERING || j==nowY || k==nowX || (map[j][nowX] != 0 && map[nowY][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 py=mapStatus[nowY][nowX].parent[0];
//var px=mapStatus[nowY][nowX].parent[1];
//var pcost=mapStatus[nowY][nowX].movementCost;
//if(py!=undefined){pcost=mapStatus[py][px].movementCost;};
var movementCost = mapStatus[nowY][nowX].movementCost + ((j==nowY || k==nowX ? HV_COST : D_COST) * map[j][k]);
//trace("___map("+k+","+j+")="+map[j][k]+","+movementCost+'['+mapStatus[nowY][nowX].movementCost+',('+nowX+','+nowY+')]');
//gfx_mc.sur_map[k][j]=movementCost;
//trace('('+k+','+j+') from ['+nowX+","+nowY+"]");
//gfx_mc.sur_map_type[k][j]=100;
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?
// Clean up temporary functions
//delete isOpen;
//delete isClosed;
//delete nearerSquare;
//delete closeSquare;
//delete openSquare;
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]);
}
//trace("____path:"+ path_xy.join('|'));
return path_xy;
} else {
// Ended with 0 open squares; ran out of squares, path NOT found
return null;
}
};
//ASSetPropFlags(_global, "findPath", 1, 0);