-
.empty()
I am implementing a path-finding algorithm and I can't understand the following:
First of all this function is called:
Code:
int UpdateMap(unsigned int startx, unsigned int starty, unsigned int endx, unsigned int endy)
{
PathFind<WorldSearchNode> pathfind;
WorldSearchNode StartNode;
StartNode.x = startx;
StartNode.y = starty;
WorldSearchNode EndNode;
EndNode.x = endx;
EndNode.y = endy;
pathfind.SetStartandGoalStates(StartNode, EndNode);
unsigned int xSearchState;
unsigned int xSearchSteps = 0;
do
{
xSearchState = pathfind.PathFindStep();
xSearchSteps++;
}
while(xSearchState == PathFind<WorldSearchNode>::PATH_FIND_PROCESSING);
if (xSearchState == PathFind<WorldSearchNode>::PATH_FIND_SUCCEEDED)
{
WorldSearchNode *Node = pathfind.GetSolutionStart();
int steps = 0;
Node->CopyNodeToWorld();
for(;;)
{
Node = pathfind.GetSolutionNext();
if (!Node)
{
break;
}
Node->CopyNodeToWorld();
steps++;
}
pathfind.FreeSolutionNodes();
return 1;
}
else if (xSearchState == PathFind<WorldSearchNode>::PATH_FIND_FAILED)
{
return 0;
}
return 0;
}
As can be seen, the first function to be called from within this function is the SetStartandGoalStates, which is here:
Code:
void SetStartandGoalStates(RobotState &Start, RobotState &Goal)
{
xCancelRequest = FALSE;
xStart = AllocateNode();
xGoal = AllocateNode();
xStart->xRobotState = Start;
xGoal->xRobotState = Goal;
xState = PATH_FIND_PROCESSING;
xStart->c = 0;
xStart->h = xStart->xRobotState.GoalDistanceEstimate(xGoal->xRobotState);
xStart->f = xStart->c + xStart->h;
xStart->parent = 0;
//push the start node onto the open list
xOpenList.push_back(xStart);//this has made the heap unsorted
//sort heap
push_heap(xOpenList.begin(),xOpenList.end(),CompareHeap());
//initialise path find steps counter
xSteps = 0;
}
Next is the FindPathStep() function, the beginning of which is here:
Code:
unsigned int PathFindStep()
{
assert((xState>PATH_FIND_UNINITIALISED) && (xState<PATH_FIND_INVALID)); //evaluates expression, exits program if false, continues if true.
if ((xState == PATH_FIND_SUCCEEDED) || (xState == PATH_FIND_FAILED))
{
return xState;
}//ensures that if PathFindStep is run after the search has succeeded, we want to return a success.
//If there is nothing left to search then the OpenList will be emptied, we can use this to define failure
//We also need to incorporate the event that the search has been aborted
if (xOpenList.empty())
{
exit(0);
xState = PATH_FIND_FAILED;
FreeAllNodes();
return xState;
}
As can be seen I have a check at the beginning of this function to see if xOpenList.empty() returns true, ending the program if it is. And this is exactly what it is doing. I ran a similar check on xOpenList.empty() directly after push_heap(xOpenList.begin(),xOpenList.end(),Compar eHeap()); and it returned false. So why is xOpenList being emptied by the time I come to check it in FindPathStep?
Any help would be much appreciated.
-
And another thing, I know that assert(....) at the beginning of FindPathStep() is not aborting the program because I commented it out and it made no difference.