I am currently using your library for pathfinding within my project. On a 50x50 grid, with some large obejcts to block the way (up to 10x10), when attempting to reach an internal node of the blocked area, computaiton time for the path would go up to 1 second (freezing everything in the meantime).

I have edited your AStar class and was able to reduce computation time for 40%, reaching times of around 0.6 secs. If visiting is disabled, then computation time goes down to 0.2 secs, still a little bit high, but way better than the original.

I am submiting the patch with visiting enabled for you to include in the source if you see fit. I've basically cleaned up the no-path-found section (which computed the path a couple times, and needlessly called the distance function), as well as changed the closed list for a dictionary (since order is not important). I've also noticed a slight improvement by using Array.sortOn rather than manually searching for the node with the best f.

Regards

Just killed hour trying to apply this patch under windows. gnuwin32 path.exe crashes. I don't know how to figure out how to apply it manually. Could you please upload entire file?

The problem is the patch was for release 66, which was the latest on Nov 16, 2009 when I submitted the patch. Since then for what I can see you changed the structure of the project... you are using ints instead on IntPoint and other stuff, so the patch itself can't be applied directly.

Non the less, the idea behind the patch is still COMPLETELY valid.

a - the closed Vector should be a Dictionary. A Dictionary has no set order, and can find stuff inside of it in O(1). A vector has order but needs O(n) for lookups when non-sorted. When using A* (unlike other pathfinding algorithms) the order of the closed is not required. Actually, if you look at your code you will notice you are just adding stuff and searching for them with indexOf with the only purpose of knowing if they are there. The reduction of the complexity for this tasks carries a pretty big performance boost in general to the algorithm.

b - Instead of searching by hand the element in the open list with lowest f, have it sorted each time you add elements (right after the for each(var y:int in graph.getNeighbors(x))). Once again, searching for the lowest on a non-sorted vector is O(n), while sorting with sort() is O(log(n)) and getting the lowest element of a sorted list is O(1) (it's always the first if we order in ascending order). Therefore, you can replace this piece of code:

// Find node with lowest f var tf:Number = Number.POSITIVE_INFINITY; var x:int = -1; for (var i:int=0; i

. . .

open.splice(open.indexOf(x), 1);

with just:

var x:int = open.shift();

Notice you are additionally getting rid of another call to indexOf which is O(n).

c - Finally, the improvement of the building of a path when no solution was found. You are currently doing:

// No solution found, return shortest alternative var min:Number = Number.POSITIVE_INFINITY; var ng:int = -1; for each(var n:int in closed) { var d:Number = graph.distance(goal, n); if (d < min) { min = d; ng = n; } }

However, the call to graph.distance(goal, n) is needless, since for every node 'y' to have ever been on open (and therefore in closed), you have already done:

h[y] = graph.distance(y,goal);

so this can be replaced with:

var min:Number = Number.POSITIVE_INFINITY; var ng:int = -1; for each(var n:int in closed) { if (h[n] < min) { min = h[n]; ng = n; } }

I'm attaching the code with these changes, but since my current computer doesn't have Flex installed (I pretty much haven't coded in AS for a year now) I haven't tested it, though I'm almost certain it will work.

If you have any doubts or issues, just let me know.