app.js

var CELL_SIZE = 30,
    MAP_SIZE = 20,
    VISUAL_FRAME_COUNT = 10,
    INFINITY = Infinity,
    MAP = [
        [2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3],
    ],
    SolverClass = DStarLiteSolver, solver;

var canvas = CE.defines("canvas_id").
    extend(Animation).
    extend(Text).
    ready(function() {
        canvas.Scene.call("MyScene");
    });
function startOver() {
    canvas.Scene.call("MyScene");
}
canvas.Scene.new({
    name: "MyScene",
    ready: function(stage) {
        this.solver = new SolverClass();
        this.clock = 0;
        this.tileMap = new TileMap();
        this.tileMap.addToStage(stage, this);
        this.solver.solveFor(this.tileMap);
    },
    render: function(stage) {
        var scene = this;
        if(!(this.clock++ % VISUAL_FRAME_COUNT)) {
            console.log("ticking");
            this.solver.step();
        }
        d2foreach(this.tileMap.tiles, function(tile, x, y) {
            if(tile.goal) {
                tile.el.fillStyle = "green";
                tile.el.fillRect();
            }
            else if(tile.obstacle) {
                tile.el.fillStyle = "black";
                tile.el.fillRect();
            }
            else if(tile.state == "head" || scene.solver.current == tile) {
                tile.el.fillStyle = "red";
                tile.el.fillRect();
            }
            else if(tile.state == "current") {
                tile.el.fillStyle = "magenta";
                tile.el.fillRect();
            }
            else {
                tile.el.fillStyle = "white";
                tile.el.fillRect();
                tile.el.strokeRect();
            }
        });
        stage.refresh();
    },
    exit: function(stage) {
    
    }
});

function TileMap() {
    this.construct()
}

function d2array(size, obj) {
    var tiles = [];
    for(var i = 0; i < size; i++) {
        var row = [];
        for(var j = 0; j < size; j++) {
            var tile = new obj();
            row.push(tile);
        }
        tiles.push(row);
    }
    return tiles;
}

function d2foreach(arr, fn) {
    for(var i = 0; i < arr.length; i++) {
        for(var j = 0; j < arr.length; j++) {
            fn(arr[i][j], i, j);
        }
    }
}

TileMap.prototype.construct = function(stage) {
    this.tiles = d2array(MAP_SIZE, Tile);
    this.setMap(MAP);
}

TileMap.prototype.setMap = function(map) {
    d2foreach(this.tiles, function(tile, x, y) {
        tile.x = x;
        tile.y = y;
        tile.obstacle = map[y][x] == 1;
        tile.start = map[y][x] == 2;
        tile.goal = map[y][x] == 3;
    });
}

TileMap.prototype.addToStage = function(stage, scene) {
    d2foreach(this.tiles, function(tile, x, y) {
        tile.el = scene.createElement(CELL_SIZE, CELL_SIZE);
        tile.el.x = x * CELL_SIZE;
        tile.el.y = y * CELL_SIZE;
        tile.el.on("click", function() {
            tile.obstacle = !tile.obstacle;
        });
        stage.append(tile.el);
    });
}

function Tile() {
    this.f_score = 0;
    this.g_score = 0;
    this.open = false;
    this.closed = false;
}

Tile.prototype.toString = function() {
    return this.x + "x" + this.y;
}

function N() {
    this.isnode = true;
    this.visited = false;
}

function DStarLiteSolver() {
    var solver = this, U, g, rhs, sStart, sGoal, km, kold, obstacleMapCopy;
    function heuristic(from, to) {
        var x = to.x - from.x,
            y = to.y - from.y;
        if(!to) return INFINITY;
        return x + y;
    }
    function calculateKey(s) {
        mingrhs = Math.min(g[s], rhs[s])
        return [mingrhs + heuristic(sStart, s) + km, mingrhs]
    }
    function initialize() {
        U = minHeap(calculateKey)
        km = 0
        rhs = {};
        g = {}
        d2foreach(solver.map.tiles, function(tile, x, y) {
            rhs[tile] = g[tile] = INFINITY;
        })
        rhs[sGoal] = 0;
        U.push(sGoal);
    }
    function cellAt(x, y) {
        if(x < 0 || x >= MAP_SIZE || y < 0 || y >= MAP_SIZE) return;
        return solver.map.tiles[x][y];
    }
    function updateVertex(u) {
        if(!u) return;
        if(u != sGoal) {
            neigbors = []
            rhs[u] = Math.min(costpg(u, cellAt(u.x-1, u.y)),
                              costpg(u, cellAt(u.x+1, u.y)),
                              costpg(u, cellAt(u.x, u.y-1)),
                              costpg(u, cellAt(u.x, u.y+1)));
        }
        U.remove(u);
        if(g[u] != rhs[u]) {
            U.push(u);
        }
    }
    function computeShortestPath() {
        var u;
        while (U.topKey() < calculateKey(sStart) || rhs[sStart] != g[sStart]) {
            kold = U.topKey();
            u = U.pop();
            if (kold < calculateKey(u)) {
                U.push(u);
            }
            else if(g[u] > rhs[u]) {
                g[u] = rhs[u];
                updateVertex(cellAt(u.x-1, u.y));
                updateVertex(cellAt(u.x+1, u.y));
                updateVertex(cellAt(u.x, u.y-1));
                updateVertex(cellAt(u.x, u.y+1));
            }
            else {
                g[u] = INFINITY;
                updateVertex(u);
                updateVertex(cellAt(u.x-1, u.y));
                updateVertex(cellAt(u.x+1, u.y));
                updateVertex(cellAt(u.x, u.y-1));
                updateVertex(cellAt(u.x, u.y+1));
            }
        }
    }
    function main() {
        sLast = sStart;
        initialize();
        computeShortestPath();
    }
    function cost(from, to) {
        return !to || obstacleMapCopy[to.x][to.y].obstacle ? INFINITY : 1;
    }
    function costpg(from, to) {
        return !to || obstacleMapCopy[to.x][to.y].obstacle ? INFINITY : 1 + g[to];
    }
    function tryForEdge(from, to) {
        if(!to) return;
        // if any edge costs has changed
        if(obstacleMapCopy[to.x][to.y].obstacle ^ cellAt(to.x, to.y).obstacle) {
            console.log("found discrepancy");
            km = km + heuristic(sLast, sStart);
            sLast = sStart;
            // for all directed edges (u, v) with changed edge costs
            obstacleMapCopy[to.x][to.y].obstacle = cellAt(to.x, to.y).obstacle;
            updateVertex(from)
            computeShortestPath()
        }
    }
    function step() {
        if(sStart == sGoal) 
            return;
        /* if g(sStart) = infinity then there is no known path */
        // sStart =  min neighbor with c(sStart, neighbor) + g(neighbor)
        var neighbors = [[costpg(sStart, cellAt(sStart.x-1, sStart.y)), cellAt(sStart.x-1, sStart.y)],
                         [costpg(sStart, cellAt(sStart.x+1, sStart.y)), cellAt(sStart.x+1, sStart.y)],
                         [costpg(sStart, cellAt(sStart.x, sStart.y-1)), cellAt(sStart.x, sStart.y-1)],
                         [costpg(sStart, cellAt(sStart.x, sStart.y+1)), cellAt(sStart.x, sStart.y+1)]];
        sStart = neighbors.sort()[0][1]
        // move to sStart
        solver.current = sStart;
        // scan graph for changed edge costs
        tryForEdge(sStart, cellAt(sStart.x-1, sStart.y));
        tryForEdge(sStart, cellAt(sStart.x+1, sStart.y));
        tryForEdge(sStart, cellAt(sStart.x, sStart.y-1));
        tryForEdge(sStart, cellAt(sStart.x, sStart.y+1));
    }
    function solveFor(map) {
        solver.map = map;
        obstacleMapCopy = d2array(MAP_SIZE, N);
        d2foreach(map.tiles, function(tile, x, y) {
            obstacleMapCopy[x][y].obstacle = tile.obstacle;
            if(tile.start)
                sStart = tile;
            if(tile.goal)
                sGoal = tile;
        })
        main();
    }
    this.step = step;
    this.solveFor = solveFor;
}

function AStarSolver() {
    var solver = this;
    solver.state = "solving";
    solver.parents = d2array(MAP_SIZE, N);
    solver.visited = d2array(MAP_SIZE, N);
    solver.frontier = minHeap(function(a) { return a.f_score; }, function(a, b) { return a - b; });
}

AStarSolver.prototype.finishSolving = function () {
    this.state = "found";
    this.markPath(this.current);
}

AStarSolver.prototype.startSolving = function () {
    this.state = "solving";
}

AStarSolver.prototype.heuristic = function (tile) {
    var solver = this,
        x = Math.abs(tile.x - solver.goal.x),
        y = Math.abs(tile.y - solver.goal.y);

    return (x + y);
}

AStarSolver.prototype.solveFor = function (map) {
    var solver = this;
    solver.map = map;
    d2foreach(map.tiles, function(tile, x, y) {
        if(tile.start)
            solver.start = tile;
        if(tile.goal)
            solver.goal = tile;
    })

    solver.current = solver.start;
    solver.current.g_score = 0;
    solver.current.f_score = solver.current.g_score + solver.heuristic(solver.current);
    solver.current.open = true;
    solver.frontier.push(solver.current);
    solver.prepareStep();
}

AStarSolver.prototype.prepareStep = function() {
    var solver = this, c;
    d2foreach(solver.map.tiles, function(tile, x, y) {
        tile.state = "none";
    });
}

AStarSolver.prototype.step = function() {
    var solver = this, c;
    if(solver.state !== "solving")
        return;
    if(solver.current === solver.goal){
        solver.finishSolving()
        return;
    }
    solver.prepareStep();
    d2foreach(solver.map.tiles, function(tile, x, y) {
        tile.state = "none";
    });


    solver.current = solver.frontier.pop();
    c = solver.current;
    c.open = false;
    c.closed = true;
    solver.markPath(solver.current);
    solver.current.state = "head";

    solver.exploreCell(c, c.x - 1, c.y);
    solver.exploreCell(c, c.x + 1, c.y);
    solver.exploreCell(c, c.x, c.y - 1);
    solver.exploreCell(c, c.x, c.y + 1);
}

AStarSolver.prototype.exploreCell = function(p, x, y) {
    var solver = this, c, tentative_g_score;
    if(x < 0 || x >= MAP_SIZE || y < 0 || y >= MAP_SIZE) return;
    c = solver.map.tiles[x][y];
    if(c.obstacle || c.closed) return;
    tentative_g_score = p.g_score + 1;
    if(!c.open || tentative_g_score < c.g_score) {
        solver.parents[x][y] = p;
        c.g_score = tentative_g_score;
        c.f_score = c.g_score + solver.heuristic(c);
        if(c.open) {
            solver.frontier.remove(c);
        }
        c.open = true;
        solver.frontier.push(c);
    }
}

AStarSolver.prototype.markPath = function(from) {
    var solver = this, c = from;
    while(true) {
        c.state = "current";
        p = solver.parents[c.x][c.y];
        if(p.isnode) break;
        c = p;
    }
}

AStarSolver.prototype.exploreFrontier = function() {
    
}

function minHeap(priority) {
    var heap = {},
    entry_finder = {},
    array = [],
    counter = 0,
    size = 0;

    heap.topKey = function() {
        if (size <= 0) return;
        return array[0].priority;
    }

    heap.empty = function() {
        return !size;
    };

    heap.push = function(value) {
        heap.remove(value);
        up(array[size] = make_entry(value), size++);
        return size;
    };

    heap.pop = function() {
        var removed = null, entry;
        while(!removed) {
            if (size <= 0) return;
            removed = array[0].value;
            if (--size > 0) entry = array[size], down(array[0] = entry, 0);
        }
        return removed;
    };

    heap.remove = function(value) {
        if(entry_finder[valueId(value)])
            entry_finder[valueId(value)].value = null;
    }

    function valueId(value) {
        return value.x + "x" + value.y;
    }

    function make_entry(value) {
        var entry = {
            value: value,
            priority: priority(value),
            count: counter++
        };
        entry_finder[valueId(value)] = entry;
        return entry;
    }

    function up(entry, i) {
        while (i > 0) {
            var j = ((i + 1) >> 1) - 1,
                parent = array[j];
            if (entry.priority > parent.priority) break;
            array[i] = parent;
            array[i = j] = entry;
        }
    }

    function down(entry, i) {
        while (true) {
            var r = (i + 1) << 1,
                l = r - 1,
                j = i,
                    child = array[j];
            if (l < size && array[l].priority < child.priority) child = array[j = l];
            if (r < size && array[r].priority < child.priority) child = array[j = r];
            if (j === i) break;
            array[i] = child;
            array[i = j] = entry;
        }
    }

    return heap;
}

index.html

<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <!-- The above 3 meta tags *must* come first in the head; any other head content must come *after* these tags -->
        <title>D* Lite experiments</title>

        <!-- Bootstrap -->
        <link href="bootstrap/css/bootstrap.min.css" rel="stylesheet">
        <link href="app.css" rel="stylesheet">


        <!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
        <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
        <!--[if lt IE 9]>
            <script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
            <script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
            <![endif]-->
    </head>
    <body>
        <div class="container">
            <div class="header clearfix">
                <nav>
                    <ul class="nav nav-pills pull-right">
                        <li role="presentation" class="active"><a href="#">Home</a></li>
                        <li role="presentation"><a href="#">About</a></li>
                    </ul>
                </nav>
                <h3 class="text-muted">D* Lite Experiments</h3>
            </div>
            <script src="http://canvasengine.net/cdn/canvasengine-latest.all.min.js"></script>
            <canvas id="canvas_id" width="700" height="600"></canvas>
        </div>

        <!-- jQuery (necessary for Bootstrap's JavaScript plugins) -->
        <!-- <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.2/jquery.min.js"></script> -->
        <!-- Include all compiled plugins (below), or include individual files as needed -->
        <!-- <script src="bootstrap/js/bootstrap.min.js"></script> -->
        <script src="http://d3js.org/d3.v3.min.js"></script>
        <script src="app.js"></script>
    </body>
</html>