the A* pathfinding

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

Recommended Posts

I am new to pathfinding and I am trying to figure out how to do it. I made an rpg game in visual basic before I learn't c++ and now am remaking it in c++ and opengl and a lot better. But I am confused about the A* pathfinding. Can someone point me in the direction of the clearest tutorials. I get the basic concept well most of it. Thanks for any help. vbuser

Share on other sites
You could try the programming from the theory contained here or are you looking for a specific C++ class to look at?

Share on other sites
I read that tutorial already somewhere else. So I do these steps.

-take my present x and y and add it to a closed list
-I add all the squares around it max of 8 if not blocked
-I calculate the amount of cost to get there from present sqaure and the estimate to how far away it is
-I find which is the lowest score
-I add that to the closed list
-I then clear the open list and used the new squares around it again max of 8
-I then after have got to the target I used the objects in the closedlist to get my path

Is this correct or am I missing something?

Share on other sites
The closed list conmtains all points that have been explored not just the ones that lead to the goal so you can not just follow the closed list, also remember all items in the open list will stay in the open list until you check all nodes around them and put them in the closed list, I think each node needs to rember witch node was its parent and you follow these connections back to the start giving you your path.

Share on other sites
Ok thanks I'll See if I can get it working properely.
Thanks vbuser

Share on other sites
I'm having a little trouble with pathfinding. Could someone point me in the direction of some good source code that is clear to read?
Thanks vbuser

So this is what I understand so far.
-I add the start square to the openlist
-I add the surrounding squares to the openlist and make the start square its parent
-I remove the start square from the openlist and add to the closed list
-I calculate the f score for each of the items on the openlist
-I choose the one with the lowest f score and remove it from the open list and add it to the closed list
-I add any squares around the new parent to the openlist and record the parent
-I see if it is a lower f score if I use the current square to get there and if it is lower I change it and change the parent
-I then put the lowest one on the closed list and then repeat it till the parent square is the target square
-I then retrace the path to the start square

Is that all I need to do? Or am I missing some things?
Thanks vbuser

[Edited by - vbuser1338 on March 15, 2005 6:52:02 PM]

