A* path planning
May 14, 2006 02:04 PM
Hi, i'm trying to write an A* algorithm but i'm getting a bit stuck on a certain topic.
i have a std::vector called OPEN and push back the nodes that are due for checking on here. i also have a closed and a path vector so I can eventually build a path for my agent to follow.
The only problem i'm having is that i need to find the lowest f value in my OPEN vector. i can find it right enough its just that how do i pop it from the vector when it probably isn't the last item in the vector?
Hope I make sense with this problem,
Phill.
183
May 14, 2006 02:17 PM
Seems like what you need is a priority queue rather than a normal vector for storing the open nodes.
864
May 14, 2006 08:41 PM
... or use the STL algorithm sort() to find the lowest cost item, then reinsert the remaining items into a new vector. Not overly efficient, but it would work.
Alternatively, use the priority_queue as mentioned, or a std::map or std::multimap.
Here's one adaptor for std::multimap I made some time ago... I was storing pointers so I've made a slight change to SearchQueue::contains()... hopefully it compiles as is... feel free to use and abuse it as you see fit (I'm posting it for free and fair use by anyone... no rights reserved... just don't blame me if it breaks under some uses! ;) ).
Cheers,
Timkin
Notes: SearchQueue::value_type is of type std::pair<Key,Type>, meaning that an object of this type has two attributes: first of type 'Key' and second of type 'Type'. So, for example, pop() returns an object of this type.
Which brings me to the point that pop() actually returns a copy of the value_type stored... so be careful with what you're storing and how it gets copied. ;)
Alternatively, use the priority_queue as mentioned, or a std::map or std::multimap.
Here's one adaptor for std::multimap I made some time ago... I was storing pointers so I've made a slight change to SearchQueue::contains()... hopefully it compiles as is... feel free to use and abuse it as you see fit (I'm posting it for free and fair use by anyone... no rights reserved... just don't blame me if it breaks under some uses! ;) ).
Cheers,
Timkin
#include <map>template <typename Key, typename Type>class SearchQueue{ public: typedef std::multimap<Key,Type> container_type; typedef typename container_type::key_type key_type; typedef typename container_type::mapped_type mapped_type; typedef typename container_type::value_type value_type; typedef typename container_type::size_type size_type; typedef typename container_type::iterator iterator; typedef typename container_type::const_iterator const_iterator; private: container_type queue; public: SearchQueue():queue(){} ~SearchQueue(){ queue.clear(); } SearchQueue(const SearchQueue& rhs){ if (!rhs.queue.empty()) queue.insert(rhs.begin(),rhs.end()); } iterator begin(){return queue.begin();} const_iterator begin() const{return queue.begin();} iterator end(){return queue.end();} const_iterator end() const{ return queue.end();} size_type size() const { return queue.size();} void clear() { queue.clear();} bool empty() const { return queue.empty();} iterator insert(const key_type& _Key, mapped_type& _Object){ return queue.insert(value_type(_Key,_Object)); } void erase(iterator _Where){ queue.erase(_Where); } value_type pop(){ value_type first = *queue.begin(); queue.erase(queue.begin()); return first; } iterator contains(const mapped_type& _Object){ iterator qIter = queue.begin(); for (; qIter != queue.end(); qIter++){ if (_Object == qIter->second) return qIter; } return qIter; }};Notes: SearchQueue::value_type is of type std::pair<Key,Type>, meaning that an object of this type has two attributes: first of type 'Key' and second of type 'Type'. So, for example, pop() returns an object of this type.
Which brings me to the point that pop() actually returns a copy of the value_type stored... so be careful with what you're storing and how it gets copied. ;)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
