Sign in to follow this  

Yet one more A* question *SOLVED*

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

If you intended to correct an error in the post then please contact us.

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


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


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


Link to post
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).

This way your H will be shorter for your diagonal moves.

Share this post


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


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


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

Many thanks in advance.

Share this post


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


Link to post
Share on other sites
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

Share this post


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


Guys, I admit I'm not the brightest star, please help me a bit more here.

Many thanks

Share this post


Link to post
Share on other sites
I've only done a quick scan of the code, but this is the first thing that stands out...

if (gX==0)
{
if (gY==0)
addG=14;
...

You're permitting 9 successor nodes from the current node (gX=(-1,0,1),gY=(-1,0,1)), with the (gX=0,gY=0) equating to the current node. Thus, you're permitting a node to be a child of itself in your search tree. That's fine, except that you're adding a movement cost of 14 to this 'null move'. If you're going to permit not moving as a valid move, then it should have a 'g' cost of 0. Personally, I'd simply omit this move form the action set.

There may be more problems, but I haven't gotten that far into the code yet.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
I had some kind of revelation LOL.

I’ve pinpointed that spot covering a small detail of the whole A* idea. Every time I was choosing new square from the open list with its lowest F score I was choosing from only neighbor grids whereas all(!) squares should be considered.

Below the code that works, it needs polishing but it works:

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=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 and removing it from the Open List
CL[cpX][cpY]=TRUE;
OL[cpX][cpY]=FALSE;

//below we determine the next grid we should check:
//loopp that will go through all squares and will pick the lowest F grid from the Open List

int x,y;

for (x=0;x<23;x++)
{
for (y=0;y<15;y++)
{
if (OL[x][y]==TRUE)
{
// checking if a grid with the lower F cost was found
if (F[x][y]<lowest)
{
goX=x;
goY=y;
lowest=F[x][y];
}
}
}
}

//movig to the next grid depending on goX and goY
cpX=goX;
cpY=goY;

}// end of while (cpX!=destinationX || cpY!=destinationY)
}



Thank you all for your patience.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

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