Share on other sites
Ok this is kindof frustrating but I am going to learn. I got my head arround the theory end of it and now I am going to code it. I have code but when it goes through the squares and goes through the lowest on the openlist until it reaches the target square it just never comes out and freezes. Here is my code if anyone wants to help I'll keep trying to figure it out.
#include "map.h"extern map map[15][15];	//use map declared in main1.cppint mapwidth = 15;struct openlist{	int xcoord;	//The x coord of the node on this list	int ycoord;	//The y coord of the node on this list	int parentx;	//The parent X of this node	int parenty;	//The parent Y of this node	int parentcost;	//The cost so far to get to that parent	int f;	//The f score	int g;	//The g score	int h;	//The h score};int whichList[15][15];	//Stores if an item is on closed or open list (1-open , 2-closed)openlist openList[15 * 15 + 2];	//an array to store every tile on the open listint NumOnOpenList = 0;	//The number on the listvoid FindPath(int sx,int sy,int tx,int ty){	int parentx = sx;	//The parent square is startx	int parenty = sy;	//The parent square is starty	int NumOnOpenList = 0;	//The number on the open list	int a,b;	//Variables for loops	//add the starting square to the openList	openList[1].xcoord = parentx;	//The xcoord	openList[1].ycoord = parenty;	//The ycoord	openList[1].g = 0;	//No cost to get here because we are here	openList[1].h = abs(parentx - tx) + abs(parenty - ty);	//H is equal to the 'Manhatten distance'	openList[1].f = openList[1].g + openList[1].h;	//Calcualte the F value	openList[1].parentcost = openList[1].g;	//The total travel cost for this parent	NumOnOpenList += 1;	//We added one to the open list so add one to the total	whichList[parentx][parenty] = 1;	//Its on the open list	//Add the adjacent sqaures to the openlist	for(b = parenty - 1;b <= parenty + 1; b++)	{		for(a = parentx - 1;a <= parentx + 1;a++)		{			if(a >= 0 && a < mapwidth && b >= 0 && b < mapwidth)			{				//add each item to the open list				if(map[a].surface != 1)	//If it is not blocked				{					if(whichList[a] == 0)	//If its not on open or closed list					{						NumOnOpenList += 1;	//Add one to the number on the list						//Now add it to the open list						openList[NumOnOpenList].parentx = parentx;	//Record the parent of this child						openList[NumOnOpenList].parenty = parenty;	//Record the parent of this child						openList[NumOnOpenList].xcoord = a;	//Record the x value of this child						openList[NumOnOpenList].ycoord = b;	//Record the y value of this child						whichList[a] = 1;	//Now we add it to the open list						int NumOnList = 0;	//When we search for the item this holds it						//We have to find out which number the coord is on the openList						for(int start = 1;start < NumOnOpenList;start++)						{							if(openList[start].xcoord == parentx && openList[start].ycoord == parenty)							{								openList[NumOnOpenList].parentcost = openList[start].parentcost;								NumOnList = start;	//Record it							}						}							//The travel is the cost from the parent to the child						if(abs(openList[NumOnOpenList].xcoord - openList[NumOnOpenList].parentx) == 1 && 						abs(openList[NumOnOpenList].ycoord - openList[NumOnOpenList].parenty) == 1)						{							//It is a diagonal move							openList[NumOnOpenList].g += 14;	//Add 14 to the cost						}						else						{							//It is a normal move							openList[NumOnOpenList].g +=10;						}						//Now calculate the h cost for that sqaure						openList[NumOnOpenList].h = (abs(openList[NumOnOpenList].xcoord - tx) + abs(openList[NumOnOpenList].ycoord - ty))* 10;						openList[NumOnOpenList].f = openList[NumOnOpenList].g + openList[NumOnOpenList].h;	//The total f value										}//If it was on a list or not				}//If its walkable			}//If it was on the map					}//For a	}//For b			//Remove the starting square from the open list	whichList[parentx][parenty] = 2;	//Its moved to closed list	//Now move the last item to the first	openList[1].f = openList[NumOnOpenList].f;	openList[1].g = openList[NumOnOpenList].g;	openList[1].h = openList[NumOnOpenList].h;	openList[1].parentcost = openList[NumOnOpenList].parentcost;	openList[1].parentx = openList[NumOnOpenList].parentx;	openList[1].parenty = openList[NumOnOpenList].parenty;	openList[1].xcoord = openList[NumOnOpenList].xcoord;	openList[1].ycoord = openList[NumOnOpenList].ycoord;	NumOnOpenList -= 1;	//We have removed one from openlist and moved	//to starting(the starting square)	//Now we must choose the lowest f values from the openList(max of 7 right now)	do	{		if(NumOnOpenList != 0)	//There is none on the open list which means no path		{			int lowestF;	//The lowest f score			int NumHolder;	//The openList with the lowest number						for(int open = 1; open < NumOnOpenList;open++)			{				if(open == 1)	//Its our first entry in the openlist				{					lowestF = openList[open].f;	//Record the f cost					NumHolder = open;	//Record that it was the first entry				}				if(openList[open].f < lowestF)	//Its lower than the current				{					lowestF = openList[open].f;					NumHolder = open;	//Record which one is the lowest				}			}			whichList[openList[NumHolder].xcoord][openList[NumHolder].ycoord] = 2;	//Change the item to the closed list					parentx = openList[open].xcoord;	//Record the parent			parenty = openList[open].ycoord;	//Record the parent			//Now We have found the lowest score			//We have to add the surrounding squares to open list			for(b = parenty - 1;b < parenty + 1;b++)			{				for(a = parentx - 1;a < parentx + 1;a++)				{					if(a >= 0 && a < mapwidth && b >= 0 && b < mapwidth)					{						if(whichList[a] == 1)	//If its on the open list						{							//Check to see if its better to use current square							int openListNumber = 0;	//Which number in the list this tile is																				//We have to find out which number the coord is on the openList							for(int start1 = 1;start1 < NumOnOpenList;start1++)							{								if(openList[start1].xcoord == a && openList[start1].ycoord == b)								{								openListNumber = start1;	//record which number on list this is								}							}														int tempG = openList[openListNumber].g;	//The g if we used the current square to get there														//The travel is the cost from the parent to the child							//Remember NumHolder holds our list number							if(abs(openList[NumHolder].xcoord - openList[openListNumber].parentx) == 1 && 							abs(openList[NumHolder].ycoord - openList[openListNumber].parenty) == 1)							{								//It is a diagonal move								tempG += 14;	//Add 14 to the cost							}							else							{								//It is a normal move								tempG +=10;							}							if(tempG < openList[openListNumber].g)	//Its easier using the current square							{								openList[openListNumber].parentx = openList[NumHolder].xcoord;								openList[openListNumber].parenty = openList[NumHolder].ycoord;								//Change the scores								openList[openListNumber].g = tempG;	//Change the g								//H will be the same								//Recalculate f cost								openList[openListNumber].f = openList[openListNumber].g + openList[openListNumber].h;							}						}	//If it was already on list						//if its not better nothing happens						if(whichList[a] == 0)	//Its not on a list						{							if(map[a].surface != 1)	//Its not blocked							{								//Now add it to the openList								NumOnOpenList += 1;	//Add one to the number on the list								//Now add it to the open list								openList[NumOnOpenList].parentx = parentx;	//Record the parent of this child								openList[NumOnOpenList].parenty = parenty;	//Record the parent of this child								openList[NumOnOpenList].xcoord = a;	//Record the x value of this child								openList[NumOnOpenList].ycoord = b;	//Record the y value of this child								openList[NumOnOpenList].g = openList[NumHolder].parentcost;	//Keep the cost								openList[NumOnOpenList].h = (abs(openList[NumOnOpenList].xcoord - tx) + abs(openList[NumOnOpenList].ycoord - ty)) * 10;	//Find the h distance								if(abs(parentx - openList[NumOnOpenList].xcoord) == 1 && 								abs(parenty - openList[NumOnOpenList].ycoord) == 1)								{									//Its diagonal so add 14								openList[NumOnOpenList].g += 14;								}								else	//Its not diagonal								{									openList[NumOnOpenList].g += 10;								}								openList[NumOnOpenList].f = openList[NumOnOpenList].g + openList[NumOnOpenList].h;	//Find the F score								whichList[a] = 1;	//Now we add it to the open list							}						}					}//If i was on the map									}//Loop a			}//loop b		}//If openlist was not empty		if(NumOnOpenList == 0)		{			MessageBox(NULL,"NO PATH","SORRY",MB_OK);		}	}while(parentx != tx || parenty != ty);	//While its not on the target		MessageBox(NULL,"Path found","YES",MB_OK);}

