A* (a-star) Pathfinding with Node.js and Ncurses.

path-demo.js

var nc = require('ncurses'),
    ui = require('./src/ui'),
    map = require('./src/path-map'),
    pf = require('./src/pathfinding');

nc.colorPair(2, nc.colors.BLACK, 15);
ui.windows.root.bkgd = nc.colorPair(2);


var map = map.createMap(nc.cols, nc.lines, ui.windows.root);

var grid = new pf.Grid(nc.cols, nc.lines, map);
var astar = new pf.AStar();



ui.windows.root.on('inputChar', function (key, keyCode) {
  var curx = map.window.curx,
      cury = map.window.cury;
  
  switch (keyCode) {
  case nc.keys.RIGHT:
    map.window.cursor(cury, curx + 1)
    break;
  case nc.keys.LEFT:
    map.window.cursor(cury, curx - 1)
    break;
  case nc.keys.UP:
    map.window.cursor(cury - 1, curx)
    break;
  case nc.keys.DOWN:
    map.window.cursor(cury + 1, curx)
    break;
  case nc.keys.SPACE:
    map.toggleCollision(curx, cury);
    grid.setWalkable(curx, cury, !grid.getNode(curx, cury).walkable);
    redraw_path();
    break;
  }
  switch (key) {
  case "c":
    map.drawPath(false);
    break;
  case "s":
    map.setStart(curx, cury);
    grid.setStartNode(curx, cury);
    redraw_path();
    break;
  case "e":
    map.setEnd(curx, cury);
    grid.setEndNode(curx, cury);
    redraw_path();
    break;
  case "p":
    redraw_path();
    break;
  case "h":
    //toggle heuristics
    if (astar.heuristic === astar.diagonal) {
      astar.heuristic = astar.manhattan;
      map.__heuristicName = 'manhattan';
    } else if (astar.heuristic === astar.manhattan) {
      astar.heuristic = astar.euclidian;
      map.__heuristicName = 'euclidian';
    } else {
      astar.heuristic = astar.diagonal;
      map.__heuristicName = 'diagonal';
    }
    redraw_path();
    
    break;
  }
  
  map.draw();
});


map.draw();


function redraw_path () {
  if (grid.startNode && grid.endNode) {
    if (astar.findPath(grid) !== false) {
      astar.buildPath();
      map.drawPath(astar.path);
      map.__msg = null;
    } else {
      map.drawPath(false);
      map.__msg = "No path found."
    }
  }
}

path-map.js

var nc = require('ncurses');

function add_border (map, cols) {
  for (var i = 0, len = map.length; i < len; i++) {
    map[i] = 0;
    if (i % cols === 0) {
      map[i] = 1;
      if (i > 0) { map[i-1] = 1; }
    }
    if (i < cols || i >= len - cols) {
      map[i] = 1;
    }
  }
}

function draw () {
  var i = this.length,
      w = this.width,
      map = this,
      curx = this.window.curx,
      cury = this.window.cury,
      tile, cost;
  
  while (i--) {
    x = i % w;
    y = (i / w) | 0;
    tile = (map[i] === 1) ? "#" : " ";
    this.window.addstr(y, x, tile);
  }

  if (map.__path) {
    map.__path.forEach(function (node) {
      map.window.addstr(node.y, node.x, '.');
    });
  }
  if (map.__start) {
    this.window.addstr(map.__start.y, map.__start.x, "@");
  }
  if (map.__end) {
    this.window.addstr(map.__end.y, map.__end.x, ">");
  }

  //log
  if (map.__msg) {
    this.window.addstr(map.height - 1, 0, " " + map.__msg + " ");
  } else {
    cost = (map.__path) ? map.__path.length - 1 : "-";
    this.window.addstr(map.height - 1, 0,
                       " Cost: " + cost +
                       ", Heuristic: " + map.__heuristicName + " ");
  }
  
  this.window.cursor(cury, curx);
  this.window.refresh();
}

function toggleCollision (x, y) {
  var pos = x + (y * this.width);
  if (this[pos] === 0) {
    this[pos] = 1;
  } else {
    this[pos] = 0;
  }
}

