Yet one more A* question *SOLVED*

Started by
10 comments, last by ursus 17 years, 5 months ago
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
Advertisement
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.

This topic is closed to new replies.

Advertisement