Last active
December 11, 2015 04:28
-
-
Save McFunkypants/4544753 to your computer and use it in GitHub Desktop.
This file contains hidden or 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
// Path function, executes AStar algorithm operations | |
function calculatePath() | |
{ | |
// create Nodes from the Start and End x,y coordinates | |
var mypathStart = Node(null, {x:pathStart[0], y:pathStart[1]}); | |
var mypathEnd = Node(null, {x:pathEnd[0], y:pathEnd[1]}); | |
// create an array that will contain all world cells | |
var AStar = new Array(worldSize); | |
// list of currently open Nodes | |
var Open = [mypathStart]; | |
// list of closed Nodes | |
var Closed = []; | |
// list of the final output array | |
var result = []; | |
// reference to a Node (that is nearby) | |
var myNeighbours; | |
// reference to a Node (that we are considering now) | |
var myNode; | |
// reference to a Node (that starts a path in question) | |
var myPath; | |
// temp integer variables used in the calculations | |
var length, max, min, i, j; | |
// iterate through the open list until none are left | |
while(length = Open.length) | |
{ | |
max = worldSize; | |
min = -1; | |
for(i = 0; i < length; i++) | |
{ | |
if(Open[i].f < max) | |
{ | |
max = Open[i].f; | |
min = i; | |
} | |
} | |
// grab the next node and remove it from Open array | |
myNode = Open.splice(min, 1)[0]; | |
// is it the destination node? | |
if(myNode.value === mypathEnd.value) | |
{ | |
myPath = Closed[Closed.push(myNode) - 1]; | |
do | |
{ | |
result.push([myPath.x, myPath.y]); | |
} | |
while (myPath = myPath.Parent); | |
// clear the working arrays | |
AStar = Closed = Open = []; | |
// we want to return start to finish | |
result.reverse(); | |
} | |
else // not the destination | |
{ | |
// find which nearby nodes are walkable | |
myNeighbours = Neighbours(myNode.x, myNode.y); | |
// test each one that hasn't been tried already | |
for(i = 0, j = myNeighbours.length; i < j; i++) | |
{ | |
myPath = Node(myNode, myNeighbours[i]); | |
if (!AStar[myPath.value]) | |
{ | |
// estimated cost of this particular route so far | |
myPath.g = myNode.g + distanceFunction(myNeighbours[i], myNode); | |
// estimated cost of entire guessed route to the destination | |
myPath.f = myPath.g + distanceFunction(myNeighbours[i], mypathEnd); | |
// remember this new path for testing above | |
Open.push(myPath); | |
// mark this node in the world graph as visited | |
AStar[myPath.value] = true; | |
} | |
} | |
// remember this route as having no more untested options | |
Closed.push(myNode); | |
} | |
} // keep iterating until until the Open list is empty | |
return result; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Where's the estimated distance sorting step? You're calculating an estimated distance for paths, but do not appear to be sorting on it – therefore seem to be missing the benefit of a prioritized search queue.
Also, shouldn't the world graph store a number for visited nodes indicating the cost to reach the node, rather than a simple boolean flag? We don't want to neglect paths to visited nodes if we happen upon a shorter way to get there.