Yet one more A* question SOLVED

ursus · 2006-11-11T06:49:37

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]

Artificial Intelligence Programming

Started by ursus October 22, 2006 04:16 AM

10 comments, last by ursus 18 years ago

Timkin

864

November 06, 2006 05:10 PM

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

ursus

Author

206

November 11, 2006 06:49 AM

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.

Yet one more A* question SOLVED

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Yet one more A* question *SOLVED*

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines

Yet one more A* question SOLVED