I'm trying to implement a generic A* system that can be applied a generic directed graph (it's nodes can be of any type). The problem that I am having now is getting my heuristic function to the Prioritize class so it can be used to sort the priority queue of paths. Any ideas? Let me know if you want me to post more code. I just wanted to keep it as simple as possible.

Give the Prioritize object a constructor which accepts a custom heuristic, and uses the default heuristic otherwise.

Then, construct a prioritize object with the custom heuristic and pass it to the priority_queue constructor.

How can I pass a prioritize object to the priority_queue constructor? Right now I'm passing a class...if I try to pass an instance of the object, the compiler complains.

Thanks for the help.

You can't pass classes to constructors, so there's obviously something else you're not understanding. The constructor you're calling there isn't taking any parameters, and the classes you're 'passing' are going to the template instantiation, not the constructor per se.

Either way, if you're using std::priority_queue, may I suggest that you don't? Its functionality is severely restricted in ways that are likely to cause problems with this sort of algorithm.

What would you suggest using instead of std::priority_queue? (Learning to be effective with C++ seems to be a long process for me)

[Edited by - sled on October 17, 2006 9:51:55 AM]

priority_queue< Path<T>*, vector< Path<T>* >, Prioritize<T> >   pathQueue(Prioritize<T>(Heuristic));

Quote: Either way, if you're using std::priority_queue, may I suggest that you don't? Its functionality is severely restricted in ways that are likely to cause problems with this sort of algorithm.

True. What would you suggest as a replacement?

Typically you need access to the middle of the structure, so almost any container will do in that regard. eg. Sorted/unsorted/partially-sorted vector/list/deque. I think my last implementation used a deque, with insertions into the relevant point as found by binary search (upper_bound, or lower_bound, one of those two).

It's worth experimenting to see which one works best for your particular problem space. Although keeping it as a sorted heap makes intuitive sense when you think about the need to continually pull the best node off the queue, you have to bear in mind that typically you add more nodes than you will remove, so you're spending a lot of your time reshuffling nodes you're never going to use, and possibly adding overhead to the 'add' operation when you should perhaps streamline 'add' in preference to 'get next'. I seem to recall that this is the reason why one person found that keeping the open list unsorted was fastest for him.

Kylotan, adding to the middle of a vector or deque is an O(n) operation. Horridly expensive.

The STL uses a heap to implement it's priority queue -- O(lg n) sorted insert.

Wouldn't it be a good idea to at least get the A* algorithm working using a priority queue, and then speed up the "get next" and "add" abstractions?

Isn't it best to come up with a good design and implement it so it is working rather then trying to get the best design on the first shot. And I thought premature optimization is a bad idea. Don't you want to profile and see what your bottleneck is/whats taking up the most memory?

Here's the basic outline of how I constructed my generic, templated OO implementation of A*.

There were two components to my implementation: a search tree and a search manager. The search tree could be operated on to expand nodes and queried to return costs of paths and path segements. It held sole responsibility for implementing the mechanics of operations on the tree. The search manager was responsible for implementing the particular search algorithm (in this case A*). This structure permitted me to use any tree structure with any search algorithm, by defining a standard interface between the two based on common search operations.

Since the search manager needs to know how to talk to the search tree (to operate on it and query it), I used a base tree class to define the tree interface via pure virtual functions. In this way, I could provide a default derived class with default implementations of these functions, while allowing myself the capacity to implement new versions of methods of the tree later through inheritance.

In addition to this generality, I also implemented a template wrapper class for my search queue, which encapsulated an STL container (given as a template parameter, along with the template node type and template return type of the cost function). The default container was a std::multimap.

Here's the basic class outline...

PathState
- the templated base type used to identify a point in the search state space, Templated on the 'Cost' type and the state space type 'State' (usually a coordinate, but might be some other point type in a configuration space).

PathNode: public PathState
- the templated derived type used to identify a searched state (the common search 'node')

PathTreeBase
- defines the templated interface to the PathTree class (meaning iterators for the tree as well as virtual methods for expanding about a node, deleting nodes, pruning subtrees, grafting subtrees, querying costs, defining an action set (the set of operators for generating expansions on the tree)). Defines the PathNode and PathState types depending on template parameters. Stores a pointer to a root PathNode object, a reference to a goal PathState object and encapsulates a std::list templated on the action type for storing the action set.

PathTree: public PathTreeBase
- the derived type used to implement the users preferred tree operations


SearchQueue
- templated wrapper class for storing (Cost,Node) pairs and accessing them prioritised on Cost.

SearchManager
- the templated (on derived tree type) class for accessing the search algrithm. Additional search algorithms could easily be implemented by making this a template base class and deriving classes for each different algorithm.

Here's a snippet of how this gets used. 'actionset' is defined elsewhere and is basically of a type that is a list of possible actions. This would typically be within the definition of the object that is moving around the state space... so an NPC, or AI controlled vehicle, etc.

typedef PathState<double,CARTESIAN2i>    state_type;typedef PathTree                         tree_type;typedef SearchManager<PathTree>          search_type;int main(void){	CARTESIAN2i start(0,0);	CARTESIAN2i goal(10,5);	tree_type	mytree(actionset,goal);	search_type	mysearch;	bool result = mysearch.findBestPath(start,goal,&mytree);        return 0;}

With this implementation its trivial to define trees based on different action sets and different state spaces. All domains specific aspects of the search are hidden within the derived PathTree class and the types given as template parameters, meaning the user only has to worry about one class to interface this implementation to their search domain.

If you have any particular questions, I'll do my best to answer them. Please understand though that I cannot at this time share any specific code.

Cheers,

Timkin