• 9
• 10
• 9
• 10
• 10

A* trouble

This topic is 3980 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm trying to implement A*. Basically it works as long as there is no walls. Kind of defeats the purpose, eh? Some pictures: This works as it should. (I think?) This doesn't. Green dot = starting node Red dot = goal node Blue dots are nodes on the closed list, and white = openlist When it gets to the wall, the current nodes F score is lower than any on the open list. So it's just an endless loop. Not sure why this happens. My loop:
	do
{
iter++;

if( iter > 200 )
return;

for( int i = 0; i < openlist.size(); i++ )
{
node n = openlist.get( i );

if( n.F() <= currentnode.F() )
{
currentnode = n;
}
}

openlist.remove( currentnode );
closedlist.push( currentnode );

if( isgoal( currentnode, e ) )
return;

expand( expansions, currentnode, e );

for( int i = 0; i < expansions.size(); i++ )
{
node n = expansions.get( i );

int newg = currentnode.G + getgcost( currentnode, n );

if( !walkable( n.x, n.y ) )
continue;

if( isgoal( n, e ) )
return;

if( closedlist.contains( n ) )
continue;

if( !openlist.contains( n ) )
{
n.G = newg;
n.parent = ¤tnode;

openlist.push( n );

continue;
}
else
{

if( n.G < newg )
{
openlist.remove( n );

n.G = newg;
n.parent = ¤tnode;

openlist.push( n );

continue;
}

n.G = newg;
n.parent = ¤tnode;

openlist.push( n );
}

}

}
while( !openlist.empty() );
}

Thanks for any help!

Share on other sites
I implemented my pathfinding based on the wonderful article:

A* for beginners

I would check the outline of how A* works and make sure that you are doing all of the steps. It seems to me that you are not doing any sort of sorting to get the lowest value node, and the current node shouldn't be considered when you are deciding which node to go to.

Share on other sites
You're performing a greedy search, rather than A*. Read the suggested article.

Share on other sites
As Timkin said, this is a greedy search. It should still be able to find a path, but there is a bug in the implementation. After going through the do loop, currentnode is no longer on the open list, but you're using it in the loop that finds the open node with the lowest F() value. Actually if F() is returning the cost to the node plus the heuristic value then this is an A* search. Just fix that loop by setting currentnode to a node that is in the open list before entering the loop.

Share on other sites
Quote:
 Original post by VorpyActually if F() is returning the cost to the node plus the heuristic value then this is an A* search. Just fix that loop by setting currentnode to a node that is in the open list before entering the loop.

Where's the heuristic cost computation? Perhaps I'm just blind, but I couldn't see it after looking 3 times! ;)

Share on other sites
The heuristic could be computed in the F() method of the node class. The definition of node isn't given. This would be a rather needlessly procedural first iteration of the implementation, since if it works like that then it means F() is accessing goal and heuristic information from some other namespace that isn't logically related to the goal and heuristics. So...assuming a readable design, this isn't A*.

Actually, I think this isn't a greedy search then, it's plain old shortest path first. Which I guess is greedy in a sense, but I think greedy search usually refers to a search that always expands the node with the lowest heuristic value.

I also noticed another minor bug. You shouldn't return after expanding a node and finding that one of its children is the goal state because it could be a suboptimal path. The path is only known to be optimal when the goal node is the lowest cost node on the open list. This doesn't matter if you don't care about optimality, and the extra length of the found path compared to the opimal path is bound by the difference between the edge that led to the goal and the lowest cost edge that leads to the goal. On the other hand, for any realistic problem your code will actually be slightly faster if that check was removed from the inner for loop, since it only ever returns true once at the very end. It's a redundant check.

Share on other sites
Quote:
Original post by Timkin
Quote:
 Original post by VorpyActually if F() is returning the cost to the node plus the heuristic value then this is an A* search. Just fix that loop by setting currentnode to a node that is in the open list before entering the loop.

Where's the heuristic cost computation? Perhaps I'm just blind, but I couldn't see it after looking 3 times! ;)

I was computating the heuristic in the expand() function.

I've messed with this a little more. It now finds a(it cuts corners, but I'll fix that next) path.

Does this look right?

void findpath( node start, node end ){	start.G = 0;	openlist.push( start );		while( !openlist.empty() )	{		//get node with lowest F score		//the openlist is sorted by the F score		node selectednode = openlist.pop();		if( isgoal( selectednode, end ) )		{                        //having problems with this			//thepath = getpath( start, selectednode );			closedlist.push( selectednode );			return;		}		//check all successor's of the selected node		for( int x = selectednode.x - 1; x <= selectednode.x + 1; x++ )		{			for( int y = selectednode.y - 1; y <= selectednode.y + 1; y++)			{				int newg = 0;				//tile isn't walkable				if( map[x][y] == 1 )					continue;				node successor( x, y );								//don't check out the starting square				if( start.x == successor.x && start.y == successor.y )					continue;				if( closedlist.contains( successor ) )					continue;								//make this successor's parent the selected node				successor.parent = &selectednode;					if( abs( successor.x - selectednode.x ) == 1 && abs( successor.y - selectednode.y ) == 1 )					newg = successor.parent->G + 14; //diagonal move				else					newg = successor.parent->G + 10; //non diagonal move				//if it's on the openlist already...				if( openlist.contains( successor ) )				{					//...and the new path is better then update the G cost					if( newg < successor.G )					{						openlist.remove( successor  );						successor.G = newg;						openlist.push( successor );					}								}				else				{					//push it onto the openlist for the first time					successor.G = newg;					successor.H = getheuristic( successor, end );										openlist.push( successor );				}			}		}		closedlist.push( selectednode );		//sort openlist by F score		openlist.sortf();	}}

Also, every node has the same parent on the closed list. So I can't retrieve the actual path. Can't quite figure that one out.

Thanks for everyone's help so far.

Share on other sites
Quote:
 Original post by VorpyActually, I think this isn't a greedy search then, it's plain old shortest path first.

By which you mean best-first search, which is a generalisation of greedy search... but you are correct, greedy search is usually reserved for best-first searchers on an heuristic function, rather than a path cost function. My bad... not sure where my brain was when I wrote greedy... I certainly meant best-first. Ah well, only human! ;)

Quote:
 I also noticed another minor bug. You shouldn't return after expanding a node and finding that one of its children is the goal state because it could be a suboptimal path. The path is only known to be optimal when the goal node is the lowest cost node on the open list.

In many practical domains this isn't a problem, but you are certainly correct and the OP should take heed. A* guarantees to expand all nodes in a given cost contour before expanding any node in a higher cost contour. Hence, the first time it tries to expand about the goal it knows that the current lowest cost path to this goal node is indeed the optimal solution. If the algorithm is forced to terminate before this point it may not have searched all nodes in lower cost contours and hence may have missed the optimal solution.

Cheers,

Timkin