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!