bool sortNodes(const PathNode *A, const PathNode *B)
{
return A->F > B->F;
};
A)
openList.push_back(node);
std::sort(openList.begin(), openList.end(), sortNodes);
B)
openList.insert(std::lower_bound(openList.begin(), openList.end(),node, sortNodes),node);
Insert sort with std::vector ? (A*star) [SOLVED]
Author
Hi!
Can someone explain to me why these produce different results?
I'm trying to sort pathfinding nodes based on their F-value (using Astar here...)
With push and sort the results are perfect.
With insert and lower_bound, the returned path is garbled.
Since the openList is mostly sorted I don't really want to sort it all the time, which is rather time-consuming.
Dear Gamedev.net, any clues? :)
/Robert
[Edited by - Rasmadrak on November 14, 2008 12:47:31 AM]
1) Do you in fact care about the ordering of elements that have equal F values?
2) Are you reusing the iterator in a loop? Keep in mind that .insert() into a vector will invalidate any iterator beyond that point - notably any previous .end() - so it will need to be re-requested, and not saved in a variable.
3) Any particular reason you're storing pointers to PathNode instead of the PathNodes directly?
4) .insert() on a vector is O(N); have you considered using std::list (or perhaps even a sorted container such as std::multi_set)?
2) Are you reusing the iterator in a loop? Keep in mind that .insert() into a vector will invalidate any iterator beyond that point - notably any previous .end() - so it will need to be re-requested, and not saved in a variable.
3) Any particular reason you're storing pointers to PathNode instead of the PathNodes directly?
4) .insert() on a vector is O(N); have you considered using std::list (or perhaps even a sorted container such as std::multi_set)?
Author
Quote:
1) Do you in fact care about the ordering of elements that have equal F values?
Nope, if F is equal then the first node in the list will do.
Quote:
2) Are you reusing the iterator in a loop? Keep in mind that .insert() into a vector will invalidate any iterator beyond that point - notably any previous .end() - so it will need to be re-requested, and not saved in a variable.
After the insert, the list/vector is resorted and the next node is processed.
Quote:
3) Any particular reason you're storing pointers to PathNode instead of the PathNodes directly?
Yes, the pathgrid is initiated once and all calculations are done refering/pointing to those nodes.
Quote:
4) .insert() on a vector is O(N); have you considered using std::list (or perhaps even a sorted container such as std::multi_set)?
The result is the same with both std::list and std::vector.
The problem is that I don't really get the node with the lowest F score when I'm using lower_bound. It's almost as if the F, which is a float, gets converting into a integer or something.
EDIT:
Found the problem.
I was using a too tight heuristic which returned false information. The sorting fixed it (beats me why), but when I over-estimated the distance (F) the lower_bound version worked flawlessly!
I simply multiplied the distance with 1.1 .
This could mean that it may be a rounding error causing faults, i.e by multiplying by a factor I increase the "distances" between the different F-values.
Thanks for your time!
Author
Hello, it's me again...
I guess I was too eager in finding a solution -
lower_bound seem to produce less graceful paths, but they're good enough.
If speed becomes an issue, it's nice to know there's a quick-and-dirty fix. :)
Cheers!
I guess I was too eager in finding a solution -
lower_bound seem to produce less graceful paths, but they're good enough.
If speed becomes an issue, it's nice to know there's a quick-and-dirty fix. :)
Cheers!
That sounds like pretty sketchy surrounding if you can hack things like that. What exactly is your calculation for F?
Author
Quote:Original post by Zahlman
That sounds like pretty sketchy surrounding if you can hack things like that. What exactly is your calculation for F?
pseudo:
G = distanceTraveledSoFar;
H = distanceToTarget*1.4;
F = G + H;
With this as F cost, and using std::priority_queue I believe it works as expected.
Further investigation must be done to ensure that a large collection of nodes isn't wrongfully searched.
Using priority queues was actually a lot easier than I expected! :)
Having a heuristic function that underestimates the distance should not cause incorrect results. In fact, it is necessary if you want to ensure that the path found is optimal. Even a heuristic that constantly returns 0 should work, causing A* to degrade to a shortest path first search. Overestimating the distance may shorten the search and cover up whatever the real problem is.
If you really want to find out what is going wrong with the insertion method, you should watch the values in the array.
If you really want to find out what is going wrong with the insertion method, you should watch the values in the array.
Author
Hi all!
Just wanted to check in and report my progress.
After a really (and I mean REALLY) extensive test I noticed that I did the A-Star search partially wrong.
The culprit:
Premature optimization.
If I hadn't been trying to speed up the search before knowing the actual problem (which back then was selecting the closest start/finish nodes) I would have seen this problem earlier.
Instead of just using a simple integer check to see if the node had been visited and/or is in the openlist, I replaced it with a full "is it in the openList?"-search.
The magic-number voodoo which was used as H is now replaced with simply the distance to the finish node.
Voila, it worked right away as expected.
Finally my A*Star works perfectly!
Note to others:
Never ever in your wildest dreams optimize prematurely.
If you're trying to redo other peoples work - read the description properly!
A big thanks to all who helped!
/Robert
Just wanted to check in and report my progress.
After a really (and I mean REALLY) extensive test I noticed that I did the A-Star search partially wrong.
The culprit:
Premature optimization.
If I hadn't been trying to speed up the search before knowing the actual problem (which back then was selecting the closest start/finish nodes) I would have seen this problem earlier.
Instead of just using a simple integer check to see if the node had been visited and/or is in the openlist, I replaced it with a full "is it in the openList?"-search.
The magic-number voodoo which was used as H is now replaced with simply the distance to the finish node.
Voila, it worked right away as expected.
Finally my A*Star works perfectly!
Note to others:
Never ever in your wildest dreams optimize prematurely.
If you're trying to redo other peoples work - read the description properly!
A big thanks to all who helped!
/Robert
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
