# 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.

## Recommended Posts

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

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 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

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633654
• Total Posts
3013168
×