A* performance
Author
I''ve implemented the A* search, and was wondering how it rated against other implementations. Bascially it can search through about 300 nodes/ms on my P3 1 Ghz, or about 300k nodes/sec. It uses a stl map to store the sets, and preallocated link buffer for better memory access.
-ddn
this also depends on the size of the grid/mesh you are searching on, the cost function and so on.
an example from me, on a 559 waypoint grid, just using euclidian distance for heuristic and cost. i''m using a "handmade" priority queue with incorporated hashtable and a memory pool for faster allocation of new nodes.
average apprx. 8000paths/second (p4 2666) when calculating a path from each waypoint to each other : logfile
an example from me, on a 559 waypoint grid, just using euclidian distance for heuristic and cost. i''m using a "handmade" priority queue with incorporated hashtable and a memory pool for faster allocation of new nodes.
average apprx. 8000paths/second (p4 2666) when calculating a path from each waypoint to each other : logfile
Author
You are correct as31415rin, from my inital profiling, i found nearly half the time was spent in the herustic evaulator function and the other half was the insertion cost of adding a node into the maps.
The cost of adding a node, was reduced using a memory pool and the evaulator function is dependent upon the user, so i can't optimize that.
I've read some article about using a proirty queue, or heaps. They are faster for small sets from what i understand. I might switch to that, since STL has a native implementaiton of a heap.
thanks again!
-ddn
[edited by - ddn3 on August 17, 2003 3:49:43 PM]
The cost of adding a node, was reduced using a memory pool and the evaulator function is dependent upon the user, so i can't optimize that.
I've read some article about using a proirty queue, or heaps. They are faster for small sets from what i understand. I might switch to that, since STL has a native implementaiton of a heap.
thanks again!
-ddn
[edited by - ddn3 on August 17, 2003 3:49:43 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement