Jump to content
  • Advertisement
Sign in to follow this  
vbuser1338

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.

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

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


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

Share this post


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


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


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

Share this post


Link to post
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.cpp
int 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 list
int NumOnOpenList = 0; //The number on the list

void 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








Share this post


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


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


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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!