astar.js

search: function(unit, grid, start, end, heuristic) {
            astar.init(grid);
            heuristic = heuristic || astar.manhattan;
            var openHeap = astar.heap();

            start.hexes = 0;

            openHeap.push(start);

            while(openHeap.size() > 0) {

                // Grab the lowest f(x) to process next.  Heap keeps this sorted for us.
                var currentNode = openHeap.pop();

                // End case -- result has been found, return the traced path.
                if(currentNode === end) {
                    var curr = currentNode;
                    var ret = [];
                    while(curr.parent) {
                        ret.push(curr);
                        curr = curr.parent;
                    }
                    return ret.reverse();
                }

                // Normal case -- move currentNode from open to closed, process each of its neighbors.
                currentNode.closed = true;

                // Find all neighbors for the current node
                var neighbors = this.neighbors(unit, grid, currentNode);
//                var neighborIntersectionWalls = this.neighborIntersectionWalls(grid, currentNode);
                for(var i=0, il = neighbors.length; i < il; i++) {
                    var neighbor = neighbors[i];
                    if(neighbor.closed || neighbor.isWall()) {
                        // Not a valid node to process, skip to next neighbor.
                        continue;
                    }

                    // The g score is the shortest distance from start to current node.
                    // We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.
                    var gScore = currentNode.g + neighbor.cost;
                    var beenVisited = neighbor.visited;

                    if(!beenVisited || gScore < neighbor.g) {

                        // Found an optimal (so far) path to this node.  Take score for node to see how good it is.
                        neighbor.visited = true;
                        neighbor.parent = currentNode;
                        neighbor.h = neighbor.h || heuristic(neighbor.pos, end.pos);
                        neighbor.g = gScore;
                        neighbor.hexes = currentNode.hexes + 1;

                        neighbor.f = neighbor.g + neighbor.h + currentNode.hexes;

                        
                        if (!beenVisited) {
                            // Pushing to heap will put it in proper place based on the 'f' value.
                            openHeap.push(neighbor);
                        }
                        else {
                            // Already seen the node, but since it has been rescored we need to reorder it in the heap
                            openHeap.rescoreElement(neighbor);
                        }
                    }
                }
            }

            // No result was found - empty array signifies failure to find path.
            return [];
        },