Jump to content
  • Advertisement
Sign in to follow this  

Hybrid approach of data structure representation of opened list

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



After taking a read on this page,

Amit has suggested to use a

priority queue for ranking management

binary heap for insertion and deletion of opened nodes.


I wonder, if I create 1 std::vector and 1 std::priority_queue in my astar class.

How can I make sure there is actually 1 centralized opened list available.

If 2 inconsistent opened lists are available, they may expose to errors.

Any code example on how to go about doing that?

To keep 2 containers synchronized?

I am a C++ coder.




I'd like to have a data structure that excels at insertion, deletion and looking up?

Which should I choose? I find out that heaps can only have O(n) on minimum + maximum search

My map is about 40x40 cells (a grid)



Edited by lucky6969b

Share this post

Link to post
Share on other sites

Why not use a std::set or a std::multiset (or a std::(multi)map if you need to keep more information) ordered by total cost?


Alternatively, you could implement a heapq. http://stackoverflow.com/questions/29981545/what-is-the-algorithm-used-by-pythons-heapq-merge-known-as


Edit: This morning I realized I was not complete here, sorry for that.

I usually have a set of open+closed positions (ordered by position) that gives the best found solution at the position (without estimate, as an estimate is always the same for the same position). That set thus tells me whether it makes sense to bother adding the new point.

If it is useful, I have a set of open points, ordered by total cost (walked distance + estimate), for getting the next point to try.

Edited by Alberth

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!