An implementation of an A* pathfinding algorithm in JavaScript for Sphere.

binarytree.js

/**
* Script: BinaryTree.js
* Written by: Radnen
* Updated: 10/27/2011
**/

function TreeNode(object)
{
  this.data = object;
	this.left = null;
	this.right = null;
}

function BinaryTree()
{
	this.root = null;
	this.compare = function(a, b) { return a > b; }
	this.equals = function(a, b) { return a == b; }
}

/**
* - this clears the tree for reuse.
**/
BinaryTree.prototype.clear = function()
{
	this.root = null;
}

/**
* - used for debug purposes, returns a human readable string of the contents.
**/
BinaryTree.prototype.toAString = function(data) {
	if (!data) return "{}";
	return data.data + " {l: " + this.toVisual(data.left) + ", r: " + this.toVisual(data.right) + "}";
}

/**
* - adds a node containing the data element sorted by the compare function.
**/
BinaryTree.prototype.add = function(data)
{
	if (!this.root) { this.root = new TreeNode(data); return; }
	
	var current = this.root;
	var previous = null;
	var left = false;
	
	while (current) {
		if (this.compare(current.data, data)) {
			previous = current;
			current = current.left;
			left = true;
		}
		else {
			previous = current;
			current = current.right;
			left = false;
		}
	}
	
	if (left) previous.left = new TreeNode(data);
	else previous.right = new TreeNode(data);
}

/**
* - returns true if the data element is indeed within the tree.
**/
BinaryTree.prototype.contains = function(data) {
	var temp = this.root;

	while (temp) {
		if (this.equals(temp.data, data)) return true;
		else if (this.compare(temp.data, data))
			temp = temp.left;
		else
			temp = temp.right;
	}
	
	return false;
}

/**
* - shift returns the left-most data in the tree.
**/
BinaryTree.prototype.shift = function() {
	var prev, temp = this.root;
	
	while (temp.left) {
		prev = temp;
		temp = temp.left;
	}
	
	if (!prev) {
		var t = this.root.data;
		this.root = this.root.right;
		return t;
	}
	
	if (temp.right) prev.left = temp.right;	
	else prev.left = null;
	
	return temp.data;
}

/**
* - pop returns the right-most data in the tree.
**/

/**
* - remove searches for and removes a node containing the data element.
**/
BinaryTree.prototype.remove = function(data) {
	var temp = this.root;
	while (temp) {
		if (this.equals(temp.data, data)) {
			temp = this.removeAt(temp);
		}
		else if (this.compare(temp.data, data))
			temp = temp.left;
		else
			temp = temp.right;
	}
	
}

/**
* - internal use, removes a node at the specific location.
**/
BinaryTree.prototype.removeAt = function(node) {
	if (!node.left && !node.right) return null;
	else if (!node.left) {
		return node.right;
	}
	else if(!node.right) {
		return node.left;
	}
	else {
		var data = this.getInOrderSuccessor(node);
		node.data = data;
		return node;
	}
}

/**
* - internal use, gets the inorder successor for node removal.
**/
BinaryTree.prototype.getInOrderSuccessor = function(node) {
	var retVal, prev;
	
	while (node.left) {
		prev = node;
		node = node.left;
	}
	Alert(node.data);
	
	prev.left = null;
	return node.data;
}

pathfinder.js

/**
* Script: pathfinder.js
* Written by: Radnen
* Updated: 1/21/2012
**/

RequireScript("binarytree.js");

function PathNode(x, y)
{
  this.x = x;
	this.y = y;
	
	this.f = 0;
	this.g = 0;
	this.h = 0;
	
	this.next = null;
	this.blocked = false;
}

var Pathfinder = {
	open: new BinaryTree(), // binary tree to order opened nodes
	closed: [],							// hash to store closed nodes
		
	grid: [],								// contains nodes
	width: 0,								// width of pathing field
	height: 0,							// height of pathing field
	
	block: function(x, y)
	{
		var i = x*this.width+y;
		this.grid[i].blocked = !this.grid[i].blocked;
	},
	
	init: function(width, height)
	{
		this.width = width;
		this.height = height;
		
		var w = 0;
		for (var x = 0; x < width; ++x) {
			var y = height+1;
			while(y--) this.grid[w + y] = new PathNode(x, y);
			w += width;
		}
	},
	
	doPath: function(x1, y1, x2, y2)
	{		
		this.open.clear();
		this.closed = [];
		var cur, n = 0, w = 0, h = 0, temp, ww;
		
		temp = this.getStart(x1, y1);		
		this.closed[temp] = true;
		cur = this.grid[temp];
		
		while(true) {
			w = cur.x + 2;
			h = cur.y + 2;
			
			for (var x = cur.x-1; x < w; ++x) {				
				if (x < 0 || x == this.width) continue;
				
				ww = x * this.width;
				
				for (var y = cur.y-1; y < h; ++y)
				{
					if (y < 0 || y == this.height) continue;					
					n = ww + y;
					
					if (this.closed[n]) continue;
					
					temp = this.grid[n];

					if (temp.blocked) continue;
					
					if (!this.open.contains(temp)) {
						if (x == cur.x || y == cur.y) temp.g = cur.g + 10;
						else temp.g = cur.g + 14;
						temp.h = 10*(Math.abs(temp.x - x2) + Math.abs(temp.y - y2));
						temp.next = cur;
						temp.f = temp.g + temp.h;
						this.open.add(temp);
					}
					else if (cur.g < temp.g) {
						if (x == cur.x || y == cur.y) temp.g = cur.g + 10;
						else temp.g = cur.g + 14;
						temp.next = cur;
						temp.f = temp.g + temp.h;
					}
				}
			}			
			
			if (this.open.root == null) return null;

			cur = this.open.shift();
			this.closed[(cur.x*this.width)+cur.y] = true;
			
			if (cur.x == x2 && cur.y == y2) break;
		}		
		
		return this.follow(cur);		
	},
		
	getStart: function(x, y)
	{
		var i = x*this.width + y;
		var n = this.grid[i];
		n.f = n.g = n.h = 0;
		return i;
	},
	
	follow: function(node) {
		var arr = [];
				
		while (node) {
			arr.unshift({x: node.x, y: node.y});
			node = node.next;
		}
		
		return arr;
	},
};

Pathfinder.open.compare = function(a, b) {
	return a.f > b.f;
}

/* INTERACTIVE TEST: */

var white = CreateColor(255, 255, 255);
var red = CreateColor(255, 0, 0);
var left = false;
var arrow = GetSystemUpArrow();

Pathfinder.init(10, 10);
var steps = [];
function game() {
	while(!IsKeyPressed(KEY_ESCAPE)) {
		OutlinedRectangle(0, 0, 160, 160, white);
		
		var mx = GetMouseX();
		var my = GetMouseY();
		var x, y;
		
		for (var i = 0; i < 10; ++i) {
 			x = i << 4;
			for (var j = 0; j < 10; ++j) {
				y = j << 4;
				
				if (mx > x && my > y && mx < x+16 && my < y+16) {
					if (IsMouseButtonPressed(MOUSE_LEFT) && !left) {
						Pathfinder.block(i, j);
						steps = Pathfinder.doPath(0, 0, 8, 9);
						left = true;
					}
					if (!IsMouseButtonPressed(MOUSE_LEFT)) left = false;
				}

				if (Pathfinder.grid[i*Pathfinder.width+j].blocked) Rectangle(x, y, 16, 16, white);
			}
		}
		
		if (steps) {
			for (var i = 0; i < steps.length; ++i)
				Rectangle(steps[i].x*16, steps[i].y*16, 16, 16, red);
		}
		
		arrow.blit(mx-8, my);
		FlipScreen();		
	}
}