function setStart (x, y) {
  this.__start = {x:x, y:y};
}

function setEnd (x, y) {
  this.__end = {x:x, y:y};
}

function drawPath (path) {
  this.__path = path;
}


exports.createMap = function (w, h, win) {
  var map = new Array(w * h);
  
  add_border(map, w);

  map.window = win;
  map.width = w;
  map.height = h;
  map.draw = draw;
  map.toggleCollision = toggleCollision;
  map.setStart = setStart;
  map.setEnd = setEnd;
  map.__start = false;
  map.__end = false;
  map.__path = false;
  map.__heuristicName = 'diagonal'; //astar start
  map.drawPath = drawPath;
  
  return map;
};

pathfinding.js

exports.Node = function (x, y) {
  this.x = x;
  this.y = y;
  
  this.f = 0;
  this.g = 0;
  this.h = 0;

  this.walkable = true;
  this.parent = null;
};


exports.Grid = function (numCols, numRows, map) {
  var i, j;
  
  this.numCols = numCols;
  this.numRows = numRows;
  this.nodes = [];
  this.startNode = null;
  this.endNode = null;

  for (i = 0; i < numCols; i++) {
    this.nodes[i] = [];
    for (j = 0; j < numRows; j++) {
      this.nodes[i][j] = new exports.Node(i, j);
    }
  }

  if (map) {
    i = map.length;
    while (i--) {
      if (map[i] === 1) {
        this.nodes[i % numCols][(i / numCols) | 0].walkable = false;
      }
    }
  }
};

exports.Grid.prototype = Object.create({}, {
  'getNode': {
    value: function (x, y) {
      return this.nodes[x][y];
    }
  },
  'setWalkable': {
    value: function (x, y, value) {
      this.nodes[x][y].walkable = value;
    }
  },
  'setStartNode': {
    value: function (x, y) {
      this.startNode = this.nodes[x][y];
    }
  },
  'setEndNode': {
    value: function (x, y) {
      this.endNode = this.nodes[x][y];
    }
  }
});


exports.AStar = function () {
  this.straightCost = 1.0;
  this.diagCost = Math.SQRT2;
  //this.diagCost = 1.0;
  this.heuristic = this.diagonal;
};

exports.AStar.prototype = Object.create({}, {
  'findPath': {
    value: function (grid) {
      this.grid = grid;
      this.open = [];
      this.closed = [];

      this.startNode = this.grid.startNode;
      this.endNode = this.grid.endNode;

      this.startNode.g = 0;
      this.startNode.h = this.heuristic(this.startNode);
      this.startNode.f = this.startNode.g + this.startNode.h;

      return this.search();
    }
  },

  'buildPath': {
    value: function () {
      var node = this.endNode;
      this.path = [];
      this.path.push(node);
      while (node !== this.startNode) {
        node = node.parent;
        this.path.unshift(node);
      }
    }
  },

  'search': {
    value: function () {
      var i, j, startX, endX, startY, endY, test, cost, g, h, f,
          node = this.startNode;
      
      while (node !== this.endNode) {
        startX = Math.max(0, node.x - 1);
        endX = Math.min(this.grid.numCols - 1, node.x + 1);
        startY = Math.max(0, node.y - 1);
        endY = Math.min(this.grid.numRows - 1, node.y + 1);

        for (i = startX; i <= endX; i++) {
          for (j = startY; j <= endY; j++) {
            
            test = this.grid.getNode(i, j);
            if (test === node || !test.walkable) {
              continue;
            }
            cost = this.straightCost;
            if (!((node.x === test.x) || (node.y === test.y))) {
              cost = this.diagCost;
            }
            g = node.g + cost;
            h = this.heuristic(test);
            f = g + h;

            if (this.isOpen(test) || this.isClosed(test)) {
              if (test.f > f) {
                test.f = f;
                test.g = g;
                test.h = h;
                test.parent = node;
              }
            } else {
              test.f = f;
              test.g = g;
              test.h = h;
              test.parent = node;
              this.open.push(test);
            }
          }
        }
        this.closed.push(node);
        if (this.open.length === 0) {
          return false; //no path found
        }
        this.open.sort(function (a, b) {
          return a.f - b.f;
        });
        node = this.open.shift();
      }
    }
  },

  'isOpen': {
    value: function (node) {
      var i = 0;
      for (; i < this.open.length; i++) {
        if (this.open[i] === node) {
          return true;
        }
      }
      return false;
    }
  },

  'isClosed': {
    value: function (node) {
      for (var i = 0; i < this.closed.length; i++) {
        if (this.closed[i] === node) {
          return true;
        }
      }
      return false;
    }
  },

  'visited': {
    get: function () {
      return this.closed.concat(this.open);
    }
  },

  /*
   * heuristics
   */
  
  'manhattan': {
    value: function (node) {
      return (Math.abs(node.x - this.endNode.x) * this.straightCost +
              Math.abs(node.y + this.endNode.y) * this.straightCost);
    }
  },

  'euclidian': {
    value: function (node) {
      var dx = node.x - this.endNode.x,
          dy = node.y - this.endNode.y;
      return (Math.sqrt(dx * dx + dy * dy) * this.straightCost);
    }
  },
  
  'diagonal': {
    value: function (node) {
      var dx = Math.abs(node.x - this.endNode.x),
          dy = Math.abs(node.y - this.endNode.y),
          diag = Math.min(dx, dy),
          straight = dx + dy;
      return (this.diagCost * diag +
              this.straightCost * (straight - 2 * diag));
    }
  }
  
});