vbuser

Share on other sites
EDIT: Mixed higher/lower, its corrected now. Thanks Salias!

If I might add a detail:

If your estimate (called heuristic in most texts) is always lower or equal than the real cost, the path you will find is guaranteed to be the shortest, and the algorithm is called 'A*'.

If your heuristic can be higher than the real cost, then the algorithm is called 'A', and you might not always find the shortest path but it will often find a solution faster, even find an optimal solution faster.

So you see, your heuristic is very important.

Good luck!

[Edited by - Steadtler on March 17, 2005 6:33:29 PM]

Share on other sites
You might also consider not doing A* first. Try writing Best First or Djkstra. After you got that working you should be able to reuse much of the code and add the extra A* steps to it.

Share on other sites
Quote:
 Original post by SteadtlerIf I might add a detail:If your estimate (called heuristic in most texts) is always higher than the real cost, the path you will find is guaranteed to be the shortest, and the algorithm is called 'A*'.

Actually you want a heuristic which is never overestimates the cost of the path from a given node.

The order in which a node is evaluated is based on the path distance to the node plus the estimate of the distance from the node to the goal. Assume that the heuristic (h) is positive and less then or equal to the distance from the node to the goal. The value for the goal node itself must therefore be the distance along the path taken to reach the goal, plus zero. Since the total cost of a node is never overestimated, any node along the true shortest path will have a value less than the goal node and will be examined before the goal is reached. This means that A* will always find the shortest path.

In fact if you supply a h of 0 for every node (admissable since it underestimates the path length) you get Djkstra's, which is also guarenteed to find the shortest path.

There was an interesting article on the use of inadmissable heuristics in this month's issue of game developer. For some maps you can get paths that are "good enough" by examining fewer nodes using an overestimating heuristic. The system would then go back and check for local errors in the path that would "look bad" to the player. However for some maps this resulted in actually slower results as it could cause nodes to be moved from the closed list back to the open list as shorter paths to the nodes were found, which causes them to be examined multiple times.

• 10
• 16
• 9
• 13
• 41