In many cases, a game already has some sort of node structure allocated for the AI, like waypoints in an FPS game, or tiles in a 2d game. You can simply add some fields to that structure for A* like given cost, parent *, final cost. And then let your A* use pointers to your tile/waypoint class.

Quote:

Original post by d000hg Can this system cover a path with waypoints where you go through the same tile multiple times?

A* paths will never overlap tiles.

I'm working now on storing a node per tile and just referencing these. I'll let you know how it goes...

One question - which STL containers are random access and which are not? My docs tell me things like lower_bound have different orders depending on this but I can't find a definitive list. Vector MUST be, and list NOT but what else?

And as for those heap functions - I can't understand them, the sample in VS6 doesn't fully sort them in the make_heap function. Is there a tut on using these somewhere?

Quote:

Original post by d000hg One question - which STL containers are random access and which are not? My docs tell me things like lower_bound have different orders depending on this but I can't find a definitive list. Vector MUST be, and list NOT but what else?

Quote:

The number of comparisons is logarithmic: at most log(last - first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first.

So std::list can be used but for random accessible iterators it will be faster. Any container can have random accessible iterators it doesn't have to be a standard library containers.

C-style static/dynamic arrays can be used there iterators are simply plain old pointers and they are a model of the Random Access Iterator Concept.

Containers provided by the C++ standard library that have random accessible iterators are std::vector & std::deque.

Quote:

Original post by d000hg And as for those heap functions - I can't understand them, the sample in VS6 doesn't fully sort them in the make_heap function. Is there a tut on using these somewhere?

Small one here at the bottom in the "Example" section then check some of the links in the "See Also" section.

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 vector/deque, the push_heap function is of Logarithmic order, but it's also recommend I use a map - so I can sort nodes by their cost, but also look them up based on the (X,Y) tile position. If I use a map with (X,Y) as the key, can I still get the fast insert functionality or am I forced to put up with linear order for inserts? I can't use hash_map so don't suggest that!

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]