Jump to content

  • Log In with Google      Sign In   
  • Create Account


#Actualslicer4ever

Posted 04 October 2012 - 08:59 PM

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


for #2, i generally add an ID field to my node, i compare this ID to my generator, if it's != then the node has not been added to the open or close list, as such, i add it, and I then update it's ID.

this of course means that theoretically it's possible for the generator to eventually loop a 32 bit ID, but the odds of that are increadibly small/unlikely, and a worse case is that a single path is constructed incorrectly.

#1slicer4ever

Posted 04 October 2012 - 06:17 PM

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


for #2, i generally add an ID field to my node list, i compare this ID to my generator, if it's != then the node has not been added to the open or close list, as such, i add it, and I then update it's ID.

this of course means that theoretically it's possible for the generator to eventually loop a 32 bit ID, but the odds of that are increadibly small/unlikely, and a worse case is that a single path is constructed incorrectly.

PARTNERS