a-star.js

//!/usr/bin/js
// vim: fileencoding=utf-8
// spidermonkey or rhino
//
// algorithm follow from http://ja.wikipedia.org/wiki/A*

var map = [
  "**************************",
  "*S* *                    *",
  "* * *  *  *************  *",
  "* *   *    ************  *",
  "*    *                   *",
  "************** ***********",
  "*                        *",
  "** ***********************",
  "*      *              G  *",
  "*  *      *********** *  *",
  "*    *        ******* *  *",
  "*       *                *",
  "**************************"
];

var map_width = Math.max.apply(Math, map.map(function(n){ return n.length }));
var map_height = map.length;

function Node(x, y){
  this.x = x;
  this.y = y;
  this.hs = Node.hs(x, y);
  this.fs = 0;
  this.parent = null;
}

Node.isSamePos = function(a, b){
  return a.x === b.x && a.y === b.y;
};
Node.hs = function(x, y){
  return Math.pow(x - Node.Goal.x, 2) + Math.pow(y - Node.Goal.y, 2);
}
Node.Direct = [[1,0], [-1,0], [0,1], [0,-1]];

Node.prototype = {
  isGoal: function(){
    return Node.isSamePos(Node.Goal, this);
  }
};

NodeList = function(){
  this.list = [];
};

NodeList.prototype = {
  minFsNode: function(){
    var min = null;
    var i = 0;
    this.list.forEach(function(node, index){
      if(!min){
        min = node.fs;
        i   = index;
      } else if(node.fs < min){
        min = node.fs
        i   = index;
      }
    });
    return this.list[i];
  },
  find: function(x, y){
    var target = {
      x: x,
      y: y
    };
    var res = null;
    this.list.some(function(node){
      var flag = Node.isSamePos(target, node);
      if(flag)
        res = node;
      return flag
    });
    return res;
  },
  isEmpty: function(){
    return !this.list.length;
  },
  push: function(n){
    return this.list.push(n);
  },
  remove: function(node){
    var i = this.list.indexOf(node);
    if(~i)
      this.list.splice(i, 1);
  }
}

map.forEach(function(line, index_y){
  var s_i = line.indexOf('S');
  if(~s_i){
    Node.Start = {
      x: s_i,
      y: index_y
    }
  }
  var g_i = line.indexOf('G');
  if(~g_i){
    Node.Goal = {
      x: g_i,
      y: index_y
    }
  }
});

var opens = new NodeList();
var closes = new NodeList();
var start = new Node(Node.Start.x, Node.Start.y);
var end = null;

start.fs = start.hs;
opens.push(start);

while(true){
  if(opens.isEmpty()){
    print('no goal');
    break;
  }
  var node = opens.minFsNode();
  opens.remove(node);
  if(node.isGoal()){
    end = node;
    break;
  }
  closes.push(node);
  var n_gs = node.fs - node.hs;
  for(var i = 0, len = Node.Direct.length; i < len; ++i){
    var direct = Node.Direct[i];
    var x = node.x + direct[0];
    var y = node.y + direct[1];
    if(0 === y || y === map_height || 0 === x || x === map_width || map[y][x] === '*')
      continue;
    var dist = Math.pow(node.x - x, 2) + Math.pow(node.y - y, 2);
    var f_d = n_gs + Node.hs(x, y) + dist;
    var m = null;
    if(m = opens.find(x, y)){
      if(m.fs > f_d){
        m.fs = f_d;
        m.parent = node;
      }
    } else if(m = closes.find(x, y)){
      if(m.fs > f_d){
        m.fs = f_d;
        m.parent = node;
        opens.push(m);
        closes.remove(m);
      }
    } else {
      m = new Node(x, y);
      m.fs = f_d;
      m.parent = node;
      opens.push(m);
    }
  }
}

if(end){
  var n = end.parent;
  var result = map.map(function(line){ return line.split('') });
  while(true){
   if(!n.parent)
     break;
   result[n.y][n.x] = '$';
   n = n.parent;
  }
  print(result.map(function(line){ return line.join('') }).join('\n'));
}