I''m trying to implement A* in a 2D tile based game, but it''s giving me some strange results. Instead of finding the most direct route, the algorithm always finds the worst route. My unit goes up and down the map, traversing every square, until it finds the destination and stops. I''m writing the game in Java. What follows is the generic A* code itself:

 public List findPath(Tile startNode, Tile goalNode)
  {
    PriorityList openList = new PriorityList();
    LinkedList closedList = new LinkedList();

    startNode.costFromStart = 0;
    startNode.estimatedCostToGoal =
        startNode.getEstimatedCost(goalNode);
    startNode.pathParent = null;
    openList.add(startNode);

    while (!openList.isEmpty())
    {
        Tile node = (Tile)openList.removeFirst();
        if (node == goalNode)
        {
            // construct the path from start to goal
            return constructPath(goalNode);
        }

        List neighbors = node.getNeighbors();
        for (int i=0; i 

The "costFromStart < neighborNode.costFromStart" part is commented out because it causes frequent crashes.  The root of the problem appears to be this.  The list that findPath returns contains all the tiles it had to look at, not just the best ones.
While testing I noticed that getEstimatedCost was returning weird values.  The numbers seemed mostly correct, but sporadic clusters of 1s appeared.  

I''m using the Manhattan distance formula for the heuristic: Math.abs(p2.x - p1.x) + Math.abs(p2.y - p1.y).  

Any help is greatly appreciated.  Thanks.   

i havent looked over all the code, but here is an idea...

how are you constructing the final path?
you should be taking the last node and iterating backwards though it to get the path calling List.push_front, are you doing this correctly?
could you post the constructPath(goalNode) code?

The method to build the actual path is as follows:

  protected List constructPath(Tile tile)  {    LinkedList path = new LinkedList();    while (tile.pathParent != null)    {      path.addFirst(tile);      tile = tile.pathParent;    }    return path;  } 

This seems to work fine. It''s just that findPath is returning tiles without any regard for efficiency. Using print statements, I found that "closedList.remove(neighborNode)" is never called, even with the second part of the main if not commented out. I''m pretty much stumped.

well first off you never want to remove anything form the closed lest anyway. Otherwise the node would get traversed again.

i think the problem is within:

if ((!isOpen && !isClosed))// || //costFromStart < nighborNode.costFromStart)            {                	neighborNode.pathParent = node;	neighborNode.costFromStart = costFromStart;	neighborNode.estimatedCostToGoal = neighborNode.getEstimatedCost(goalNode);	if (isClosed)	{		closedList.remove(neighborNode);	}	if (!isOpen)	{		openList.add(neighborNode);	}}  

Note on your logic:
The first 'if' tests "not open and not closed" then inside of that you test "is closed" and "not open", the "is closed" test will always fail, if it didnt then the first if would have faild. The second "not open" will always be true for simular reasons.

An idea to fix your problem:
I think your open list is behaving like a closed list. Try removing the first "not open" test and see what happens. If that works and you want me to explain why then let me know. If it doesnt work i'll post my code and you can compare the two.

PS: im assuming Tile is really a pointer to a tile, right? same with PriorityList and LinkedList. If you really want to hide the *'s then I'd suggest adding a prefix liek "LP" or something to the type name to make it easier to read, or better yet, just dont hide them.


[edited by - TheDarkening on January 3, 2004 8:28:50 PM]

No luck yet. I''ve tried changing the logic, but it still wants to cross every tile. After looking closely at getEstimatedCost that appears to be working properly. I''m out of ideas on what could be causing this. Thanks for the feedback, though.

k, i don''t see anything wrong with the code so i''ll just post mine. Have a look at it and see if you can figure out what is causing yours to fail. Note: I''m not saying my way is a better way of doing it.

Another thing that might help is every time you add a node to the closed list print both the closed list and open list, that might give some insite as to whats happening. And make sure you use a small map while debugging this, like 5 by 5 at most.

//**************************************************************void calcAStarPath( const CGrid& worldMap, int x, int y, int tX, int tY, AStarList& openList, AStarList& closedList, AStarList& path )//**************************************************************{	bool failedToFindPath = false;	// make the target node	AStarNode targetPoint(NULL, tX, tY, 0);	// add start point node to open list	AStarNode* startPoint;	startPoint = new AStarNode(NULL, x, y, 0);//	openList.push_back(startPoint);	// set shortest open to start point node	AStarNode* shortPoint;	shortPoint = startPoint;	AStarList::iterator itr;	while (*shortPoint != targetPoint)	{		// remove shortestOpen from openList		itr = checkList(openList, shortPoint);		if (itr != openList.end())			openList.erase(itr);				// add shortestOpen to closedList		closedList.push_back(shortPoint);			    // for each child of shortPoint		AStarNode* childNode;		AStarNode* oldShortPoint = shortPoint;		shortPoint->assignChildren(worldMap);		for (int i = 0; i < oldShortPoint->getNumChildren(); ++i)		{			childNode = oldShortPoint->getChild(i);			if (childNode == NULL)				continue;			// if the child is in the closed list then there is nothing left to do for this child			if (checkList(closedList, childNode) != closedList.end())				continue;			// update the F value for the node			childNode->calcF(calcHeuristic(childNode->getX(), childNode->getY(), tX, tY));			// if the child is not in the open list then add it			if (checkList(openList, childNode) == openList.end())			{				openList.push_back(childNode);			}						// if this path to the child node has a snorter path then the currently set shortest path then make this path the new shortest path			if (*childNode < *shortPoint)			{				shortPoint = childNode;			}		}		// if the open list dries up then there is no path to the target node		if (openList.empty())		{			failedToFindPath = true;			break;		}		// if none of this node''s children had a shorter path then this node, then 		// we are at a dead end of some sort, find the next shorest path in the  		// open list and hope it has better luck at getting to the target node.		if (*shortPoint == *oldShortPoint)			shortPoint = findNewShortPoint(openList);	}		// couldnt find the target, leave in disapointment...	if (failedToFindPath)		return;	// figure out the path by taversing the parent nodes, starting at the target.	// the starting point node will not be added to this list or the Dude will spend 	// a tick moving to where he already is	AStarNode* p = shortPoint;	while (p->getParent() != NULL)	{		path.push_front(new AStarNode(NULL, p->getX(), p->getY(), 0));		p = p->getParent();	}}

quote:
You also don''t test for when you actually get to the goal node, you just search until you run out of places to search (which would be after exploring the whole map)

ya he does.

if (node == goalNode){   // construct the path from start to goal   return constructPath(goalNode);} 

quote:
I''m not seeing any code that would direct your search. All you do is explore randomly (well, not randomly, in the order the neighbors are stored).

well his open list is PriorityList which should be storing the node with the best total cost at the front.

Although, Zeugmal, you set the cost from start and cost to goal, but do you ever add these together to se the total path?
You might also want to look over the PriorityList code and see if its storing the lowest-total-cost or the highest-total-cost at the front.

Okay, first thing...

            boolean isOpen = openList.contains(neighborNode);            boolean isClosed =                closedList.contains(neighborNode);   

If neighborNode is in the open list, then it isn't in the closed list, so you don't need to search the closed list unless the open list check returns false. This will save you some cycles!

Second, you absolutely must consider the problem of examining a new path through a node already in the closed list and testing whether the cost of the new path is lower than the cost of the old path. You can't ignore this!

MOST IMPORTANT: If you find that the cost is lower, you MUST graft the subtree below the node in the closed list onto the neighbor you just expanded AND THEN update that entire subtree cost given the new cost to the neighbor (You're currently not doing this because of the bug you believe you have in your estimated cost). Then you can remove the old node in the closed list and replace it with the new one. Intelligent bookkeeping will save you some memory by not keeping extra copies of nodes... but be careful.

I believe your problem is being caused by NOT updating this subtree when you find a better path. Since you are dealing with a tile based world and presumably, you are expanding in four directions, then essentially what is going to happen with your current code is that it is going to propogate the highest cost so far encountered through a given node to all nodes in the subtree below it, because there is currently no way of reducing that cost estimate in the code you have presented.

                if (isClosed)                {                    closedList.remove(neighborNode);                }     

Furthermore, this line is going to screw things up. If the neighborNode is already in the closed list, then there is a very good chance that you have expanded the subtree below it... so deleting the neighborNode from the closed list is going to disconnect the subtree already searched from your search tree (which is now stored among the open and closed lists) and presumably screw up your path returned.

I hope these points help you to clean up your algorithm.

Good luck,

Timkin

[edited by - Timkin on January 4, 2004 8:17:41 AM]

Thanks for the help, everyone. I''ve got the algorithm working properly now. TheDarkening''s suspicions were correct about the closed list behaving like an open list. All I had to do was reverse the lists.