A* and Mac Game Programming Book

cloke
Unregistered
 
Post: #1
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.

Code:
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
}
Quote this message in a reply
Member
Posts: 111
Joined: 2002.06
Post: #2
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 http://www.meandmark.com.
Quote this message in a reply
cloke
Unregistered
 
Post: #3
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.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Upcoming Multiplatform Game Programming Book for Beginners JazonYamamoto 3 987 Apr 14, 2014 05:55 PM
Last Post: JustinFic
  [Book] Cocos2d for iPhone 1 Game Development Cookbook NathanBurba 1 5,218 Jan 8, 2012 05:40 PM
Last Post: mmztech
  Game engines with object programming JonnyThunder 3 8,065 Aug 16, 2010 10:42 AM
Last Post: SethWillits
  free mac game programming book jaked 4 6,611 Jun 8, 2009 12:48 AM
Last Post: SethWillits
  Book dedicated for iPhone Game Development linlord 3 4,192 Apr 1, 2009 09:55 AM
Last Post: linlord