A* search (JavaScript)

From LiteratePrograms
Jump to: navigation, search

Contents

[edit] Introduction

This article describes an implementation of the A* search algorithm in JavaScript.

Given a graph with a start- and a target-node, the algorithm will, if possible, find a best path between those. This is the short version of how it works:

  1. The start node (S) has a cost (g()) of 0
  2. Look up each node connected to the start node and:
    • Store a reference to the start node
    • Increase the cost (g()) based on the weight of the edge followed.
    • Calculate an estimated cost (h()) to reach the target node
    • Store the node in a priority queue (opened) using f()=g()+h() as the priority value.
  3. Repeat from 2, using the node with lowest f() as start node, until the target node is reached

When the target node is reached, the back-references can be followed to create a route.

This algorithm is normally used on graphs organized as a grid, where the nodes are implicitly connected to all neighbour cells.

[edit] Data structure

Each node is represented by a pos object which is created like this:

<<pos>>=
function pos(x, y) {
	this.x=x; this.y=y;
	this.cost=0;
	this.totalcost=0;
	this.blocked=false;
	this.closed=false;
	this.prev=null;

	this.str=function() {
		return this.x+","+this.y;
	}
	this.equal=function(p) {return this.x==p.x && this.y==p.y;}
}

The grid itself is stored in an Array of Arrays containing nodes (pos-objects).

The opened priority queue used is a sorted Array. While this is probably not an optimal solution when the number of nodes gets big, it is good enough in this case and very easy to implement. A binary heap might be a better choice in many situations.

<<grid>>=
var grid=new Array();
<<opened>>=
var opened=new Array();

[edit] The algorithm

In this code, the word cell is sometimes used for nodes.

<<astar>>=

function astar()
{
	var best;
	var n=0;

	var chb=document.getElementById("chb_paintopen");
	paint_open=chb.checked;

We start by "opening" the start node (called cell here).

The opencell() function takes three arguments:

  • The first node's pos object
  • The cost to reach the position
  • The previous node's position (In starts case, it is just start)

The best variable represents the node we are currently examining.

<<astar>>=

	best=opencell(start, 0, start);

When best equals target, we are done.

<<astar>>=
	while(best && !best.equal(target)) {
		best.closed=true;
		opened.shift();

openadjacent() is a utility function that opens all nodes directly reachable from the best. In this implementation, there are no diagonal edges, so only nodes positioned on the same row or column are considered reachable.

<<astar>>=
		openadjacent(best);
<<openadjacent>>=

function openadjacent(p)
{
	var cost=grid[p.y][p.x].cost+10;
	if(p.x>0) opencell(grid[p.y][p.x-1], cost, p);
	if(p.y>0) opencell(grid[p.y-1][p.x], cost, p);
	if(p.y<(sizey-1)) opencell(grid[p.y-(-1)][p.x], cost, p);
	if(p.x<(sizex-1)) opencell(grid[p.y][p.x-(-1)], cost, p);
}

Unless the opened queue is empty, the node with the smallest total cost is assigned to best.

<<astar>>=

		if(opened.length>0) best=opened[0];
		else best=null;

		if(++n>10000) {best=null; break;}	/* Catch non-stop loops (should never happen) */
	}
	if(!best) {
		warn="No route found";
		return;
	}

When target is reached, we backtrack using the prev value stored in the each node.

<<astar>>=

	/* Find way back */
	while(!best.equal(start)) {
		setcolor(best, route_color);
		best=best.prev;
		if(!best) {
			alert("Something strange happend");	/* Should never happen */
			break;
		}
	}
}

In opencell() the cost variable refers to the cost from start (often refrred to as g()). totalcost is the sum of cost and the estimated cost to target.

<<opencell>>=

