Thread: A* pathfinding search function, need help

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    28

    A* pathfinding search function, need help

    Hi,

    I have been having trouble with a search function. It seems to find the optimal path correctly most of the time, however it runs into trouble and crashes when it needs to filter back through already visited nodes on a path search (at least i "think" thats why its crashes).

    For example it handles well in this situation: (o is the starting point, x is the target)

    Code:
             x        
                       
       ------         
             ------   
       ------         
                       
             o
    But not in this situation:

    Code:
          x          
          
      --------
      |      |
      |  o   |
      |      |      
    
    
    .
    If anyone could point out in the code why its failing on this I would be very thankful.

    Code:
    void GraphSearch::Search()
    {
    	IndexedPriorityQLow<double> pq(mFCosts, mGraph.NumNodes());
    
    	pq.insert(mSource);
    
    	//Moves target to a valid cell if its invalid
    	if(mTerrain[mTarget] == obstacle)
    		moveTarget();
    
    	while(!pq.empty())
    	{
    		int edgeCount = 0;
    		int NextClosestNode = pq.Pop();
     
    		while(mTerrain[NextClosestNode] == obstacle)
    		{
    			NextClosestNode = pq.Pop();
    		}
    
    		mShortestPathTree[NextClosestNode] = mSearchFrontier[NextClosestNode];
    
    		if(NextClosestNode == mTarget)
    			return;
    
    		EdgeIterator EdgeItr(mGraph.mEdges, NextClosestNode);
    
    		CellEdge* pE = EdgeItr.begin();
    
    		while(edgeCount < MAX_EDGES)
    		{     
    			double HCost = mGraph.GetNode(mTarget).Pos().distance(mGraph.GetNode(pE->To()).Pos());
    			double GCost = mGCosts[NextClosestNode] + pE->Cost();
    			
    			if(mSearchFrontier[pE->To()] == NULL)
    			{
    				mFCosts[pE->To()] = GCost + HCost;
    				mGCosts[pE->To()] = GCost;
    				
    				pq.insert(pE->To());
    				mSearchFrontier[pE->To()] = pE;
    			}
    			else if((GCost < mGCosts[pE->To()]) && (mShortestPathTree[pE->To()]==NULL))
    			{
    				mFCosts[pE->To()] = GCost + HCost;
    				mGCosts[pE->To()] = GCost;
    
    				pq.ChangePriority(pE->To());
    
    				mSearchFrontier[pE->To()] = pE;
    			}
    
    			edgeCount++;
    			if(edgeCount < MAX_EDGES) 
    				pE = EdgeItr.next();
    		}
    	}
    }

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    		while(mTerrain[NextClosestNode] == obstacle)
    		{
    			NextClosestNode = pq.Pop();
    		}
    Shouldn't you check if pq.empty() becomes true in this loop?

    Do you have checks to see if pq is popping/pushing illegally [overflow and underflow]? Always good practice to make such code "safe".

    I have no idea if this is really where the problem lies - it just looks a bit "fishy" to me.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Attempt to write function search()
    By elsewhere in forum C Programming
    Replies: 6
    Last Post: 12-03-2008, 08:18 AM
  2. doubt in c parser coding
    By akshara.sinha in forum C Programming
    Replies: 4
    Last Post: 12-23-2007, 01:49 PM
  3. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  4. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  5. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM