A* haXe pathfinding
November 26th, 2008
I rewrote bmod at BaseOneOnline.com’s Actionscript 3.0 A* classes to haXe (flash9 because I’m working on a game and needed some quick pathfinding. I also wanted to see if haXe would solve the A* algorithm faster than the adobe actionscript 3 compiler, and by how much. The benchmarks are not as accurate on bmod’s as3 because he mentions he used an inaccurate timing method. I had trouble with haXe’s flash9.utils.Timer class too, so i used the haXe haxe.Timer class to get a more accurate measurement.
The solved path is not always the shortest path possible as intended. But will suffice for what i need it for.
When sorting a node’s neighbors by it’s cost (distance), I had some trouble because i didn’t know how to translate AS3’s Array.sort) to haXe’s Array.sort. So i added DiskTree.net’s QuickSort (sorting the node property for distance “f”) to the com.baseoneonline.haxe.astar package.
Other than the timer and replacing Array.sort with QuickSort, the code is pretty much the same, just re-written to be compiled on haXe. There may be a few more enhancements i can make to make this faster, such as using Vector instead of Array and compiling for flash10, something i may try, or you can try and let me know :)
The original BaseOneOnline.com AS3 A* Article is here: http://blog.baseoneonline.com/?p=87
The exact Actionscript3 source that i used to convert to haXe:
BaseOneOnline-AStar-AS3.zip
Check the site though, he may have an update
My haXe‘d A* classes:
zipped: AStar-haXe.zip
svn: http://publicsvn.remixtechnology.com/AStar-haXe
Both examples have random “unwalkable” tiles generated, so just refresh this page to get a new random tile map. Just click around on the lighter tiles to find new paths
Original A* path finding in Actionscript 3 [Source][Destination]
You need Flash 10 to view the awesome. It’s a free and fast upgrade.
Ported A* path finding to haXe as3 [Source][Destination]
You need Flash 10 to view the awesome. It’s a free and fast upgrade.
i hope this fills your haXe tile based path finding needs well. Many thanks to bmod for his great work!
Nice work.
It would be nice to be able to compare the two finding the same path, from the attempts I made I couldn’t tell which was faster, sometimes one sometimes the other.
nice work !
the following exception occurs whith debug player when the path cannot be solved on both versions
TypeError: Error #1009: Cannot access a property or method of a null object reference. at com.baseoneonline.haxe.astar::QuickSortNodes$/quicksort() at com.baseoneonline.haxe.astar::QuickSortNodes$/run() at com.baseoneonline.haxe.astar::AStar/solve() at AStarHaxe/onClick()
It's not always the shortest path possible because the code you ported was incorrect. Whoever wrote it doesn't seem to have a good grasp of A*, or at least not of their own code for it. Here's how to fix your version. The problems are in com/baseoneonline/haxe/astar/AStar.hx. Line 110 was: n.g = node.g; it should be: n.g = node.g + n.cost; (Problem:g, the cost of the path so far, was being abused badly, by trying to store the cost for stepping to that node as well. The end result was to essentially randomize it for any node examined more than once.) Lines 112-116 were: var f:Float = n.g + node.g + n.h; if (f < n.f) { n.parent = node; n.g = node.g; } they should be: if (node.g + n.cost < n.g) { n.parent = node; n.g = node.g + n.cost; } (Problem: Same as before, plus a broken comparison, such that the if condition was always false. Meaning that once you visited a node, you'd never find a shorter path to it.) Lines 201, 209, 217, and 225 are all: n.g += COST_ORTHOGONAL; they should be: n.cost = COST_ORTHOGONAL; (Problem: The origin of the abuse of .g we've seen all along.) Similarly, lines 240, 251, 262, and 273 are all: n.g += COST_DIAGONAL; and should all be: n.cost = COST_DIAGONAL; (Problem:Same as before, just the diagonal steps this time.) Haven't tested, so there may be other problems with the code, but making those fixes should improve the situation noticably. Additionally, there are some obvious performance faux pas. Instead of storing an arrays of closed nodes, it would be better to put a .closed property (boolean) on each node, to avoid searching the array for each node. open, which is better named search_nodes, should really be a min heap, which eliminates the sorting altogether; just run heapify as needed. Instead of checking to see if something is an element of open, just check to see if .parent has been set. tl;dr : Man, you started with really bad code. Looks like the original author put up a much-improved version a few days ago, might want to grab that and see if it's any better: http://blog.baseoneonline.com/?p=151