Sign in to follow this  
drunkhaveawreckrun

A* trouble

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Vorpy
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.


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

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Timkin
Quote:
Original post by Vorpy
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.


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 this post


Link to post
Share on other sites
Quote:
Original post by Vorpy
Actually, 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

Share this post


Link to post
Share on other sites
Every node appears to have the same parent because of a little bit of memory mismanagement. Your variables are on the stack, so when you get their address you're really getting the address of a temporary stack variable. Once the variable is out of scope the address is invalid. It may be best to allocate all the nodes beforehand and then avoid using temporary copies when possible.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this