Archived

This topic is now archived and is closed to further replies.

A* performance

This topic is 5266 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites