Sign in to follow this  
Rasmadrak

Insert sort with std::vector ? (A*star) [SOLVED]

Recommended Posts

Hi! Can someone explain to me why these produce different results?
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);



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]

Share this post


Link to post
Share on other sites
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)?

Share this post


Link to post
Share on other sites
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!


Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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! :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this