8

Im developing an A* for the first time, and I was using a priority_queue for the open set, until I realize you need to check if nodes are in the open set too, not just the close one.

Thing is, you cant iterate over a priority queue..So why everyone recommend a priority queue for the open set? Is it yet the best option? I think the only way to iterate over it is making a copy so I can pop everything from it (enormous cost).

What the best data structure to use on A*?

1

3 Answers 3

7

A priority queue (PQ) is an abstract data structure (ADS). There are many possibilities to implement them. Unfortunately, the priority_queue supplied with the C++ standard library is rather limited, and other implementations are suited a lot better for implementing 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 to implement A* is:

  1. Get the node with the lowest cost
  2. Decrease the costs of arbitrary elements

Any priority queue can do 1., but for 2., you need a "mutable" priority queue. The Standard-Lib one cannot do this. Also, you need an easy way to find entries in the priority queue, to find out where to decrease the keys (For when A* finds a better path to an already opened node). There are two basic ways for this: You store a handle to the priority queue element within your graph node (or use a map to store those handles for each graph node) - or you insert the graph nodes themselves.

For the first case, where you store handles for each node, you can use std::multiset for your priority queue. std::multiset::first() will always be your "lowest cost" key, and you can decrease a key by removing it from the set, changing the value and re-inserting, and updating the handle. Alternatively, you can use the mutable priority queues from Boost.Heap, which directly support "decrease-key".

For the second case, you would need some kind of "intrusive" binary tree - since your pathfinding nodes themselves need to be in the priority queue. If you don't want to roll your own, see the ordered associative containers in Boost.Intrusive.

3

The subject is very large, I suggest you reading this page if you want to know the different possibilities and have a good understanding of which 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 difficulty to implement and performances, which was totally what I was looking for. But maybe you are looking for something different ?

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

-1

They mean A priority queue not necessarily the std::priority_queue class that comes with the language. If the built in one doesn't do what you need it to write your own, or find another.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.