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

Thanks in advance!

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.

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.

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.

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 ).