/* =============================================================================== = PATHFINDING FUNCTION =------------------------------------------------------------------------------ = Version: 1.0.2 = Last changes: jul 15 (1.0.0) - first version = Last changes: aug 09 (1.0.1) - several speed improvements, thanks tonypa = Last changes: aug 10 (1.0.2) - even more speed improvements by tonypa (again) =------------------------------------------------------------------------------ = 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) =============================================================================== */ _global.findPath = function(map, startY, startX, endY, endX) { // 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 = true; // If diagonal movements are allowed at all var ALLOW_DIAGONAL_CORNERING = true; // Not implemented. Always true // 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! ------------------ // Caches dimensions var mapH = map.length; var mapW = map[0].length; // New status arrays var mapStatus = new Array(); for (var i=0; i 0 && !isClosed(endY, endX)) { // Browse through open squares var i = nearerSquare(); var nowY = openList[i][0]; var nowX = openList[i][1]; // Closes current square as it has done its purpose... closeSquare (nowY, nowX); // Opens all nearby squares, ONLY if: for (var j=nowY-1; j<=nowY+1; j++) { for (var k=nowX-1; k<=nowX+1; k++) { if (j >= 0 && j < mapH && k >= 0 && k < mapW && !(j==nowY && k==nowX) && (ALLOW_DIAGONAL || j==nowY || k==nowX)) { // If not outside the boundaries or at the same point or a diagonal (if disabled)... if (map[j][k] != 0) { // 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. 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. } } else { // Wall, 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 = new Array(); var nowY = endY; var nowX = endX; while ((nowY != startY || nowX != startX)) { returnPath.push([nowY,nowX]); var newY = mapStatus[nowY][nowX].parent[0]; var newX = mapStatus[nowY][nowX].parent[1]; nowY = newY; nowX = newX; } returnPath.push([startY,startX]); return (returnPath); } else { // Ended with 0 open squares; ran out of squares, path NOT found return ("ERROR: Could not reach the end"); } }; ASSetPropFlags(_global, "findPath", 1, 0);