A* and Mac Game Programming Book

[cloke]

I'm trying to convert the A* example in the Mac Game Programming book to use STL linked lists for the closed and found path list, and to use priority_queue for the open list. The linked list conversion has been no problem, but I seem to be hitting a wall with how to use the priority_queue. The bulk of my issues are in the EvaluateNeighbors code. Below is what I have converted so far, but I end up creating a endless loop by not pushing and popping things properly from the open list.

Does anybody have any suggestions on how to go about converting the book code. Or could someone provide a little pseudo code to help me visualize exactly what is supposed to be done with the open list.

Thanks for any suggestions.

P.S. I've only included the one function. The rest of the code is pretty much straight out of the book with the exception of "AlreadyInOpenList" which I changed to "IsCheaperLocation" which just returns wether or not the new node is cheaper than what is on the top of the open list.

void PathFinder::EvaluateNeighbors(PathLocationPtr parent, std::list<PathLocation> neighborList,
short goalRow, short goalColumn)
{ //Iterator to go over neighbor list.
std::list<PathLocation>::iterator currentNeighbor;

float newCost;
float estimatedCost;
float overallCost;

for(currentNeighbor = neighborList.begin(); currentNeighbor != neighborList.end(); currentNeighbor++)
{
PathLocation p = *currentNeighbor;

newCost = p.GetCostFromStart() + p.GetMovementCost(parent);

if ( this->IsCheaperLocation(&p) || !(this->AlreadyInClosedList(&p)) )
{ // This neighbor is new.
std::cout << "Found cheaper and not in closed list" << std::endl;
p.SetParent(parent);
p.SetCostFromStart(newCost);
estimatedCost = p.EstimatePathCost(goalRow, goalColumn);
p.SetEstimatedCostToGoal(estimatedCost);
overallCost = p.GetCostFromStart() + estimatedCost;
p.SetTotalCost(overallCost);
openList.push(p);
}
else if ( (p.GetCostFromStart() > newCost) )
{
std::cout << "Failed first test" << std::endl;
// This neighbor is improved.
if (AlreadyInClosedList(&p)) {
currentNeighbor = closedList.erase(currentNeighbor);
}
if (IsCheaperLocation(&p)) {
// This entry is improved. Update its cost.
p.SetTotalCost(overallCost);
p.SetCostFromStart(newCost);
p.SetEstimatedCostToGoal(estimatedCost);
openList.push(p);
}
}
// end else if
// Read next neighbor
} // end while
}

[szymczyk]

There are two mistakes in the EvaluateNeighbors() function in the book. First, the line

newCost = p.GetCostFromStart() + p.GetMovementCost(parent);

should be

newCost = parent.GetCostFromStart() + p.GetMovementCost(parent);

Second, the OR (||) in the first if statement should be AND (&&).

I have code that corrects those mistakes that you can download at www.meandmark.com.

[cloke]

Thanks for the update. I was beating my head against the wall just trying to get the book code to work properly.

I'd still like to move the list management to using stl, but the priority_queue is giving me issues with the openList. If anyone has some suggestions for converting it that would be great. I've been able to use the STL linked lists which was a pretty straight forward conversion.