A* Path Finding

astar.js

String.prototype.replaceAt=function(index, char) {
  return this.substr(0, index) + char + this.substr(index+char.length);
};
var Point = function(x,y, parent) {
    this.x = x;
    this.y = y;
    this.cost = 0;
    this.moveCost = 0;
    this.goalCost = 0;
    this.parent = parent === undefined ? null : parent;
    this.adjacentToParent = this.parent != null && (this.x == this.parent.x || this.y == this.parent.y);
    
    // See if we can reach this node easier through a different parent
    this.checkForBetterPath = function(point) {
        var adjacentToItem = this.x == point.x || this.y == point.y;
        var newCost = point.moveCost + adjacentToItem  ? 10 : 14;
        if(newCost > this.moveCost) {
            this.moveCost = newCost;
            this.parent = parent;
            this.cost = this.moveCost + this.goalCost;
        }
    };
        
    // Calculate move costs
    this.calculateCost = function(goal){
        this.moveCost = this.parent.moveCost  + this.adjacentToParent ? 10 : 14;
        this.goalCost = Math.abs(goal.x-this.x) + Math.abs(goal.y-this.y);
        this.cost = this.moveCost + this.goalCost;
    };
        
    // Does a point equal another
    this.equals = function(point) {
        return point.x == this.x && point.y == this.y;
    };
    
    return this;
};

function aStar(level) {
    this.open = [];
    this.closed = [];
    this.goal = new Point(0,0);
    this.finished = false;
    
    // Load the level string and find start, destination
    this.initLevel = function(level) {
        for(var row=0;row<level.length;row++) {
            // Find destination point
            var index = level[row].indexOf('o');
            if(index != -1) {
                this.goal.x = index;
                this.goal.y = row;
            }
            // Find start point
            index = level[row].indexOf('x');
            if(index != -1) this.open.push(new Point(index, row));
        }
    };
    
    // Find the next closest tile in the open list and move it to closed
    this.getNextClosest = function() {
        var min = 999;
        var index = -1;
        for(var i=0;i<this.open.length;i++) {
            if(this.open[i].cost < min) {
                index = i;
                min = this.open[i].cost;
            }
        }
        if(index != -1)  {
            var item = this.open[index];
            this.open.splice(index, 1);
            this.closed.push(item);
            return item;
        }
        return null;
    };
    
    // Get an array of adjacent points
    this.findAdjacent = function(node) {
        var arr = [];
        var minx = node.x-1 >= 0 ? node.x-1 : 0;
        var maxx = node.x+1 <= level[0].length-1 ? node.x+1 : level[0].length-1;
        var miny = node.y-1 >= 0 ? node.y-1 : 0;
        var maxy = node.y+1 <= level.length-1 ? node.y+1 : level.length-1;
        for(var x=minx;x<=maxx;x++) {
            for(var y=miny;y<=maxy;y++) {
                if((level[y].charAt(x) == ' ' || level[y].charAt(x) == 'o') && this.checkClosed(x,y) == null) {
                    var item = this.checkOpen(x,y);
                    if(item == null) {
                        item = new Point(x,y,node);
                        item.calculateCost(this.goal); 
                        this.open.push(item);
                    } else {
                        item.checkForBetterPath(node);
                    }
                }
            }
        }
    };
    
    // Check if an item is already in the open queue
    this.checkOpen = function(x,y) {
        for(var i=0;i<this.open.length;i++) {
            if(this.open[i].x == x && this.open[i].y == y) return this.open[i];
        }
        return null;
    };
    
    // Check if an item is already in the closed queue
    this.checkClosed = function(x,y) {
        for(var i=0;i<this.closed.length;i++) {
            if(this.closed[i].x == x && this.closed[i].y == y) return this.closed[i];
        }
        return null;
    };    
    
    this.initLevel(level);
    
    var count = 0;
    while(!this.finished) {
        var current = this.getNextClosest(current);
        if(current != null && !current.equals(this.goal)) this.findAdjacent(current);
        else this.finished = true;
    };
    
    return this.closed;
};

var level = [
    "  #      #          #      ",
    "  #   #  #   o  #          ",
    "      #  ################# ",
    "               #           ",
    " x                 #       "
];  

var path = new aStar(level);

var target = path[path.length-1];
while(target.parent != null) {
    if(level[target.parent.y].charAt(target.parent.x) == ' ')
        level[target.parent.y] = level[target.parent.y].replaceAt(target.parent.x,'.');
    target = target.parent;
};

var html = '';
for(var i=0;i<level.length;i++) {
   html += '<div>'+level[i].replace(/ /g,'&nbsp;')+'</div>';
};