Advertisement Jump to content
Sign in to follow this  
Anand Baumunk

[C++] Vector faster than priority-queue in A*

This topic is 1766 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

Well met!

 

I'm still going on with optimising my A*-pathing. Everything is working fine now, only thing I need to do is make it faster.

After a lot of reading and testing, I found the only bottleneck was the useage of a std::vector for the openlist, making the retrieval of the lowest cost node expensive. So I went ahead and replaced it with a priority-queue, beeing sure that everything would be fine afterwards.

 

I was fairly suprised when I noticed that the speed had not changed by much. So I tried profiling again, and found that the bottleneck has shifted to one line:

openList.push(*map[x][y]);

My priority-queue is defined as

priority_queue<node> openList;

and the operator

bool operator>(const node i) const{
    return costF > i.costF;
}  

I can't really see why the push exactly could be the problem, others than the operator beeing bad. I also tried not pushing the nodes itself, but a struct holding only the important infos, but that did nothing.

 

Note that I am pushing nodes when they change their F-cost, too. Because priority-queues are hard to reorder (and in O(n)). When poping the top, ignore it if it isn't actually on the openlist (flag in node). 

 

I have no idea what could be the problem with it - please help me out smile.png

Thanks in advance!

Edited by gnomgrol

Share this post


Link to post
Share on other sites
Advertisement

I'm no C++ pro but I believe that not using a reference in your operator would cause your program to copy the node.

 

Also, have you tried using a vector with make_heap from algorithm?

Share this post


Link to post
Share on other sites

Storing the nodes in a separate array and storing pointers or indices because the vector might be rellocated (to the objects stored in the vector) in the priority_queue might improve performance since pushing values into the priority_queue will require moving them around and copying pointers is faster than copying the whole structure.

Edited by TiagoCosta

Share this post


Link to post
Share on other sites

Also, have you tried using a vector with make_heap from algorithm?

Did you know that's how std::priority_queue is implemented?

Share this post


Link to post
Share on other sites

 

Also, have you tried using a vector with make_heap from algorithm?

Did you know that's how std::priority_queue is implemented?

 

 

He said:

 

"I found the only bottleneck was the useage of a std::vector for the openlist, making the retrieval of the lowest cost node expensive. So I went ahead and replaced it with a priority-queue, beeing sure that everything would be fine afterwards."

 

What I meant was that he could try using the make_heap, instead of replacing it with a priority_queue (probably I wasn't clear enough though).

Share this post


Link to post
Share on other sites

I did a similar comparison a few years back, only I wasn't using any STL, my code was running on Cell SPUs.  What I found was that keeping the open nodes in plain old unsorted arrays (and optimizing the search for the lowest cost node using SIMD intrinsics) was faster than using a priority queue (without SIMD optimization).

 

It depends on how many open nodes you tend to have and how frequently the cost of nodes needs to be updated.  In my case I found that node costs were updated much more frequently than removing a node from the open list, so the overhead of maintaining the order in the priority queue was outweighing the benefit of having it.  I seem to remember having around ~200 nodes on the open list on average.  Those SPUs were really good at brute force.

 

In most cases though I would expect the priority queue to win out.

 

Share this post


Link to post
Share on other sites

It depends on how many open nodes you tend to have and how frequently the cost of nodes needs to be updated.  In my case I found that node costs were updated much more frequently than removing a node from the open list, so the overhead of maintaining the order in the priority queue was outweighing the benefit of having it.  I seem to remember having around ~200 nodes on the open list on average.  Those SPUs were really good at brute force.

 

In most cases though I would expect the priority queue to win out.

 

I'm curious, but why were you updating the cost of nodes so often?  And as a workaround, did you try just adding the node again, with a different cost.

Share this post


Link to post
Share on other sites

 

It depends on how many open nodes you tend to have and how frequently the cost of nodes needs to be updated.  In my case I found that node costs were updated much more frequently than removing a node from the open list, so the overhead of maintaining the order in the priority queue was outweighing the benefit of having it.  I seem to remember having around ~200 nodes on the open list on average.  Those SPUs were really good at brute force.

 

In most cases though I would expect the priority queue to win out.

 

I'm curious, but why were you updating the cost of nodes so often?  And as a workaround, did you try just adding the node again, with a different cost.

 

 

Well, as I said this is from a few years ago, so I can't recall all of the details.  It may be that the frequency of updating node costs was simply much more than I had expected, and not more frequent than node removals.  With the priority queue, it needs to be reordered any time a node is added, removed or has it's cost updated.  So all three of those operations are O( log N ).  With a simple unsorted array, adding a node or updating the cost is O( 1 ), and removing the best node is O( N ).

Share this post


Link to post
Share on other sites
Thanks for all the answers!
When I saw ApochPIQs answer, I hit my head against a wall. Of corse that was the problem! 
... Atleast I thought so. For some reason, when the operator is defined like this
 
bool node::operator<(const node *right) const{
return (costF < right->costF);
}
it is beeing completly ignored by the priority queue. Deleting it doesn't give me ">operator not defined".
 
So, I switched back to using 
struct nodeCostCompare{
bool operator() (const node *a, const node *b)const
{
return a->costF > b->costF;
}
};
priority_queue<node*, vector<node*>, nodeCostCompare> openList;  
which is actually beeing called. 
 
The  problem is that this is not faster than my old code. I guess it is because, everytime I push, a new nodeCostCompare is created, right?
So I have to find a way of using the overloaded >operator, but as I stated, I can't figure out why it is not beeing called when using reference instead of value to compare (and what the hell else it is using).
 
Storing the nodes as pointers leaves me with the problem that I can't update the values of them after I pushed them into the queue - I bypassed the problem by just pushing the node again, and when poping, checked if they were on the openlist. 
But I can't do that with pointers - as soon as I try to update a value on a node that I pushed onto the openlist, I end up with the "invalid heap" runtime error. 
 
For the moment, I just took out the code that was updateing nodes - now the path is slightly incorrect.
 
If you had some more thoughts on this, I'd highly apprechiate it to hear them!
 
 
EDIT: Okey, I figured out the problem with this one: The problem is, the pointer addresses are sorted. The only way to avoid this is a class that 'compares the pointers'.
So this is no option either.
Edited by gnomgrol

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!