.empty()

This is a discussion on .empty() within the C++ Programming forums, part of the General Programming Boards category; I am implementing a path-finding algorithm and I can't understand the following: First of all this function is called: Code: ...

  1. #1
    Funniest man in this seat minesweeper's Avatar
    Join Date
    Mar 2002
    Posts
    801

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

  2. #2
    Funniest man in this seat minesweeper's Avatar
    Join Date
    Mar 2002
    Posts
    801
    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.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21