You can look up nodes by their (X,Y) position the same way you would look up map tiles by their (X,Y) position.

As for using a heap to find the open node with least cost...that stuff can be kind of confusing, especially with an algorithm like this, since you might change the cost of a node while it is inside the open list. Maybe just skip that one for now; I think you'll get a big speed boost just by finding nodes and their open/closed/unsearched status by looking them up by (X,Y) coordinate instead of scanning the lists for them. Oh, and on that note, be sure to reset the status of all the nodes after performing the A* so that they'll be in the right state for the next search.

As for finding the least cost open node, lots of people seem to just use a sorted list for that. As in, a list they keep in sorted order by inserting the nodes into the proper place in the list. When the value of a node changes, you just need to look up the list to see where its new position is.

The heap stuff is complicated because the stl doesn't provide a function which would be necessary for using a heap in this algorithm. When the value of a node in the heap changes, you need to be able to find the location of node in the heap and bubble it to the right position. As far as I know the stl doesn't provide a way to do this. Books on data structures might describe how this can be done...you'd need to understand how a heap works and stuff. Heaps themselves are complicated things. The idea behind a heap is that if you just want to find the entry with the smallest (or largest) key, it isn't necessary to keep the entries in a fully sorted order. Heaps are like maps, but faster because organize the tree in a less sorted way which only enables them to find the smallest element quickly.

You could also try using a map for the open list. Just when updating a key, first remove the node, update the key, then reinsert the node. I think this should work, and it will be somewhat close to the efficiency of a heap.

I come to the conclusion that however crappy my implementation, the incredible slowness must be due partly to an algorithmic weakness. We always tell people that the right algorithm is more important to speed than the implementation after all.

I looked up A* in a couple more places and found a contradiction:
When a new node N' is generated from the current node N, look for N' in the Open and Closed lists. If it's already in the open list, make sure the version with the lowest cost is retained. But what if it's in the closed list? One doc I found said if N' is in Closed, sometimes it can be put back on Open - another said that if N' is in closed, skip this node and go on to look at the next one.

Which behaviour is correct?

With a proper implementation of A*, a node in the closed list should never be put back in the open list. With an imperfect implementation, it is sometimes possible that a node is placed in the closed list but later a lower cost path to that node is found. In such situations, you also need to re-value all paths that go through the node the easiest way to do that is to put it back in the open list.

I wasn't sure how to use the stl heap functions either, despite having a code example to work from.

Instead, for the open list, I used a vector, and called std::sort on it with my own predicate, and kept the best node at the end of the vector. That way, I could just use pop_back() to get rid of the top node.

For the closest list, I used a std::set of path link objects.

Quote: Original post by Anonymous Poster
The heap stuff is complicated because the stl doesn't provide a function which would be necessary for using a heap in this algorithm. When the value of a node in the heap changes, you need to be able to find the location of node in the heap and bubble it to the right position. As far as I know the stl doesn't provide a way to do this.

This isn't true, in Game Programming Gems 1 the article A* Speed Optimizations by Steve Rabin uses the standard library heap operations plus std::vector to implement a custom priority queue that does exactly what you describe and it's simple.

This is the beauty of the heap operations it gives you alot of flexiablity compared to using std::priority_queue which is a container adaptor that basically uses the standard library heap operations internally but gives a restricted interface not suited for this problem.

Quote: Original post by d000hg
make_heap sounds like it sorts the specified range - so why is sort_heap required? Or does make_heap not fully sort but perhaps do a 'pre-sort'? If I use heaps with push_heap, then starting from an initial empty container do I ever need to call make/sort_heap, or if every element is added with push_heap will that be sufficient?

For what you are doing you can ignore std::sort_heap. std::sort_heap is used to sort a Sequence this essentially the heapsort algorithm for a Sequence which doesn't have much to do with what you are trying to do. You are basically trying to implement a custom priority queue using heaps.

Quote: Original post by SimmerD
I wasn't sure how to use the stl heap functions either, despite having a code example to work from.

As i mentioned earlier there is an article in the Games Programming Gems 1 book called "A* Speed Optimizations" that uses STL heap operations and it's quite simple.

Well I found an algorithmic bug, and after that I was able to geta path all the way across the level in about 20ms (in Release).

I implemented a node for each tile, and a flag to say if it's on the closed list - so the closed list is removed entirely. That got it to 10ms. Then I added a flag to say if a node is on the open list. I still have an open lsit but don't have to search it to see if a node is already in it. Time down to about 5ms.

The only costly operation now is inserting the new nodes into the open list to keep it sorted. I was going to try a binary heap or the lower_bound functions, but the container contains pointers to objects. How can I get the ordering comaprisions to be made on the object pointed to, not based on the pointer's value?

It's looking good though!

Quote: Original post by d000hg
I was going to try a binary heap or the lower_bound functions, but the container contains pointers to objects. How can I get the ordering comaprisions to be made on the object pointed to, not based on the pointer's value?

std::lower_bound and the heap operations are overloaded to take a binary predicate this means you can use any C++ callable entity with it, you can use a free/member function or functor e.g.:

1. using free-function:

#include <algorithm>#include <vector>struct foo {   //......};bool foo_compare(const foo* lhs, const foo* rhs) {   //......}//.....typedef std::vector<foo*> foo_vec;foo_vec l;//....foo* new_val = //.....foo_vec::iterator result = std::lower_bound(l.begin(), l.end(), new_val, foo_compare);// ...std::make_heap(l.begin(), l.end(), foo_compare);

2. using a member function:

#include <algorithm>#include <functional> // mem_fun#include <vector>struct foo {  //....  bool compare(const foo* f) const { /* ... */  }};typedef std::vector<foo*> foo_vec;foo_vec l;//....foo* new_val = //.....foo_vec::iterator result = std::lower_bound(l.begin(), l.end(), new_val, std::mem_fun(&foo::compare));std::make_heap(l.begin(), l.end(), std::mem_fun(&foo::compare));

3. using a functor:

#include <algorithm>#include <vector>struct foo {   //......};struct foo_compare {   bool operator()(const foo* lhs, const foo* rhs) const { /* ... */ }};//.....typedef std::vector<foo*> foo_vec;foo_vec l;//....foo* new_val = //.....foo_vec::iterator result = std::lower_bound(l.begin(), l.end(), new_val, foo_compare());// ...std::make_heap(l.begin(), l.end(), foo_compare());

[Edited by - snk_kid on September 28, 2005 4:43:33 AM]

My A* search uses stl and is quite fast. I have provided the source and the description of the optimizations in a seperate thread. Here is the link to that thread:

A* Optimization

Argh, I keep forgetting the trick with priority queues where instead of updating a value of a node already in the queue you simply insert another copy of the node, and then when the old version appears later it is safely ignored.

Of course this technique makes the stl heap and queue stuff a lot more usable.

snk_kid:

I got lower_bound working fine now, one last question is whether this is used in conjuntion with the heap functions? The kind of seem two different ways to do the same thing - either insert at the iterator returned by lower_bound, or simply use push_heap and pop_heap starting from an empty open list - this will ensure it's always a valid binaray heap I think?
Am I correct here, and is either method inherently faster for this use? In theory since all I want from the open list is to find the smallest element, a binary heap does less work so may be quicker?