# Yet one more A* question *SOLVED*

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

## Recommended Posts

Hi, I've been working on the A* pathfinding algorithm for some time now and there is one thing I fail to understand. I've managed to implement the algorithm partially basing on the 'A* Pathfinding for Beginners' tutorial successfully calculating F, G and H scores. The problem appears when approaching to obstacles; they are always walked around using the latest lowest F score. Obviously the path often gets illogical this way. Let me show you on this example (the orange line is how 'my' pathfinding works): http://img149.imageshack.us/my.php?image=pathfindingfm2.png After analyzing the example program I've fond that somehow it finds more reasonable path. It looks to me like after each step the whole path made so far and examined if there is a better way to get to the current point. I'm not sure how to do it, however. I find very little information about it in the article. Perhaps I didn't give it enough though but I've been breaking my head over this for some time now so any hints and suggestions will be greatly appreciated. Thanks in advance [Edited by - ursus on November 11, 2006 6:45:37 AM]

##### Share on other sites
This problem sometimes occurs when the heuristic is too small. The heuristic must ensure that the point with the lowest score may not be reached with a score even lower. A stronger condition is that, when exploring adjacent nodes, the score obtained for an explored node must be larger than the score for the current node.

Is this the case for your heuristic?

##### Share on other sites
As you can see the path found by your algorithm clearly isnt the shortest since its going 'over' the obstacle instead of under it.
When i wrote my first version (also from this tutorial) i had a similar problem.

Quote:
 Original post by ursus...After analyzing the example program I've fond that somehow it finds more reasonable path. It looks to me like after each step the whole path made so far and examined if there is a better way to get to the current point. I'm not sure how to do it, however. I find very little information about it in the article....

I think you are right here, this was what i forgot the first time too, however this is explained in the tutorial. Look at the step by step summary of the algorithm (under the explanation); i think you forgot this:
Quote:
 If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

so basicly you just act like if the point wasn't on the open list, just calculate the G cost. Compare this to the G of this point on the open list, if the new G is better (lower): change parent, change G, recalculate F (adding H + new G).

hope this helps you out.

##### Share on other sites
Does your game allow moves in the diagonal direction?

If so, then your prblem is that you have set diagonal move equal to 10, but a diagonal move is a longer move. You need to set it to 14 (diagonal is about 1.414).

##### Share on other sites
(Continuation of my last post)

Whoops, just took another look and it looks like you are using 14 for your G's, but 10 for your H's. That is definitely your problem. Use 14 for diagonal moves in the H value as well.

##### Share on other sites
The problem is one caused by your choice of heuristic. You're using a function of the Manhattan distance for the heuristic (equivalent to the 1-norm distance function) which, for those that aren't familar, is the sum over coordinates 'i' of the distance in each coordinate: Σi|XGi-Xi|, where XGi is the i'th coordinate of the goal and Xi is the i'th coordinate of the node under consideration and |.| is the absolute value function.

However, you're permitting diagonal moves in your action operator set (transition function). What this means is that the heuristic cost of a diagonal move is 20, whereas the path cost is 14. You're heuristic is inadmissible, in that it overestimates the actual cost. For A* to work correctly, your heuristic must never overestimate the actual cost of a transition between any two nodes.

There are two simple fixes for this:

(1) Use the Euclidean distance (2-norm) as your heuristic: SQRT(Σi(XGi-Xi)2)
OR
(2) Scale your current heuristic by a factor no greater than 14/20 (diagonal path cost on current diagonal heuristic cost).

Cheers,

Timkin

##### Share on other sites
Guys,

Thank you all for your answers and sorry for staying quiet for so long - my PC broke and it took me a while to get a new one.

Perhaps my description in my first post wasn't extremely fortunate. Let me show you one more example:

http://img134.imageshack.us/my.php?image=pathfinding2me3.jpg

In this case the algorithm follows the steps till it 'hits' the wall made of 1 square. In my implementation it'd go around the obstacle. It'd seem to me far more logical to use the other path right from the beginning (less moves and score to get there). This happens when using the app from the tutorial (as per the print screen).

I wonder how this is achieved. I can see the blue squares (Closed List) initially goes toward the obstacle but eventually a new path is determined.

##### Share on other sites
You are not calculating your diagonal moves correctly. They should be 14's, not 20s. That last square before the target has a H of 20, but it should be 14.

In fact, that bottom path from the start should have H values of:

74, 64, 54, 44, 34, 24, 14

Not

80, 70, 60, 50 , 40, 30, 20

Diagonal moves are 14, not 20.

With lower H's, you will get lower F's, which will get you the right path from the get go.

##### Share on other sites
Quote:
 Original post by ursusI wonder how this is achieved. I can see the blue squares (Closed List) initially goes toward the obstacle but eventually a new path is determined.

That blue path has incorrect costs associated with it. The 'g' cost for each node is the minimum of the cost of all possible ordered traversible sub-paths from the start to that node. That is, the lowest cost path from the start to that node that can be traversed. The blue path costs indicate that they are being computed as having passed through the obstacle. You can see this because the path cost is actually decreasing with distance away from the start (it drops from 90 below the obstacle to 84 to the left of it. It should be at least 100.) Since your cost function is not monotonically increasing, you cannot expect to find the optimal path.

I would suspect that it is your implementation that is incorrect in this manner though, rather than the article. Go back and check it again. 8)

Cheers,

Timkin

##### Share on other sites
All,

Once again I thank you very much for your help.

The screen shots I've presented in my previous posts were taken from the properly working (I hope) tutorial example. I assume it calculates everything properly.

I think Scorpie was most accurate in this case. My part of checking squares in the open list was messed up.

After some corrections I managed to move one step forward but my implementation still calls for refinement.

Let me present you my code (I try to keep it simple for now):
void FindPath(){	int cpX, cpY;		// current (grid) X and Y position	int goX, goY;		// next grid X and Y position to be taken	int lowest;		// temproary lowest F cost	int addG;		// the G score to be added, can be: 10 or 14		cpX=startX;	cpY=startY;				// adding grids to the Open List:	while (cpX!=destinationX || cpY!=destinationY)	{				lowest=10000;	// for no let's assume the lowest F will never be bigger than 10000		int gX, gY;	//grix X and Y (-1, 0, 1)				for (gY=-1;gY<=1;gY++)		{			for (gX=-1;gX<=1;gX++)			{								if (TAKEN[cpX+gX][cpY+gY]==FALSE	&& // checking if the curent grid is not occupied by another sprite					CL[cpX+gX][cpY+gY]==FALSE)	// checking if the curent grid is not in the Closed List				{					//determining the G score for diagonal or orthogonal move					if (gX==-1)					{						if (gY==0)							addG=10;						else							addG=14;					}										if (gX==0)					{						if (gY==0)							addG=14;						else							addG=10;					}										if (gX==1)					{						if (gY==0)							addG=10;						else							addG=14;					}										//if that grid is already on the open list					if (OL[cpX+gX][cpY+gY]==TRUE)					{						//check if G score is lower if we go through the current grid						if (G[cpX][cpY]+addG<G[cpX+gX][cpY+gY])						{							//changing parent							parentX[cpX+gX][cpY+gY]=cpX;							parentY[cpX+gX][cpY+gY]=cpY;														//recalculating G, H, F							G [cpX+gX][cpY+gY]=G[cpX][cpY]+addG;// G cost							H [cpX+gX][cpY+gY]=10*(abs(destinationX-(cpX+gX))+abs(destinationY-(cpY+gY)));// H cost							F [cpX+gX][cpY+gY]=G[cpX+gX][cpY+gY]+H[cpX+gX][cpY+gY];// F cost, F=G+H						}					}					else					{								OL[cpX+gX][cpY+gY]=TRUE;// added to the Open List						G [cpX+gX][cpY+gY]=G[cpX][cpY]+addG;// G cost						H [cpX+gX][cpY+gY]=10*(abs(destinationX-(cpX+gX))+abs(destinationY-(cpY+gY)));// H cost						F [cpX+gX][cpY+gY]=G[cpX+gX][cpY+gY]+H[cpX+gX][cpY+gY];// F cost, F=G+H											//setting up parents						parentX[cpX+gX][cpY+gY]=cpX;						parentY[cpX+gX][cpY+gY]=cpY;					}										//below I determine the next grid we should go:										// checking if a grid with the lower F cost was found					if (F[cpX+gX][cpY+gY]<lowest)					{						lowest=F[cpX+gX][cpY+gY];// yes, it was found!						goX=gX;// taking even better way						goY=gY;					}									}// end of ifs							}		}// end of fors				//adding the curent grid to the Closed List		CL[cpX][cpY]=TRUE;			//movig to the next grid depending on goX and goY		cpX+=goX;		cpY+=goY;		}//end of while (cpX!=destinationX || cpY!=destinationY)}

The result of the above is this:

http://img123.imageshack.us/img123/6299/pathfinding2aj9.png

The ideal path should be (as per the tutorial):

http://img130.imageshack.us/img130/9662/pathfinding3si7.png

Many thanks

1. 1
Rutin
26
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 9
• 9
• 9
• 46
• 41
• ### Forum Statistics

• Total Topics
631750
• Total Posts
3002062
×