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

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.