function opencell(p, cost, prev)
{
	if(p.blocked) return null;

An extra cost (4) is applied if the direction is changed. This is intented to reflect the extra time spent accelerating a physical object.

<<opencell>>=

	if(prev && prev.prev && !prev.equal(start)) {
		if(p.x-prev.x != prev.x-prev.prev.x ||
			p.y-prev.y != prev.y-prev.prev.y) cost+=4;
	}

The totalcost variable is the sum of cost and an extimated cost to reach target. Here we just add the differences in x and y directions, and multiply with 14. This constant should probably be fine-tuned to get the best results.

<<opencell>>=

	var totalcost=parseFloat(cost)+14*(Math.abs(p.x-target.x)+Math.abs(p.y-target.y));

The A* algorithm normally also includes a closed queue, representing the nodes that have been considered. In this implementation, the close queue is implicitly defined as those who have a calculated totalcost and are not in the opened queue.

If we reach a node that is opened or closed, it should normally be left, but we might reach that node in a "cheaper" way than when it was first considered, so we see if the new totalcost is better than the stored one. If that is true, the node can be reopened.

<<opencell>>=

	/* If position is already considered: check for better cost */
	if(p.totalcost!=0) {
		if(totalcost<p.totalcost) {
			var nn;

When reopening a node, we must remove it from the opened queue. It will be reinserted into the correct position.

<<opencell>>=
			for(nn=0; nn<opened.length; ++nn) {
				if(p.equal(opened[nn])) {
					opened.splice(nn, 1);
					break;
				}
			}
		} else return null;
	}

	p.cost=cost;
	p.prev=prev;
	p.totalcost=totalcost;

As we use just a simple sorted Array for the opened queue, we iterate the queue to find the right position and use the splice() function to insert it. This obviously has performance issues when the number of nodes grows.

<<opencell>>=

	var n=0;
	for(n=0; n<opened.length; ++n) {
		if(p.totalcost<opened[n].totalcost) {
			opened.splice(n, 0, p);
			break;
		}
	}
	if(n>=opened.length) opened[n]=p;

The pos object representing the node is also stored in the grid array, so that it easy to look up.

<<opencell>>=

	grid[p.y][p.x]=p;

mark opened


[edit] The user interface

We use an html table to display the grid. The start and target positions can be changed by a user, who can also add and remove blockings (nodes that cannot be traversed).

<<astar.html>>=
<html>
<head>
 <title>A*</title>
 <script type="text/javascript" src="astar.js"></script>
</head>
<body onload="doastar();">
 <h1>A* Demo</h1>
 <h2>Instructions</h2>
 'S' is the start position, 'T' is the target position and black positions are blocked.<br/>
 Start and target positions are moved by clicking on them and then clicking on a new position. Any other position will be blocked or unblocked if clicked on.<br/>
 The script is successfully tested on Mozilla Firefox.<br/>
 <input type="checkbox" id="chb_paintopen" checked="1" onclick="chb_click();">Mark open positions</input>
 <table id="grid" border="1"></table>
 <p id="expl"></p>
</body>

The table created in the html code is initially empty. We use the mkgrid() function to generate a table of the wanted size.

<<DOM>>=

function mkgrid()
{
	var table=document.getElementById("grid");
	table.onmouseout=astar_mouseout;

	var tbody=document.createElement("tbody");
	table.appendChild(tbody);

	var tr=document.createElement("tr");
	tr.appendChild(document.createElement("th"));
	tbody.appendChild(tr);

	var x, y;
	for(x=0; x<sizex; ++x) {
		var th=document.createElement("th");
		th.appendChild(document.createTextNode(x));
		tr.appendChild(th);
	}

	for(y=0; y<sizey; ++y) {
		grid[y]=new Array();
		var tr=document.createElement("tr");
		tbody.appendChild(tr);

		var th=document.createElement("th");
		th.appendChild(document.createTextNode(y));
		tr.appendChild(th);

		for(x=0; x<sizex; ++x) {
			grid[y][x]=new pos(x, y);
			var td=document.createElement("td");
			td.appendChild(document.createTextNode(""));

All nodes are identified by their x and y positions in the id attribute.

<<DOM>>=
			td.id=x+","+y;
			td.width=20;
			td.onclick=astar_click;
			td.onmouseover=astar_mouseover;
			td.setAttribute("x", x);
			td.setAttribute("y", y);
			tr.appendChild(td);
		}
	}
}

The wipe() function is used to clean up the table and the associated data structures before rerunning the algorithm.

<<DOM>>=

function wipe()
{
	var y, x;

	warn="";
	opened=new Array();

	for(y=0; y<sizey; ++y) {
		for(x=0; x<sizex; ++x) {
			grid[y][x].cost=0;
			grid[y][x].totalcost=0;
			grid[y][x].prev=null;
			grid[y][x].closed=false;

			if(grid[y][x].blocked) setcolor(grid[y][x], blocked_color);
			else setcolor(grid[y][x], nothing_color);
		}
	}
	setcolor(start, start_color);
	setcolor(target, target_color);
}

function settext(p, text)
{
	var td=document.getElementById(p.str());
	td.firstChild.data=text;
}

function setcolor(p, color)
{
	var td=document.getElementById(p.str());
	td.setAttribute("bgColor", color);
}

function setstart(p)
{
	if(start) {
		settext(start, "");
		setcolor(start, nothing_color);
	}
	start=p;
	settext(start, "S");
	setcolor(start, start_color);
}

function settarget(p)
{
	if(target) {
		settext(target, "");
		setcolor(target, nothing_color);
	}
	target=p;
	settext(target, "T");
	setcolor(target, target_color);
}
<<setblock>>=

function setblock(p1, p2, block)
{
	for(var y=p1.y; y<=p2.y; ++y) {
		for(var x=p1.x; x<=p2.x; ++x) {
			if(block) {
				setcolor(grid[y][x], blocked_color);
				grid[y][x].blocked=true;
			} else {
				setcolor(grid[y][x], nothing_color);
				grid[y][x].blocked=false;
			}
		}
	}
}
<<callbacks>>=

function astar_click(e)
{
	if(!e) var e=window.event;

	var x=this.getAttribute("x");
	var y=this.getAttribute("y");

	var p=grid[y][x];

	if(start_moving && !p.equal(target)) {
		setstart(p); 
		start_moving=false;
		setblock(p, p, null);
	} else if(target_moving && !p.equal(start)) {
		settarget(p);
		target_moving=false;
		setblock(p, p, null);
	} else if(p.equal(start)) start_moving=true;
	else if(p.equal(target)) target_moving=true;
	else {
		if(grid[y][x].blocked) setblock(p, p, null);
		else setblock(p, p, 1);
	}

	if(!start_moving && !target_moving) {
		wipe();
		astar();
	}

	astar_explain(x, y);
}

function chb_click()
{
	wipe();
	astar();
}

function astar_explain(x, y)
{
	var expl=document.getElementById("expl");
	var p=grid[y][x];
	var heuristic=p.totalcost-p.cost;

	if(start_moving) expl.innerHTML="Click to set new start position at "+p.str();
	else if(target_moving) expl.innerHTML="Click to set new target position at "+p.str();
	else if(p.blocked) expl.innerHTML=p.str()+
		"<br>Currently blocked. Click to unblock";
	else if(p.equal(start)) expl.innerHTML="Start position - Click to move";
	else if(p.equal(target)) expl.innerHTML="Target position - Click to move";
	else if(p.cost==0) expl.innerHTML=p.str()+"<br>Click to block this position";
	else expl.innerHTML=p.str()+
		"<br>Cost from start: "+p.cost+
		"<br>Heuristic estimate to target: "+heuristic+
		"<br>Total cost: "+p.totalcost+
		"<br>Click to block this position";

	if(warn.length>0) expl.innerHTML+="<br><div style=\"color:red\">"+warn+"<div>";
}

function astar_mouseover(e)
{
	if(!e) var e=window.event;

	var x=this.getAttribute("x");
	var y=this.getAttribute("y");

	astar_explain(x, y);
}

function astar_mouseout()
{
	var expl=document.getElementById("expl");
	expl.innerHTML="";
}

Opened positions are optionally marked with a color code.

<<mark opened>>=
	if(paint_open && !p.equal(start)) {
		var intensity=Math.floor(totalcost*4/5);
		
		if(intensity>255) intensity=255;
		setcolor(p, "#"+intensity.toString(16)+"ff"+intensity.toString(16));
	}

	return p;
}

[edit] Test code

<<astar.js>>=
var sizex=16;
var sizey=16;

var start=null;
var target=null;

grid
opened

var expl_text=null;

var paint_open=false;

var start_moving=false;
var target_moving=false;

var nothing_color="#ffffff";
var blocked_color="#000000";
var start_color="#00ff00";
var target_color="#0000ff";
var route_color="#00ffff";

var warn="";

pos
DOM
setblock
opencell
openadjacent
astar
callbacks
doastar
<<doastar>>=
function doastar()
{
	mkgrid();

	setstart(new pos(6, 2));
	settarget(new pos(9, 14));
	setblock(new pos(1, 3), new pos(10, 4), true);
	setblock(new pos(12, 4), new pos(15, 4), true);
	setblock(new pos(2, 6), new pos(14, 12), true);
	setblock(new pos(0, 6), new pos(0, 9), true);
	setblock(new pos(9, 6), new pos(10, 11), false);
	setblock(new pos(11, 11), new pos(14, 11), false);

	astar();
}

To run this code, just save astar.js and astar.html to the same directory and open astar.html in your browser. A (possibly outdated) copy is located here.

Download code
hijacker
hijacker
hijacker
hijacker