A* pathfinding search function, need help

McFury · 11-12-2007, 01:25 PM

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:

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();
		}
	}
}

matsp · 11-12-2007, 02:50 PM

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

11-12-2007, 02:50 PM	#2
matsp Kernel hacker Join Date: Jul 2007 Location: Farncombe, Surrey, England Posts: 15,686	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.
matsp is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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