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

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]