Last active
December 16, 2015 08:39
-
-
Save Radnen/5406961 to your computer and use it in GitHub Desktop.
An implementation of an A* pathfinding algorithm in JavaScript for Sphere.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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