gistfile1.js

// world is a 2d array of integers (eg world[10][15] = 0)
// pathStart and pathEnd are arrays like [5,10]
function findPath(world, pathStart, pathEnd)
{
  // shortcuts for speed
  var21abs = Math.abs;
  var	max = Math.max;
  var	pow = Math.pow;
  var	sqrt = Math.sqrt;
  
  // the world data are integers: 
  // anything higher than this number is considered blocked
  // this is handy is you use numbered sprites, more than one
  // of which is walkable road, grass, mud, etc
  var maxWalkableTileNum = 0;
  
  // keep track of the world dimensions
  var worldWidth = world[0].length;
  var worldHeight = world.length;
  var worldSize =	worldWidth * worldHeight;
  
  // which heuristic should we use?
  // default: no diagonals (Manhattan)
  var distanceFunction = ManhattanDistance; 
  var	findNeighbours = function(){}; // empty
  
	/*

	// alternate heuristics, depending on your game:

	// diagonals allowed but no sqeezing through cracks:
	var distanceFunction = DiagonalDistance; 
	var findNeighbours = DiagonalNeighbours;

	// diagonals and squeezing through cracks allowed:
	var distanceFunction = DiagonalDistance; 
	var findNeighbours = DiagonalNeighboursFree;

	// euclidean but no squeezing through cracks:
	var distanceFunction = EuclideanDistance;
	var findNeighbours = DiagonalNeighbours;

	// euclidean and squeezing through cracks allowed:
	var distanceFunction = EuclideanDistance;
	var findNeighbours = DiagonalNeighbours;

	*/
  
  // returns boolean value (world cell is available and open)
  function canWalkHere(x, y)
  {
    return ((world[x]!=null) && 
            (world[x][y]!=null) && 
      (world[x][y] <= maxWalkableTileNum));
  };
  
  // Node function, returns a new object with Node properties
  // Used in the calculatePath function to store route costs, etc.
  function Node(Parent, Point)
  {
    return {
      // pointer to another Node object
      Parent:Parent,
      // array index of this Node in the world linear array
      value:Point.x + (Point.y * worldWidth),
      // the location coordinates of this Node
      x:Point.x,
      y:Point.y,
      // the distanceFunction cost to get 
      // TO this Node from the START
      f:0,
      // the distanceFunction cost to get 
      // from this Node to the GOAL
      g:0
    };
  };
  
  // Path function, executes AStar algorithm operations
  function calculatePath()
  {
    // create Nodes from the Start and End x,y coordinates
    var	mypathStart = Node(null, {x:pathStart[0], y:pathStart[1]});
    var mypathEnd = Node(null, {x:pathEnd[0], y:pathEnd[1]});
    // create an array that will contain all world cells
    var AStar = new Array(worldSize);
    // list of currently open Nodes
    var Open = [mypathStart]; 
    // list of closed Nodes
    var Closed = []; 
    // list of the final output array
    var result = []; 
    // reference to a Node (that is nearby)
    var myNeighbours; 
    // reference to a Node (that we are considering now)
    var myNode; 
    // reference to a Node (that starts a path in question)
    var myPath; 
    // temp integer variables used in the calculations
    var length, max, min, i, j; 
    // iterate through the 
    while(length = Open.length) 
    {
      max = worldSize;
      min = -1;
      for(i = 0; i < length; i++) 
      {
        if(Open[i].f < max) 
        {
          max = Open[i].f;
          min = i;
        }
      };
      // grab the next node and remove it from Open array
      myNode = Open.splice(min, 1)[0];
      // is it the destination node?
      if(myNode.value === mypathEnd.value) 
      {
        myPath = Closed[Closed.push(myNode) - 1];
        do 
        {
          result.push([myPath.x, myPath.y]);
        }
        while (myPath = myPath.Parent);
        // clear the working arrays
        AStar = Closed = Open = [];
        // we want to return start to finish
        result.reverse();
      } 
      else // not the destination 
      {
        // find which nearby nodes are walkable
        myNeighbours = Neighbours(myNode.x, myNode.y);
        // test each one that hasn't been tried already
        for(i = 0, j = myNeighbours.length; i < j; i++)
        {
          myPath = Node(myNode, myNeighbours[i]);
          if(!AStar[myPath.value])
          {
            // estimated cost of this particular route so far
            myPath.g = myNode.g + distanceFunction(myNeighbours[i], myNode);
            // estimated cost of entire guessed route to the destination
            myPath.f = myPath.g + distanceFunction(myNeighbours[i], mypathEnd);
            // remember this new path for testing above
            Open.push(myPath);
            // mark this node in the world graph as visited
            AStar[myPath.value] = true;
          };
        };
        // remember this route as having no more untested options
        Closed.push(myNode);
      };
    }; // keep iterating until length is not equal to Open.length
    return result;
  };
  
  // Neighbours functions, used by findNeighbours function
  // to locate adjacent available cells that aren't blocked
  
  // Returns every available North, South, East or West
  // cell that is empty. No diagonals, 
  // unless distanceFunction function is not Manhattan
  function Neighbours(x, y)
  {
    var	N = y - 1,
      S = y + 1,
        E = x + 1,
          W = x - 1,
            myN = N > -1 && canWalkHere(x, N),
              myS = S < worldHeight && canWalkHere(x, S),
                myE = E < worldWidth && canWalkHere(E, y),
                  myW = W > -1 && canWalkHere(W, y),
                    result = [];
    if(myN)
      result.push({x:x, y:N});
    if(myE)
      result.push({x:E, y:y});
    if(myS)
      result.push({x:x, y:S});
    if(myW)
      result.push({x:W, y:y});
    findNeighbours(myN, myS, myE, myW, N, S, E, W, result);
    return result;
  };
  
  // returns every available North East, South East, 
  // South West or North West cell - no squeezing through
  // "cracks" between two diagonals
  function DiagonalNeighbours(myN, myS, myE, myW, N, S, E, W, result)
  {
    if(myN) 
    {
      if(myE && canWalkHere(E, N))
      result.push({x:E, y:N});
      if(myW && canWalkHere(W, N))
      result.push({x:W, y:N});
    };
    if(myS)
    {
      if(myE && canWalkHere(E, S))
      result.push({x:E, y:S});
      if(myW && canWalkHere(W, S))
      result.push({x:W, y:S});
    };
  };
  
  // returns every available North East, South East, 
  // South West or North West cell including the times that
  // you would be squeezing through a "crack"
  function DiagonalNeighboursFree(myN, myS, myE, myW, N, S, E, W, result)
  {
    myN = N > -1;
    myS = S < worldHeight;
    myE = E < worldWidth;
    myW = W > -1;
    if(myE) 
    {
      if(myN && canWalkHere(E, N))
      result.push({x:E, y:N});
      if(myS && canWalkHere(E, S))
      result.push({x:E, y:S});
    };
    if(myW) 
    {
      if(myN && canWalkHere(W, N))
      result.push({x:W, y:N});
      if(myS && canWalkHere(W, S))
      result.push({x:W, y:S});
    };
  };
  
  // distanceFunction functions
  // these return how far away a point is to another
  
  function ManhattanDistance(Point, Goal)
  {	// linear movement - no diagonals - just cardinal directions (NSEW)
    return abs(Point.x - Goal.x) + abs(Point.y - Goal.y);
  };
  
  function DiagonalDistance(Point, Goal)
  {	// diagonal movement - assumes diag dist is 1, same as cardinals
    return max(abs(Point.x - Goal.x), abs(Point.y - Goal.y));
  };
  
  function EuclideanDistance(Point, Goal)
  {	// diagonals are considered a little farther than cardinal directions
    // diagonal movement using Euclide (AC = sqrt(AB^2 + BC^2))
    // where AB = x2 - x1 and BC = y2 - y1 and AC will be [x3, y3]
    return sqrt(pow(Point.x - Goal.x, 2) + pow(Point.y - Goal.y, 2));
  };
  
  // actually calculate the a-star path!
  // this returns an array of coordinates
  // that is empty if no path is possible
  return calculatePath();
};