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.

I used a priority_queue and a deque as the underlying structure for my open list and then a regular vector for my closed list.

As for your question on vectors, the vector won't destroy the memory on the heap. Also, it doesn't internally make a secret copy with a different address. I don't know why what you described is happening. If you want pm me and you can send me your function and I can look at it. Or you can post it here if you like.

A priority queue is a good idea. That hadn't even occurred to me. But anyways, here is some of my code. I will quote important parts and some explaining in the post, and then I think I will attach the whole .h file at the bottom if you want to look at the whole thing.

First, here is my structure for a node:

Code:

struct PATHNODE
{
	int wx, wy;
	int fcost;
	
	PATHNODE *parent;

	PATHNODE () 
	{ 
		fcost = 0;
		wx = 0;
		wy = 0;
		parent = NULL;
	}

	bool equals ( PATHNODE *b )
	{
		if ( (this->wx == b->wx) && (this->wy == b->wy) )
			return true;
		else return false;
	}
};

Nothing big. wx and wy are the x and y coordinates in terms of where the node is on the map. fcost is how much it will cost to get to that node. My Open List and Closed List are declared as such:

Code:

std::vector < PATHNODE* > OpenList;
std::vector < PATHNODE* > ClosedList;

So then I call a function called CalculatePath, here is the function prototype:

Code:

std::stack < PATHNODE* > CalculatePath ( int wx1, int wy1, int wx2, int wy2, MAP_DTP &map )

It takes as input the starting coordinate and the target coordinate on the map, and also the map. Using that information it does some initializations work and then calls FindPath() to do all the recursive stuff and actually find the path. It returns a stack. The stack it returns is the final path that it calculates.

Here is the FindPath() function, which is probably the heart of it all:

Code:

bool FindPath ( PATHNODE *targetNode, MAP_DTP &map )
{

	if ( OpenList.size() == 0 ) return false;

	//Get the node with the lowest F cost and drop it from the open list
	PATHNODE *currentNode = GetLowestCostOpenListNode ();	
	if ( currentNode == NULL ) return false;
    
	//Now add the current node to the closed list
	ClosedList.push_back ( currentNode );

	//Add all adjaced nodes to the open list
	AddAdjacentNodesToOpenList ( currentNode, targetNode, map );

	//Check to see if target square is on the open list
	if ( OpenListContains ( targetNode ) )
		return true;

	return FindPath ( targetNode, map );
}

Now, like I said my problem is most likely occurring when I take the node out of the Open List and add it to the Closed List. Somewhere in there it is losing its connection its parent node. When I assign the parent node, it goes through this function:

Code:

void AddNodeToOpenList ( PATHNODE *currentNode, int wx, int wy, PATHNODE *targetNode,
							MAP_DTP &map )
{
...I have deleted most of the code in this function for the sake of
 this post.  The following code is the last code in the function, and 
the important code for right now:

	newNode->parent = currentNode;
	OpenList.push_back ( newNode );
}

Now, when I actually take a node OUT of the Open List and put it in the Closed List, it goes through this:

OpenList.erase ( OpenList.begin() + index );

(index being the index of the node to take out of the open list). Meanwhile I have a pointer called temp holding onto that memory that was just erased from OpenList, and it gets returned to my FindPath() function which then assigns it to the ClosedList.

Anyways, that's pretty much all of it. I tried to cut down the code as much as possible because I know people hate reading too much code, so I hope I cut it down enough, but not too much. If you want to read the whole file, I will attach it.

(I made it a .txt file because for some reason it wont let you upload .h files)

Still not sure what would be causing the problem. It look ok from here. Have you tried stepping through it line by line and seeing exactly where the memory becomes invalidated? I know it sounds simple but that's often the answer. Also you might want to just start up a separate project in VC6 to test out some simple test cases. Let me know what happens. I'm at work now but when I get home I will look at it in greater detail.

Ah! I found the problem!

When I add nodes to the Open List, I create the node and then I add it (obviously). Well, I wasnt taking into account that when I added the target node to the Open List, it wasnt the SAME target node in memory as the original target node I created in memory (if you get what I mean). So I just had to reassign the original target node to the new one I created in memory and boom, everything works great.

Thanks for the help.