• Advertisement
Sign in to follow this  

Hybrid approach of data structure representation of opened list

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

http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

 

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.

 

https://en.wikipedia.org/wiki/Search_data_structure

 

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)

Thanks

Jack

Edited by lucky6969b

Share this post


Link to post
Share on other sites
Advertisement

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