[nodejs][javascript]A* with Jump Point Search

astar.js

// A* with Jump Point Search on JavaScript
// - python A*: https://gist.github.com/bellbind/147645

// utility: Priority Queue
var PQ = function PQ() {
    return Object.create(PQ.prototype, {
        array: {value: []},
    });
};
PQ.prototype.empty = function () {
    return this.array.length === 0;
};
PQ.prototype.push = function (score, item) {
    for (var i = 0; i < this.array.length; i++) {
        if (score < this.array[i].score) {
            this.array.splice(i, 0, {score:score, item: item});
            return;
        }
    }
    this.array.push({score: score, item: item});
};
PQ.prototype.pop = function () {
    return this.array.shift();
};

// utility: array map
var AMap = function AMap(equals) {
    equals = equals || function (a, b) {
        return a === b;
    };
    return Object.create(AMap.prototype, {
        equals: {value: equals},
        keys: {value: []},
        values: {value: []},
    });
}
AMap.prototype.set = function (key, value) {
    for (var i = 0; i < this.keys.length; i++) {
        if (this.equals(key, this.keys[i])) return this.values[i] = value;
    }
    this.keys.push(key);
    return this.values.push(value);
};
AMap.prototype.get = function (key, defaultValue) {
    for (var i = 0; i < this.keys.length; i++) {
        if (this.equals(key, this.keys[i])) return this.values[i];
    }
    return defaultValue;
};
AMap.prototype.has = function (key) {
    for (var i = 0; i < this.keys.length; i++) {
        if (this.equals(key, this.keys[i])) return true;
    }
    return false;
};

// A* algorithm
var astar = function (env) {
    // env.start: pos, env.goal: pos
    // env.equals: (a:pos, b:pos)->bool
    // env.cost: ([pos])->num
    // env.heulistic: (pos)->num
    // env.nexts: ([pos])->[pos]
    var queue = PQ();
    var scores = AMap(env.equals);
    var init = [env.start];
    var initScore = env.cost(init) + env.heulistic(env.start);
    queue.push(initScore, init);
    scores.set(env.start, initScore);
    while (!queue.empty()) {
        var path = queue.pop().item;
        var last = path[path.length - 1];
        if (env.equals(env.goal, last)) return path;
        env.nexts(path).forEach(function (next) {
            var nextPath = path.concat([next]);
            var score = env.cost(nextPath) + env.heulistic(next);
            if (scores.has(next) && scores.get(next) <= score) return;
            scores.set(next, score);
            queue.push(score, nextPath);
        });
    }
    return null;
};


// dungeon map
var Pos = function Pos(x, y) {
    return {x: x, y: y};
};
Pos.equals = function (a, b) {
    return a.x === b.x && a.y === b.y;
};
Pos.distance = function (a, b) {
    return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
};
var Map = function Map(data) {
    return Object.create(Map.prototype, {
        data: {value: data},
    });
};
Map.prototype.find = function (ch) {
    for (var y = 0; y < this.data.length; y++) {
        var line = this.data[y];
        for (var x = 0; x < line.length; x++) {
            if (line[x] == ch) return Pos(x, y);
        }
    }
    return null;
};
Map.prototype.neighbors = function (pos) {
    var px = pos.x, py = pos.y;
    return [
        Pos(px - 1, py - 1), Pos(px + 0, py - 1), Pos(px + 1, py - 1),
        Pos(px - 1, py + 0), /*Pos(px+0, py+0),*/ Pos(px + 1, py + 0),
        Pos(px - 1, py + 1), Pos(px + 0, py + 1), Pos(px + 1, py + 1),
    ].filter(function (pos) {return !this.wall(pos.x, pos.y);}.bind(this));
};
Map.prototype.render = function (path) {
    var buf = this.data.map(function (line) {
        return line.split("");
    });
    var first = path[0];
    var last = path[path.length - 1];
    path.slice(1, path.length - 1).forEach(function (pos) {
        buf[pos.y][pos.x] = "*";
    });
    buf[last.y][last.x] = "g";
    buf[first.y][first.x] = "s";
    return buf.map(function (line) {
        return line.join("");
    });
};
Map.prototype.wall = function (x, y) {
    return !this.data[y] || !this.data[y][x] || this.data[y][x] === "O";
};

var AStarEnv = function (map) {
    var env = {
        start: map.find("S"), goal: map.find("G"),
        equals: Pos.equals,
        cost: function (path) {
            var dist = 0;
            for (var i = 1; i < path.length; i++) {
                dist += Pos.distance(path[i - 1], path[i]);
            };
            return dist;
        },
        heulistic: function (head) {
            return Pos.distance(head, env.goal);
        },
        // original A* naive nexts
        nexts: function (path) {
            return map.neighbors(path[path.length - 1]);
        },
    };
    return env;
};


