Plutor/A_star.html

## A_star.html
<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
    <title>A* demo</title>
    <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.js"></script>
    <script type="text/javascript">
        var size=81, fielddom, g, h;
        var zeroes, walls, open, clos, camefrom, lastwalls, lastopen, lastclos;
        var curx=Math.floor(size/2), cury=3;
        var active = 1;

        function init() {
            $("#field").remove();

            var cellid = 0;
            fielddom = $('<table id="field"></table>').appendTo('body');
            for (var y=0; y<size; y++) {
                var thisrow = $('<tr></tr>').appendTo(fielddom);
                for (var x=0; x<size; x++) {
                    var cell = $('<td id="cell' + (cellid++) + '">&nbsp;</td>')
                                    .appendTo(thisrow);
                }
            }

            $("#active").change( function() {
                active = $(this).is(":checked");
            });

            // Initialize state arrays
            zeroes = new Array(size*size);
            for (var i=0; i<size*size; ++i) zeroes[i] = 0;
            lastwalls = open = clos = lastopen = lastclos = zeroes;
            walls = zeroes.slice(0);

            update();
        }

        function update() {
            // TODO - Build a maze with Eller's algorithm instead?
            if (active) {
                if (cury >= 3) {
                    // Make a copy of the current state
                    lastwalls = walls.slice(0);

                    // Make a new bar
                    var barstart=-1, barend=-1;
                    if (Math.random() < 4/10) {
                        barstart = Math.floor(Math.random() * size);
                        barend = Math.floor(Math.random() * size);

                        if (barend < barstart) {
                            var temp = barend;
                            barend = barstart;
                            barstart = temp;
                        }
                    }

                    // Remove the top row
                    for (var i=0; i<size; ++i)
                        walls.shift();

                    // Add a new row
                    for (var x=0; x<size; x++) {
                        walls.push( x>=barstart && x<=barend ? 1 : 0 );
                    }

                    cury--;
                } else {
                    lastwalls = walls;
                }

                movetogoal()
                refreshfield();
            }

            setTimeout(update, 0);
        }

        function refreshfield() {
            // Show the field based on arrays
            var cellid = 0;
            var curcell = getcell(curx, cury);

            fielddom.find("tr").each( function(y, row) {
                $(row).find("td").each( function(x, cell) {
                    if (clos[cellid]) {
                      if (walls[cellid])
                        cell.className = "closedwall";
                      else
                        cell.className = "closed";
                    }
                    else if (walls[cellid])
                        cell.className = "wall";
                    else if (open[cellid])
                        cell.className = "open";
                    else
                        cell.className = "";

                    cellid++;
                } );
            } );

            fielddom.find("td.cur").removeClass("cur");
            $("#cell" + curcell).addClass("cur");
        }

        // This is A*!
        var cardcost = 10, diagcost = 14;
        var digmultiplier = size*0.8;  // Digging through a wall is expensive
        function movetogoal() {
            var nextcur = getnextmove();

            curx = nextcur % size;
            cury = Math.floor(nextcur / size);
        }
        function getnextmove() {
            // Save old state
            lastopen = open
            lastclos = clos

            // Make new state
            g = zeroes.slice(0);
            h = zeroes.slice(0);
            open = zeroes.slice(0);
            clos = zeroes.slice(0);
            camefrom = zeroes.slice(0);

            var openheap = new BinaryHeap(function(x){return g[x]+h[x];});
            var start = getcell(curx, cury);

            g[start] = 0;
            h[start] = heuristic(curx, cury);

            openheap.push(start);

            while (openheap.size() > 0) {
                var n = openheap.pop();

                // add n to closed set
                clos[n] = 1;
                open[n] = 0;

                // if n is goal, end and reconstruct path
                if ( Math.floor(n/size) == size-1 ) {
                    var nextcur = n;
                    while (n != start) {
                        nextcur = n;
                        n = camefrom[n];
                    }
                    return nextcur;
                }

                // check all of n's non-closed neighbors
                for (var dx=-1; dx<=1; ++dx) {
                    for (var dy=-1; dy<=1; ++dy) {
                        var x = (n % size) + dx;
                        var y = Math.floor(n/size) + dy;
                        if (x < 0 || x >= size || y < 0 || y >= size) continue;

                        var neighbor = getcell(x, y);
                        if (clos[neighbor] == 1) continue;

                        // calculate new g
                        oldg = g[neighbor];
                        newg = 0;
                        if (dx != 0 && dy != 0) newg += diagcost;
                        else newg += cardcost;

                        // if it's a wall, multiply the cost by dig multiplier
                        if (walls[neighbor]) {
                          newg *= digmultiplier;
                        }
                        newg += g[n];

                        // if g is better than old g, set it and new h, and set camefrom to n
                        if (isNaN(oldg) || oldg == 0 || newg < oldg) {
                            g[neighbor] = newg;
                            h[neighbor] = heuristic(x, y);
                            camefrom[neighbor] = n;

                            // add to open set
                            if (open[neighbor] != 1) {
                                open[neighbor] = 1;
                                openheap.push(neighbor);
                            }
                        }
                    }
                }
            }
        }
        function heuristic(fromx, fromy) {
            return (size-fromy) * cardcost;
        }

        function getcell(x, y) {
            return (y * size) + x;
        }

        $( init );
    </script>

    <style type="text/css">
        table#field {
            border-collapse: collapse;
        }
        table#field td {
            border: solid 1px #ccc;
            width: 10;
            height: 12;
            font-size: 1px;
        }
        table#field td.wall {
            background: blue;
        }
        table#field td.closedwall {
            background: #07f;
        }
        table#field td.cur {
            background: red !important;
        }
        table#field td.open {
            background: yellow;
        }
        table#field td.closed {
            background: cyan;
        }
    </style>

    <script type="text/javascript">
        // Binary heap implementation taken from
        //   <http://eloquentjavascript.net/appendix2.html>
        // and minified with Dean Edwards' Packer
        //   <http://jscompress.com/>

        eval(function(p,a,c,k,e,d){e=function(c){return(c<a?'':e(parseInt(c/a)))+((c=c%a)>35?String.fromCharCode(c+29):c.toString(36))};if(!''.replace(/^/,String)){while(c--){d[e(c)]=k[c]||e(c)}k=[function(e){return d[e]}];e=function(){return'\\w+'};c=1};while(c--){if(k[c]){p=p.replace(new RegExp('\\b'+e(c)+'\\b','g'),k[c])}}return p}('b x(6){3.4=[];3.6=6}x.D={u:b(8){3.4.u(8);3.k(3.4.9-1)},g:b(){5 v=3.4[0];5 d=3.4.g();7(3.4.9>0){3.4[0]=d;3.o(0)}m v},F:b(j){5 h=3.4.9;E(5 i=0;i<h;i++){7(3.4[i]==j){5 d=3.4.g();7(i!=h-1){3.4[i]=d;7(3.6(d)<3.6(j))3.k(i);q 3.o(i)}m}}B C L("N G M.")},H:b(){m 3.4.9},k:b(n){5 8=3.4[n];w(n>0){5 f=I.J((n+1)/2)-1,l=3.4[f];7(3.6(8)<3.6(l)){3.4[f]=8;3.4[n]=l;n=f}q{z}}},o:b(n){5 9=3.4.9,8=3.4[n],p=3.6(8);w(K){5 c=(n+1)*2,e=c-1;5 a=r;7(e<9){5 A=3.4[e],s=3.6(A);7(s<p)a=e}7(c<9){5 y=3.4[c],t=3.6(y);7(t<(a==r?p:s))a=c}7(a!=r){3.4[n]=3.4[a];3.4[a]=8;n=a}q{z}}}};',50,50,'|||this|content|var|scoreFunction|if|element|length|swap|function|child2N|end|child1N|parentN|pop|len||node|sinkDown|parent|return||bubbleUp|elemScore|else|null|child1Score|child2Score|push|result|while|BinaryHeap|child2|break|child1|throw|new|prototype|for|remove|not|size|Math|floor|true|Error|found|Node'.split('|'),0,{}))
    </script>

