Skip to content

Instantly share code, notes, and snippets.

@McFunkypants
Last active December 11, 2015 04:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save McFunkypants/4544753 to your computer and use it in GitHub Desktop.
Save McFunkypants/4544753 to your computer and use it in GitHub Desktop.
// 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;
}
@gmac
Copy link

gmac commented Mar 18, 2013

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment