Click on the map to calculate the path starting from the soldier position

Download the source code of this prototype

This function finds the path between two given points using an A* algorithm. It's usually needed on games that need pathfinding/navigating AI.

It uses a bidimensional map (the MAP), a START point (defined as an Y and X value, in this order to maintain standard with the way the map is built), and an END point (Y and X values).
Each MAP cell have a value of 0 (when it means a wall, or a cell it can't be visited on the route) or a value of 1 or greater. In this case, this value means the COST to navigate through that point. On an standard map, for example, a value of 1 would be used for a road, a value of 2 for normal terrain, and a value of 3 for mountains.
You can also modify the "CONSTANT variables" inside the function. For instance, you can set ALLOW_DIAGONAL to to TRUE to allow diagonal movements or to FALSE to disallow it.

AN EXAMPLE OF USAGE

// Creates a map

map = [[2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,0,0,0,0,0,0,0,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2],
       [2,2,2,2,2,2,2,2,2,2,1,2,2,2,2]];

// Finds the path from point 2,2 to point 9,9

fpath = findPath (map, 2, 2, 9, 9);

// Draw results

for (i=0; i<map.length; i++) {
   for (j=0; j<map[0].length; j++) {
      switch (map[i][j]) {
      case 0:
         _root.beginFill (0x333366);
         break;
      case 2:
         _root.beginFill (0xdddddd);
         break;
      case 1:
         _root.beginFill (0xeeeeee);
         break;
      }
      _root.moveTo (j*20, i*20);
      _root.lineTo ((j+1)*20,i*20);
      _root.lineTo ((j+1)*20,(i+1)*20);
      _root.lineTo (j*20,(i+1)*20);
      _root.lineTo (j*20,i*20);
      _root.endFill();
   }
}
for (i=0; i<fpath.length; i++) {
   x = fpath[i][1];
   y = fpath[i][0];
   _root.beginFill (0x993333, 70);
   _root.moveTo (x*20, y*20);
   _root.lineTo ((x+1)*20,y*20);
   _root.lineTo ((x+1)*20,(y+1)*20);
   _root.lineTo (x*20,(y+1)*20);
   _root.lineTo (x*20,y*20);
   _root.endFill();
}

THE SOURCE CODE

Note: some lines (where you see "»") in the following script have been broken for page layout reasons.

/*
===============================================================================
= 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<mapH; i++) mapStatus[i] = new Array();
  if (startY == undefined) return ("ERROR: No starting point");
  if (endY == undefined) return ("ERROR: No ending point");
  // Now really starts
  var openList = new Array();
  openSquare (startY, startX);
  
  // 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];
    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);