Jump to content
  • Advertisement
Sign in to follow this  
sled

Help fix my A* Design

This topic is 4233 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.
/**
 * This class is used to sort the priority_queue of paths. The lowest cost
 * path should end up at the top (aka the front).
 */
template <class T>
class Prioritize {
public:
     bool operator() ( const Path<T>* p1, const Path<T>* p2 ) const {
         return p1->Cost() > p2->Cost();
     }
}; 


/**
 * This is the default Heuristic to use if one is not provided. It simply
 * returns an estimate of 0.0f. This means that the best path will be found,
 * but it will take extra work then if a good Heuristic was supplied.
 */
template <class T>
float DefaultHeuristic(T* currentLocation, T* destination) {
	return 0.0f;
}


/**
 * This function is used to find the shortest path in a directed graph between
 * a start node and destination node.  start and destination must both be contained
 * in the graph. The shortest path is calculated used the A* algorithm.
 */
template <class T>
Path<T>* FindShortestPath(Graph<T>* pGraph, Path<T>* start, T* destination,
						  float Heuristic(T* currentLocation, T* destination) = DefaultHeuristic  ) {

	// Form a one-element queue consisting of a zero-length path that
	// contains only the root node
	priority_queue< Path<T>*, vector< Path<T>* >, Prioritize<T> > pathQueue;
	pathQueue.push( start );

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!