Implementing A* - open_list

Kirk D. · 2012-10-16T01:48:22

I'm implementing an A* algorithm (mostly for fun and conceptual learning), and the open_list needs to do two things. 1) act as a priority queue for the purpose of searching closest nodes first, and 2) I need to determine if a node is already in the open_list before adding it. (2) is the case when I ask for neighbors of the current node and don't want to inadvertantly add a node twice to the list. (1) is easily done (in C++) with std::priority_queue, but I cannot efficiently search a PQ for a pre-existing node. (2) is easily done with a std::map, but I cannot use it as a priority queue The only answer I see for this right now is to have two parallel structures that I make sure I keep consistent. Any other option that I'm overlooking??

Artificial Intelligence Programming

Started by kirkd October 04, 2012 10:05 PM

9 comments, last by ankhd 11 years, 6 months ago

ankhd

2,304

October 16, 2012 01:48 AM

Hi. The way I did this was to have a bool inlist[n][m] that match your grid size then set it when you first come across the node. Then when done rest this list. I did it with vectors.