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)