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 = &currentnode

				openlist.push( n );

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

					n.G = newg;
					n.parent = &currentnode

					openlist.push( n );

					continue;
				}
				

				n.G = newg;
				n.parent = &currentnode

				openlist.push( n );
			}

		}

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

Thanks for any help!

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.

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

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.

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! ;)

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.

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.

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

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.