A * what is the best data structure for open dialing?

Question

Im developing A * for the first time, and I used priority_queue for the open set, until I realized that you need to check if the nodes are in the open set, not just the closed one.

The fact is that you cannot sort out the priority order. So why does everyone recommend a priority queue for open dialing? Is this an even better option? I think the only way to repeat this is to make a copy so that I can pop up from it (huge cost).

What is the best data structure used for A *?

Answer 1

Priority Queue (PQ) is an abstract data structure (ADS). They can be implemented a lot. Unfortunately, priority_queue, which comes with the C ++ standard library, is quite limited, while other implementations are much better suited to implement A *. Spoilers: you can use std :: set / multiset instead of std :: priority_queue. But read on:

So, what do you need from the priority queue for implementing A *:

• Get the least cost node
• Reduce the cost of custom elements

Any priority queue can do 1., but for 2. you need a “modified" priority queue. Standard Lieb cannot do this. In addition, you need an easy way to find entries in the priority queue to find out where to decrease keys (if A * finds the best path to an already open node). There are two main ways to do this: you store the handle of the priority queue element in your node graph (or use a map to store these descriptors for each node graph) - or you insert the graph nodes yourself.

In the first case, when you store descriptors for each node, you can use std :: multiset for your priority queue. std :: multiset :: first () will always be your "low cost" key, and you can reduce the key by removing it from the set, changing the value and reinserting it, and updating the descriptor. Alternatively, you can use the variable priority queues from Boost.Heap that directly support the reduce-key.

In the second case, you will need some kind of "intrusive" binary tree - since your search paths themselves should be in the priority queue. If you don't want to roll back your own, see Ordered Associative Containers in Boost.Intrusive.

Answer 2

The topic is very large, I suggest you read this page if you want to know different possibilities and understand well what data structure is adapted to your situation: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#set- representation

In my case, the binary heap was a good balance between complexity for implementation and execution, which was exactly what I was looking for. But maybe you are looking for something else?

The rest of the document is a very good link for A * for game development http://theory.stanford.edu/~amitp/GameProgramming/index.html

Answer 3

They mean that the priority queue does not necessarily belong to the class std :: priority_queue, which comes with the language. If the built-in one does not do what you need to write your own or find another.