<body>
    <p><input type="checkbox" id="active" checked><label for="active">Run</label></p>
</body>

</html>
	<html><head>
	<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
	<title>A* demo</title>
	<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.js"></script>
	<script type="text/javascript">
	var size=81, fielddom, g, h;
	var zeroes, walls, open, clos, camefrom, lastwalls, lastopen, lastclos;
	var curx=Math.floor(size/2), cury=3;
	var active = 1;

	function init() {
	$("#field").remove();

	var cellid = 0;
	fielddom = $('<table id="field"></table>').appendTo('body');
	for (var y=0; y<size; y++) {
	var thisrow = $('<tr></tr>').appendTo(fielddom);
	for (var x=0; x<size; x++) {
	var cell = $('<td id="cell' + (cellid++) + '"> </td>')
	.appendTo(thisrow);
	}
	}

	$("#active").change( function() {
	active = $(this).is(":checked");
	});

	// Initialize state arrays
	zeroes = new Array(size*size);
	for (var i=0; i<size*size; ++i) zeroes[i] = 0;
	lastwalls = open = clos = lastopen = lastclos = zeroes;
	walls = zeroes.slice(0);

	update();
	}

	function update() {
	// TODO - Build a maze with Eller's algorithm instead?
	if (active) {
	if (cury >= 3) {
	// Make a copy of the current state
	lastwalls = walls.slice(0);

	// Make a new bar
	var barstart=-1, barend=-1;
	if (Math.random() < 4/10) {
	barstart = Math.floor(Math.random() * size);
	barend = Math.floor(Math.random() * size);

	if (barend < barstart) {
	var temp = barend;
	barend = barstart;
	barstart = temp;
	}
	}

	// Remove the top row
	for (var i=0; i<size; ++i)
	walls.shift();

	// Add a new row
	for (var x=0; x<size; x++) {
	walls.push( x>=barstart && x<=barend ? 1 : 0 );
	}

	cury--;
	} else {
	lastwalls = walls;
	}

	movetogoal()
	refreshfield();
	}

	setTimeout(update, 0);
	}

	function refreshfield() {
	// Show the field based on arrays
	var cellid = 0;
	var curcell = getcell(curx, cury);

	fielddom.find("tr").each( function(y, row) {
	$(row).find("td").each( function(x, cell) {
	if (clos[cellid]) {
	if (walls[cellid])
	cell.className = "closedwall";
	else
	cell.className = "closed";
	}
	else if (walls[cellid])
	cell.className = "wall";
	else if (open[cellid])
	cell.className = "open";
	else
	cell.className = "";

	cellid++;
	} );
	} );

	fielddom.find("td.cur").removeClass("cur");
	$("#cell" + curcell).addClass("cur");
	}

	// This is A*!
	var cardcost = 10, diagcost = 14;
	var digmultiplier = size*0.8; // Digging through a wall is expensive
	function movetogoal() {
	var nextcur = getnextmove();

	curx = nextcur % size;
	cury = Math.floor(nextcur / size);
	}
	function getnextmove() {
	// Save old state
	lastopen = open
	lastclos = clos

	// Make new state
	g = zeroes.slice(0);
	h = zeroes.slice(0);
	open = zeroes.slice(0);
	clos = zeroes.slice(0);
	camefrom = zeroes.slice(0);

	var openheap = new BinaryHeap(function(x){return g[x]+h[x];});
	var start = getcell(curx, cury);

	g[start] = 0;
	h[start] = heuristic(curx, cury);

	openheap.push(start);

	while (openheap.size() > 0) {
	var n = openheap.pop();

	// add n to closed set
	clos[n] = 1;
	open[n] = 0;

	// if n is goal, end and reconstruct path
	if ( Math.floor(n/size) == size-1 ) {
	var nextcur = n;
	while (n != start) {
	nextcur = n;
	n = camefrom[n];
	}
	return nextcur;
	}

	// check all of n's non-closed neighbors
	for (var dx=-1; dx<=1; ++dx) {
	for (var dy=-1; dy<=1; ++dy) {
	var x = (n % size) + dx;
	var y = Math.floor(n/size) + dy;
	if (x < 0 \|\| x >= size \|\| y < 0 \|\| y >= size) continue;

	var neighbor = getcell(x, y);
	if (clos[neighbor] == 1) continue;

	// calculate new g
	oldg = g[neighbor];
	newg = 0;
	if (dx != 0 && dy != 0) newg += diagcost;
	else newg += cardcost;

	// if it's a wall, multiply the cost by dig multiplier
	if (walls[neighbor]) {
	newg *= digmultiplier;
	}
	newg += g[n];

	// if g is better than old g, set it and new h, and set camefrom to n
	if (isNaN(oldg) \|\| oldg == 0 \|\| newg < oldg) {
	g[neighbor] = newg;
	h[neighbor] = heuristic(x, y);
	camefrom[neighbor] = n;

	// add to open set
	if (open[neighbor] != 1) {
	open[neighbor] = 1;
	openheap.push(neighbor);
	}
	}
	}
	}
	}
	}
	function heuristic(fromx, fromy) {
	return (size-fromy) * cardcost;
	}

	function getcell(x, y) {
	return (y * size) + x;
	}

	$( init );
	</script>

	<style type="text/css">
	table#field {
	border-collapse: collapse;
	}
	table#field td {
	border: solid 1px #ccc;
	width: 10;
	height: 12;
	font-size: 1px;
	}
	table#field td.wall {
	background: blue;
	}
	table#field td.closedwall {
	background: #07f;
	}
	table#field td.cur {
	background: red !important;
	}
	table#field td.open {
	background: yellow;
	}
	table#field td.closed {
	background: cyan;
	}
	</style>

	<script type="text/javascript">
	// Binary heap implementation taken from
	// <http://eloquentjavascript.net/appendix2.html>
	// and minified with Dean Edwards' Packer
	// <http://jscompress.com/>

	eval(function(p,a,c,k,e,d){e=function(c){return(c<a?'':e(parseInt(c/a)))+((c=c%a)>35?String.fromCharCode(c+29):c.toString(36))};if(!''.replace(/^/,String)){while(c--){d[e(c)]=k[c]\|\|e(c)}k=[function(e){return d[e]}];e=function(){return'\\w+'};c=1};while(c--){if(k[c]){p=p.replace(new RegExp('\\b'+e(c)+'\\b','g'),k[c])}}return p}('b x(6){3.4=[];3.6=6}x.D={u:b(8){3.4.u(8);3.k(3.4.9-1)},g:b(){5 v=3.4[0];5 d=3.4.g();7(3.4.9>0){3.4[0]=d;3.o(0)}m v},F:b(j){5 h=3.4.9;E(5 i=0;i<h;i++){7(3.4[i]==j){5 d=3.4.g();7(i!=h-1){3.4[i]=d;7(3.6(d)<3.6(j))3.k(i);q 3.o(i)}m}}B C L("N G M.")},H:b(){m 3.4.9},k:b(n){5 8=3.4[n];w(n>0){5 f=I.J((n+1)/2)-1,l=3.4[f];7(3.6(8)<3.6(l)){3.4[f]=8;3.4[n]=l;n=f}q{z}}},o:b(n){5 9=3.4.9,8=3.4[n],p=3.6(8);w(K){5 c=(n+1)*2,e=c-1;5 a=r;7(e<9){5 A=3.4[e],s=3.6(A);7(s<p)a=e}7(c<9){5 y=3.4[c],t=3.6(y);7(t<(a==r?p:s))a=c}7(a!=r){3.4[n]=3.4[a];3.4[a]=8;n=a}q{z}}}};',50,50,'\|\|\|this\|content\|var\|scoreFunction\|if\|element\|length\|swap\|function\|child2N\|end\|child1N\|parentN\|pop\|len\|\|node\|sinkDown\|parent\|return\|\|bubbleUp\|elemScore\|else\|null\|child1Score\|child2Score\|push\|result\|while\|BinaryHeap\|child2\|break\|child1\|throw\|new\|prototype\|for\|remove\|not\|size\|Math\|floor\|true\|Error\|found\|Node'.split('\|'),0,{}))
	</script>

	<body>
	<p><input type="checkbox" id="active" checked><label for="active">Run</label></p>
	</body>

	</html>