// nexts for Jump Point Search
// - http://harablog.wordpress.com/2011/09/07/jump-point-search/
var jps = function (map, env) {
    // jps depends on map and env.goal and env.equals
    var sign = function (a) {
        return a === 0 ? 0 : (a > 0 ? 1 : -1);
    };
    var push = function (ns, x, y) {
        if (!map.wall(x, y)) ns.push(Pos(x, y));
    };
    
    var forwards = function (current, parent) {
        if (!parent) return map.neighbors(current);
        var cx = current.x, cy = current.y;
        var px = parent.x, py = parent.y;
        var dx = sign(cx - px), dy = sign(cy - py);
        var fs = [];
        if (dx !== 0 && dy !== 0) { // forward diagonal
            push(fs, cx + dx, cy + dy);
            push(fs, cx + 0, cy + dy);
            push(fs, cx + dx, cy + 0);
            // when corner
            if (map.wall(cx - dx, cy)) push(fs, cx - dx, cy + dy);
            if (map.wall(cx, cy - dy)) push(fs, cx + dx, cy - dy);
            return fs;
        } else if (dy === 0) { // forward horizontal
            push(fs, cx + dx, cy);
            // when corner
            if (map.wall(cx, cy + 1)) push(fs, cx + dx, cy + 1);
            if (map.wall(cx, cy - 1)) push(fs, cx + dx, cy - 1);
            return fs;
        } else if (dx === 0) { // forward vertical
            push(fs, cx, cy + dy);
            // when corner
            if (map.wall(cx + 1, cy)) push(fs, cx + 1, cy + dy);
            if (map.wall(cx - 1, cy)) push(fs, cx - 1, cy + dy);
            return fs;
        }
        throw new Error("never reach");
    };

    var jump = function (forward, current) {
        var fx = forward.x, fy = forward.y;
        if (map.wall(fx, fy)) return null; // recursive call only check
        if (env.equals(env.goal, forward)) return forward;
        var cx = current.x, cy = current.y;
        var dx = sign(fx - cx), dy = sign(fy - cy);
        // return forward itself when it is turnable point
        if (dx !== 0 && dy !== 0) { // when diagonal
            // corner point itself
            if (map.wall(fx - dx, fy) && !map.wall(fx - dx, fy + dy)) {
                return forward;
            }
            if (map.wall(fx, fy - dy) && !map.wall(fx + dx, fy - dy)) {
                return forward;
            }
            // reached to corner with vertical/horizontal sides
            if (jump(Pos(fx, fy + dy), forward) !== null ||
                jump(Pos(fx + dx, fy), forward) !== null) {
                return forward;
            }
        } else if (dy === 0) { // when horizontal
            // corner point itself
            if (map.wall(fx, fy + 1) && !map.wall(fx + dx, fy + 1)) {
                return forward;
            }
            if (map.wall(fx, fy - 1) && !map.wall(fx + dx, fy - 1)) {
                return forward;
            }
        } else if (dx === 0) { // when vertical
            // corner point itself
            if (map.wall(fx + 1, fy) && !map.wall(fx + 1, fy + dy)) {
                return forward;
            }
            if (map.wall(fx - 1, fy) && !map.wall(fx - 1, fy + dy)) {
                return forward;
            }
        } else throw new Error("do not reach");
        // extend forward when it is not turnable point
        return jump(Pos(fx + dx, fy + dy), current);
    };
    
    var nexts = function (path) {
        //map.render(path).forEach(function (line) {console.log(line);});
        var current = path[path.length - 1];
        var parent = path[path.length - 2];
        var fs = forwards(current, parent);
        var ns = [];
        fs.forEach(function (forward) {
            var pos = jump(forward, current);
            if (pos) ns.push(pos);
        });
        return ns;
    };

    return nexts;
};

//[run]
// Setup environment for using A*
var map = Map([
    'OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO',
    'OS  O     O     O         O          O',
    'O   O  O  O  O  O         O    OOOO GO',
    'O      O     O  O   OOOO  O    O  OOOO',
    'OO OOOOOOOOOOOOOOO  O     O    O     O',
    'O                O  O     O          O',
    'O        OOO     O  O     OOOOOOOOO  O',
    'O  OO    O    OOOO  O     O      OO  O',
    'O   O    O          O     O  O   O   O',
    'O   OOO  O          O        O   O   O',
    'O        O          O        O       O',
    'OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO',
]);
var astarEnv = AStarEnv(map);
astarEnv.nexts = jps(map, astarEnv); // comment out it for normal A*
var path = astar(astarEnv);
console.log("[source]");
map.data.forEach(function (line) {console.log(line);});
//console.log(path);
console.log("[result]");
map.render(path).forEach(function (line) {console.log(line);});

run result

$ node astar.js 
[source]
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OS  O     O     O         O          O
O   O  O  O  O  O         O    OOOO GO
O      O     O  O   OOOO  O    O  OOOO
OO OOOOOOOOOOOOOOO  O     O    O     O
O                O  O     O          O
O        OOO     O  O     OOOOOOOOO  O
O  OO    O    OOOO  O     O      OO  O
O   O    O          O     O  O   O   O
O   OOO  O          O        O   O   O
O        O          O        O       O
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
[result]
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
Os  O     O     O         O    *  *  O
O * O  O  O  O  O   *  *  O   *OOOO*gO
O      O     O  O  *OOOO* O    O  OOOO
OO*OOOOOOOOOOOOOOO  O    *O   *O     O
O  *       *     O  O     O    *  *  O
O        OOO*    O *O     OOOOOOOOO* O
O  OO    O    OOOO* O     O **   OO  O
O   O    O    *  *  O    *O  O   O * O
O   OOO  O          O     *  O   O   O
O        O          O        O  **   O
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO