Skip to content

Instantly share code, notes, and snippets.

@Radnen
Last active Dec 16, 2015
Embed
What would you like to do?
An implementation of an A* pathfinding algorithm in JavaScript for Sphere.
/**
* 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;
}
/**
* 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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment