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:

         x        
                   
   ------         
         ------   
   ------         
                   
         o        

But not in this situation:

       x          
      
   ---------
   |       |
   |   o   |
   |       |       

If anyone could point out in the code why its failing on this I would be very thankful.

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

You probably don't want to hear it, but there's an Easy Way to Solve Hard AI Problems.

alexjc