Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Frankie68

Priority Queues (heaps), STL or code it yourself?

This topic is 5653 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

Hello everyone! I am implementing the A* algorithm and I want to use a Priority Queue to keep track of the open nodes. But I think that the following problem is unrelated to the algorithm. I searched on the internet for some nice implementations, but it was all using an array. But that is a bit of a problem here, since I cannot say at the beginning of a search how many nodes I want to store. Using the absolute maximum (128 * 128 (size of the map) ) is not an option, because the memory usage will be enormous, because there will be more than one search at a time. So I implemented my own (using pointers), but that isn''t as simple as I first thought. It works, but I really have the feeling that it could be more faster. I have never used STL before (I always wrote my own data-structures), and I was hoping that someone-else has experience with a problem a like mine and was wiling to help... To put it in a question: how can I store the nodes (sorted by estiminated length of total path) in a data-structure only using a reasonable amount of memory?

Share this post


Link to post
Share on other sites
Advertisement
I wrote my own heap/priority queue implementation using a single array of pointers. I just had to keep track of how much of it was in use and how much capacity there was, and when the in use was about to exceed the capacity, I''d allocate a new array of double the capacity, copy everything across, point the structure at the new array, delete the old array, and double the capacity variable.

To be honest though, these days I would use an std::map to store the nodes and only replace that with a home-grown structure if performance was really too low. (Which is doubtful, as the std::map uses effective tree-balancing trickery that I never learned in university. ) The map would have an integer as the key/sort criteria, and the pointer to the node would be the value. You just have to calculate the estimated path length before you add a node to the map, and it''ll handle the sorting for you. You then get a list of key/value pairs you can traverse from begin() to end().

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
I think that because the binary heap structure is made for arrays you should go for std::vector, i used it once to implement a binary heap and it worked perfectly. Vectors can be approached just like arrays for accessing/changing existing elements, and you use push_back and pop_back to add/remove elements. Thus, when a new element is put into the queue you push_back it and then let it 'float up', and when you want to pop an element off the queue you grab the top element, move the last element to the top position, pop_back the vector, and let the top element 'sink down'.

Marijn

[edit: oh by the way, i think most STL implementations actualy have a std:riority_queue class, which is exactly a binary heap.]

[edited by - marijnh on March 31, 2003 5:38:11 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by marijnh
oh by the way, i think most STL implementations actualy have a std:: priority_queue class, which is exactly a binary heap.



std:: priority_queue is a required component of the STL.

Furthermore, the std:: priority_queue container adaptor relies on the std::make_heap(), std:: push_heap(), std:: pop_heap() and std::sort_heap() functions which you can use on any iterator range yourself.


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]


[edited by - Fruny on March 31, 2003 5:53:33 AM]

Share this post


Link to post
Share on other sites
std:: priority_queue is a good choice, but a slightly too general purpose hammer for A*. There exists priority queue implementations that are better suited for A* than a heap. But just go with std:: priority_queue, it's probably fast enough for you.

[edited by - civguy on March 31, 2003 6:11:27 AM]

Share this post


Link to post
Share on other sites
Could you elaborate on those other priority queue implementations? Or give a link or something... i''m wanna know about them!

Marijn

Share this post


Link to post
Share on other sites
It''s a pathfinding algorithm. Search Google for in depth explanations, or check out the Articles & Resources section of GameDev.net.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!