A* Algorithm on a Quest

An implementation of the A* algorithm to work out a path between 2 points in a canvas.

by sperske

HTML

<input id='ImageURL' placeholder='data URI' value='data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAUAAAADIBAMAAABrKiWYAAAALVBMVEUAAAAAAKqqAABVVVWqVQBVVf//VVUAqqqZmZmqqqq7u7v/tf9V/1X//1X///+6ngltAAAAAXRSTlMAQObYZgAAAAFiS0dEAIgFHUgAAAAJcEhZcwAACxMAAAsTAQCanBgAAAAHdElNRQfeChYRBBZWfn4PAAABUklEQVR42u3YQXKDIBSAYU7Qc/csnKrrLjhDpulGG6NEAjw737909Y3AyDMlSZIkSZIkSZIkSZIkSZIkSZIkSZIkScMri6L7IhIL4Ht90YRlq6/gvkDAch74uWqsLwywPA2w0RcDmP/08+yjntgdmPeBhyelN3DTFwiYt4HLjRkMmGIBc3Dgc1/97bUncMe3PieTgDk4cN83H5gPgLVD3kjgqSmvFzC/DCxDgRW+yn3YB1jnmwfMlcD1Ok8GposC09EqjwKe/uc1H7gkzgPWTlXhgY/XwyF/Fl4ZTEMC087Y/Ah83AxHS9R1tq8Z+vsDG4UDgG3CEcAmIWCrcAww/UdgCQ8sI4Hn3+EwYAoPPCHM4YEV97mpTEBAwDphYOB3dOCvMDLwvsqjLCe/J/2E5T1dAZhDA+8HBbC58MACGFAJCAgICAgICHhtoCRJkiRJF+8GflbQQ/MmfKEAAAAASUVORK5CYII='/> <button id='LoadImage'>Parse</button><br/>

<code>Click on any 2 points on white spaces and a path will be drawn</code>
<canvas id='field' height
    
='200' width='320'></canvas>
<textarea id='Graph' wrap='off'></textarea>

CSS

#field {
border: thin black solid;
    width: 98%;
    background: #FFFFC7;
}
#Graph {
    width: 98%;
    height: 300px;
    overflow-y: auto;
}

JavaScript

// javascript-astar 0.3.0
// http://github.com/bgrins/javascript-astar
// Freely distributable under the MIT License.
// Implements the astar search algorithm in javascript using a Binary Heap.
// Includes Binary Heap (with modifications) from Marijn Haverbeke.
// http://eloquentjavascript.net/appendix2.html

(function(definition) {
    /* global module, define */
    if(typeof module === 'object' && typeof module.exports === 'object') {
        module.exports = definition();
    } else if(typeof define === 'function' && define.amd) {
        define([], definition);
    } else {
        var exports = definition();
        window.astar = exports.astar;
        window.Graph = exports.Graph;
    }
})(function() {

function pathTo(node){
    var curr = node,
        path = [];
    while(curr.parent) {
        path.push(curr);
        curr = curr.parent;
    }
    return path.reverse();
}

function getHeap() {
    return new BinaryHeap(function(node) {
        return node.f;
    });
}

var astar = {
    init: function(graph) {
        for (var i = 0, len = graph.nodes.length; i < len; ++i) {
            var node = graph.nodes[i];
            node.f = 0;
            node.g = 0;
            node.h = 0;
            node.visited = false;
            node.closed = false;
            node.parent = null;
        }
    },

    /**
    * Perform an A* Search on a graph given a start and end node.
    * @param {Graph} graph
    * @param {GridNode} start
    * @param {GridNode} end
    * @param {Object} [options]
    * @param {bool} [options.closest] Specifies whether to return the
               path to the closest node if the target is unreachable.
    * @param {Function} [options.heuristic] Heuristic function (see
    *          astar.heuristics).
    */
    search: function(graph, start, end, options) {
        astar.init(graph);

        options = options || {};
        var heuristic = options.heuristic || astar.heuristics.manhattan,
            closest = options.closest ||...