A* pathfinding search function, need help

[McFury]

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)


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.GetN ode(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]

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