the stl vector class in relation to pathfinding
Hm...well i just had a quickie question here. I went to the SGI STL website...but I couldn't find what I was looking for on there.
I have been working on this A* algorithm the past night or two. Today I decided to debug it to see where my problem lies, and it turned out that the algorithm completely works (at least for the test case i have tested it on so far) except for one key part.
If you are familiar with the A* algorithm, then you know that as you search each node, you keep track of its parent node. (If you are not familiar with A*, a really good beginners tutorial is at this website: http://www.policyalmanac.org/games/aStarTutorial.htm I learned a lot from it).
But anyways, back to the topic. In this algorithm there is an Open List and a Closed List, per say. The Open List contains nodes that have been added to the list of nodes to "explore", and each time you recurse you grab the one node from the Open List that contains the "least cost" and move it to the Closed List.
Well, for my Open List and my Closed List I am using two std::vector objects (I have thought about using linked lists as well). Each node is a PATHNODE pointer (therefore each vector is an array of PATHNODE pointers).
Well, it seems that when I initially assign a node its parent, it is working fine, but when I change the node from the Open List to the Closed List it loses the pointer to its parent. I think this is a problem with how I am using std::vector.
If your object is allocated on the heap and is a pointer, and then you add it to a std::vector, and then you erase it from the std::vector, does the std::vector go and destroy it in the heap? Or maybe when I add it to a std::vector, std::vector creates a seperate copy of it somewhere else in memory so the pointers are not the same?
Just wondering how std::vector handles arrays of pointers basically...when adding and deleting from the array...
I might change and use std::list (it is a double linked list), but i dont know how it handles its erase() and push() functions either.