Simple A* with JavaScript

astar.js

#!/usr/bin/env node

var Pathfinding = Object.create(null);

Pathfinding.Node = function(value) {
  this.value     = value;
  this.neighbors = [];
};

Pathfinding.Node.prototype.reset = function() {
  this.visited       = false;
  this.pathHeuristic = 0;
  this.pathParent    = null;
  this.pathCost      = NaN;
  this.pathData      = null;
};

function popLowest(openList) {
  var lowest = 0;
  for (var i = 1; i < openList.length; ++i) {
    if (openList[i].pathCost + openList[i].pathHeuristic < openList[lowest].pathCost + openList[lowest].pathHeuristic) {
      lowest = i;
    }
  }
  return openList.splice(lowest, 1)[0];
}

Pathfinding.aStar = function(start, goal, updateState, heuristic, stepCost) {
  start.pathData      = updateState(null, start.value);
  start.pathParent    = null;
  start.pathCost      = 0;
  start.pathHeuristic = heuristic(start.pathData, start.value, goal.value);
  var openList = [ start ];
  while (openList.length > 0) {
    var current = popLowest(openList);
    current.visited = true;
    for (var i in current.neighbors) {
      var neighbor = current.neighbors[i];
      if (neighbor.visited === true) {
        continue;
      }
      var pathData      = updateState(current.value, neighbor.value);
      var pathCost      = current.pathCost + stepCost(current.pathData, current.value, neighbor.value);
      var pathHeuristic = heuristic(pathData, neighbor.value, goal.value);
      var isOpen = ~openList.indexOf(neighbor);
      if (isOpen && pathCost + pathHeuristic > neighbor.pathCost + neighbor.pathHeuristic) {
        continue;
      }
      neighbor.pathParent    = current;
      neighbor.pathData      = pathData;
      neighbor.pathCost      = pathCost;
      neighbor.pathHeuristic = pathHeuristic;
      if (!isOpen) {
        openList.push(neighbor);
      }
    }
    if (current == goal) {
      return true;
    }
  }
  return false;
};

function GraphFrom2dArray(width, height) {
  this.width  = width;
  this.height = height;
  this.nodes  = [];
  for (var x = 0; x < width; x++) {
    this.nodes[x] = [];
    for (var y = 0; y < height; y++) {
      this.nodes[x][y] = new Pathfinding.Node({ x: x, y: y, cost: 0 }, 0);
      this.nodes[x][y].reset();
    }
  }
}

GraphFrom2dArray.prototype.connectAll = function() {
  for (var x1 = 0; x1 < this.width; x1++) {
    for (var y1 = 0; y1 < this.height; y1++) {
      var node = this.nodes[x1][y1];
      for (var x2 = 0; x2 < this.width; x2++) {
        for (var y2 = 0; y2 < this.height; y2++) {
          if (x1 == x2 && y1 == y2) {
            continue;
          }
          var dx = x2 - x1, dy = y2 - y1;
          // Só permite movimento em múltiplos de 45°
          if (dx != 0 && dy != 0 && Math.abs(dx) != Math.abs(dy)) {
            continue;
          }
          node.neighbors.push(this.nodes[x2][y2]);
        }
      }
    }
  }
};

GraphFrom2dArray.prototype.reset = function(costs) {
  for (var x in this.nodes) {
    for (var y in this.nodes[x]) {
      this.nodes[x][y].value.cost = costs[x][y];
      this.nodes[x][y].reset();
    }
  }
};

GraphFrom2dArray.prototype.node = function(x, y) {
  return this.nodes[x][y];
};

var Robocode = Object.create(null);

function travelTime(from, to) {
  var dx = Math.abs(from.x - to.x);
  var dy = Math.abs(from.y - to.y);
  var d = Math.sqrt(dx * dx + dy * dy);
  if (d == 0) {
    return 0;
  }
  var pixelsLostAccelerating = 28 + 8;
  var pixelsLostStopping     = 12 + 8;
  return Math.ceil((d * 100 + pixelsLostAccelerating + pixelsLostStopping) / 8);
}

function turnTime(from, to) {
  return Math.ceil(Math.abs(to - from) % 180 / 10);
}

function angle(from, to) {
  var dx = to.x - from.x, dy = to.y - from.y;
  var radians = Math.atan2(Math.abs(dy), Math.abs(dx));
  var angles  = radians * (180 / Math.PI);
  // Q1 +x +y
  if (dx >= 0 && dy >= 0) {
    return 90 - angles;
  }
  // Q2 +x -y
  if (dx >= 0 && dy < 0) {
    return angles + 90;
  }
  // Q3 -x -y
  if (dx < 0 && dy < 0) {
    return 270 - angles;
  }
  // Q4 -x +y
  return 270 + angles;
}

Robocode.updateState = function(current, next) {
  return { heading: current == null ? 90 : angle(current, next) };
};

Robocode.heuristic = function(state, from, to) {
  if (from.x == to.x && from.y == to.y) {
    return 0;
  }
  return turnTime(state.heading, angle(from, to)) +
    travelTime(from, to);
};

function sumPathNodes(graph, from, to) {
  var dx = to.x - from.x, dy = to.y - from.y;
  var length = Math.max(Math.abs(dx), Math.abs(dy));
  var xSign = dx == 0 ? 0 : dx > 0 ? 1 : -1;
  var ySign = dy == 0 ? 0 : dy >= 0 ? 1 : -1;
  var cost = 0;
  for (var i = 1; i <= length; ++i) {
    cost += graph.node(from.x + i * xSign, from.y + i * ySign).value.cost;
  }
  return cost;
}

Robocode.stepCost = function(graph) {
  return function(state, from, to) {
    if (from.x == to.x && from.y == to.y) {
      return 0;
    }
    return turnTime(state.heading, angle(from, to)) +
      travelTime(from, to) +
      (100 / 8) * 10 * sumPathNodes(graph, from, to);
  };
};

//     0  1  2  3
//     -  -  -  -
// 4 | 0  0  1  0 |
// 3 | S  0  1  G |
// 2 | 0  0  1  0 |
// 1 | 0  0  0  0 |
// 0 | 0  0  0  0 |
//     -  -  -  -

var costs = [ [ 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 1, 1, 1 ], [ 0, 0, 0, 0, 0 ] ];
var graph = new GraphFrom2dArray(4, 4);
graph.connectAll();
graph.reset(costs);
var start = graph.node(0, 3);
var goal  = graph.node(3, 3);
Pathfinding.aStar(start, goal, Robocode.updateState, Robocode.heuristic, Robocode.stepCost(graph));

function printPath(goal) {
  var result = [];
  var parent = goal;
  while (parent != null) {
    result.push("(" + parent.value.x + "," + parent.value.y + ") " + parent.pathCost + " (h >= " + parent.pathHeuristic + ") (heading: " + parent.pathData.heading + "°)");
    parent = parent.pathParent;
  }
  result.reverse();
  console.log(result.join('\n'));
}

printPath(goal);