Yet one more A* question *SOLVED*
Author
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]
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?
Is this the case for your heuristic?
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.
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:
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.
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.
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).
This way your H will be shorter for your diagonal moves.
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).
This way your H will be shorter for your diagonal moves.
(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.
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.
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
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
Author
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.
Many thanks in advance.
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.
Many thanks in advance.
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.
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.
Quote:Original post by ursus
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.
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
Author
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):
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
Guys, I admit I'm not the brightest star, please help me a bit more here.
Many thanks
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
Guys, I admit I'm not the brightest star, please help me a bit more here.
Many thanks
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
