oastar.js

var info = function() {
   console.log.apply(this, arguments);
}

/**
 * node, one tile on the map.
 */
var Node = function(x, y, cost, xparent, yparent) {
   this.key = x + '.' + y;
   this.x = x;
   this.y = y;
   this.cost = 0;
   this.parent = null;
   return this;
}

Node.prototype.toString = function() {
   //return this.key + '(' + this.cost + ')<-' + (this.parent && this.parent.toString());
   return this.key + ' <= ' + (this.parent && this.parent.toString());
}

/**
 * map definition & read in
 * 1 == start
 * 2 == goal
 * x == not walkable
 */
var map = "\
................................\n\
....x.....1.....................\n\
.....x..xx.....xx.xx............\n\
.....x........xx................\n\
.....xx.......x.....x...........\n\
.....xx...x...x......x..........\n\
.............xx...xxx...........\n\
.......x.....x....x2............\n\
..................xxx...........\n\
";

var nodes = {};
var open = {};
var close = {};
var start = null;
var goal = null;

map.split('\n').forEach(function(line, row) {
   line.split('').forEach(function(nodeStr, col) {
      var node = new Node(col, row);
      var nodeKey = col + '.' + row;
      if (nodeStr == '2') {
         goal = node;
         info ('GOAL: ' + node);
      } else if (nodeStr == '1') {
         start = node;
         open[nodeKey] = node;
         info ('START: ' + node);
      }
      if (nodeStr != 'x') {
         nodes[nodeKey] = node;
      }
   });
});

/**
 * heuristic function, currently straight differential
 */
var heuristic = function(n) {
   return Math.abs(goal.x - n.x) + Math.abs(goal.y - n.y);
};

/**
 * search for node with best estimate (=cost + heuristic)
 */
var getBestEstimateNode = function(ns) {
   var bestNode = null;
   var bestEstimate = null;
   for each (node in ns) {
      var currEstimate = node.cost + heuristic(node);
      if (!bestEstimate || bestEstimate > currEstimate) {
         bestNode = node;
         bestEstimate = currEstimate;
      }
   }
   return [bestNode, bestEstimate];
};

/**
 * nodes left in list?
 */
var hasNodes = function(ns) {
   for each (node in ns) {
      return true;
   }
   return false;
};

/**
 * get all neighbours
 */
var getNeighbours = function(node) {
   var neighbours = [];
   var diffs = [
      [-1, 0],
      [+1, 0],
      [ 0, +1],
      [ 0, -1]
   ];
   for each (var [xdiff, ydiff] in diffs) {
      var neighbourKey = (node.x + xdiff) + '.' + (node.y + ydiff);
      var neighbour = nodes[neighbourKey];
      if (neighbour !== undefined) {
         neighbours.push(neighbour);
      }
   }
   return neighbours;
}

var astar = function() {
   while (hasNodes(open)) {
      var [node, estimate] = getBestEstimateNode(open);
      delete open[node.key];
      close[node.key] = node;
      
      //info ('best node ' + node, estimate);
      if (node == goal) {
         throw 'goal reached';
      } else {
         var neighbours = getNeighbours(node);
         for each (var n in neighbours) {
            //info ('neighbour ' + n);
            if (close[n.key] !== undefined) continue;

            var cost = node.cost + 1 + heuristic(n);
            //info ('n.cost ' + n.cost);
            
            if (open[n.key] !== undefined && cost > n.cost) {
               continue;
            }
            n.parent = node;
            n.cost = cost;
            open[n.key] = n;
         }
      }
      //info('open ', [o.toString() for each (o in open)]);
      //info('close ', [c.toString() for each (c in close)]);
      //info('------');
   }
};

/**
 * get node for given parent
 */
var getChild = function(parent) {
   for each (var node in nodes) {
      if (node.parent === parent) return node;
   }
   return null;
}

try {
   astar();
   info ('no path found');
} catch (e) {
   // backtrack
   info ('path: ' + goal);
}