ui.js

var ncurses = require('ncurses'),
    utils = require('./utils'),
    root = new ncurses.Window();

utils.logWindow = root;


exports.windows = {
  root: root
};



process.on('SIGINT', function () {
  root.close();
  process.exit(130);
});

utils.js

var fs = require('fs'),
    logfile = null;

exports.logWindow = null;

Object.defineProperties(exports, {
  
  'logFile': {
    get: function () { return logfile; },
    set: function (filename) {
      if (logfile && filename === null) {
        logfile.end();
        logfile = null;
      } else {
        if (logfile) {
          logfile.end();
        }
        logfile = fs.createWriteStream(filename, {'flags': 'a'});
        
        logfile.on('error', function (e) {
          console.log("utils.log_file: Error with log file.");
          
          if (exports.logWindow) {
            exports.logWindow.close();
          }
          throw e;
        });
      }
    }
  }
});

/**
 * @param {string}  message
 */
function log_to_file (msg) {
  logfile.write(msg + "\n");
}

/**
 * node.js bug: error being emitted twice, once on process.error and process.close
 * @param   {Error} err
 * @throws  {Error}
 */
exports.error = function (err) {
  if (exports.logWindow) {
    exports.logWindow.close();
  }
  if (logfile) {
    log_to_file(err.name + ": " + err.message);
  }
  throw err;
};


/**
 * If exports.logfile is set, monitor in console: 'tail -F logfile'
 * @param {string}    msg
 * @param {object=}   opts={x:0, y:0}
 * @this  {ui.Window}
 */
exports.log = function (msg /*, args..., opts*/) {
  var window = (this.window) ? this.window : exports.logWindow,
      args = Array.prototype.slice.call(arguments),
      opts = (args[args.length-1] && typeof args[args.length-1] === 'object') ? args.pop() : {};
  
  msg = args.join(' ');
  
  if (logfile) {
    log_to_file(msg);
  }
  
  if (window) {
    check_log_options(opts);
    window.cursor(opts.y, opts.x);
    if (opts.clear) {
      window.clrtoeol();
    }
    window.addstr(opts.y, opts.x, opts.prompt + msg);
    //window.refresh();
    
  } else {
    //when all else fails, just throw it somewhere
    console.log(msg);
  }
};

function check_log_options (options) {
  if (options.x === undefined) { options.x = 0; }
  if (options.y === undefined) { options.y = 0; }
  if (options.clear === undefined) { options.clear = true; }
  if (options.prompt === undefined) { options.prompt = "> "; }
  
  if (typeof options.x !== 'number' || typeof options.y !== 'number') {
    exports.error(new SyntaxError("utils.log: Invalid window position."));
  }
  return options;
}