the A* pathfinding
Author
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
You could try the programming from the theory contained here or are you looking for a specific C++ class to look at?
Author
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?
-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?
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.
Author
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
[edit]
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]
Thanks vbuser
[edit]
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]
Author
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.
Thanks for any help you want to give
vbuser
#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);}Thanks for any help you want to give
vbuser
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]
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]
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.
Quote:Original post by Steadtler
If 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
