Get all the updated source code from github.
|Observed Speed of A* Search on Chrome 6.0.472.55 on OS X|
|100||700-2500ms (wildly variant)||5-10ms|
Here’s What Changed
Also, I realized two places that I was traversing lists that could be avoided. Getting rid of extra traversals (especially ones that ran inside nested loops) made a very big difference in performance.
- I was keeping all of the nodes inside a closed list, which required traversing that list every time to see if it was already closed. This was replaced with a simple bit on the node to track if it had been closed.
- I was checking to see if a node was visited already by seeing if it was in the open list. This was replaced by a simple bit to see if it had been visited.
Updated Pseudocode (* lines have changed)
I also did some general cleanup, getting rid of dependancies on the demo, and I split out the code so that the search function can be used standalone (taking a two dimensional array as a parameter), so if someone just wanted the optimized astar search, you could call it like so:
What Could Make It Better?
Last time I posted about this, I got a lot of feedback (mostly about how slow it was). If anyone reading this knows of anything that could make it better, let me know.
Source Code (direct links)