• Advertisement
Sign in to follow this  

the A* pathfinding

This topic is 4720 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
I got It working finally. A few errors when I used the wrong variables and loop errors. I coded it to output text while it found the path so now I am implementing it into my rpg game. I will post my code when I am finished in about an hour or 2.
Thanks for all the help
vbuser

Share this post


Link to post
Share on other sites
Ok I finally got all the bugs out of it. Took long enough. I still could probably shorten the code up a bit more and I will work on but it works.
Here it is. If you have any comments I would like to hear.

#include "map.h"

extern map map[15][15]; //use map declared in main1.cpp
const int MaxTilesWide = 13;
const int MaxTilesHigh = 12;

struct openlist
{
int xcoord;
int ycoord;
int parentx;
int parenty;
int f;
int g;
int h;
};
struct closedList
{
int xcoord;
int ycoord;
int parentx;
int parenty;
};
struct moveList
{
int xcoord;
int ycoord;
};
moveList endmoves[50];
moveList moves[50];

bool FindPath(int sx,int sy,int tx,int ty);
void TracePath(int endx,int endy, int startx,int starty);

int whichList[15][15]; //Stores if item is on open or closed list
openlist openList[227];
closedList closedList[227];

int NumOnOpenList = 0;
int NumOnClosedList = 0;

int xchange; //The change in x
int ychange; //The change in y
int PathLength; //The length of the path

bool FindPath(int sx,int sy,int tx,int ty)
{
bool path = false; //no path yet

int parentx = sx; //The starting parentx
int parenty = sy; //The starting parenty
int a,b; //Loop variables
NumOnClosedList = 0; //Reset variable
NumOnOpenList =0;

//Check to see if its on the map
if(tx >= MaxTilesWide || ty >= MaxTilesHigh || tx < 0 || ty < 0)
{
MessageBox(NULL,"No Path","No path",MB_OK);
path = false;
return false;
}

for(int t = 1; t < 228;t++)
{
//Reset the list
openList[t].xcoord = 0;
openList[t].ycoord = 0;
openList[t].g = 0;
openList[t].h = 0;
openList[t].f = 0;
openList[t].parentx = 0;
openList[t].parenty = 0;

closedList[t].xcoord = 0;
closedList[t].ycoord = 0;
closedList[t].parentx = 0;
closedList[t].parenty = 0;
}

for(b = 0;b < MaxTilesHigh;b++)
{
for(a = 0; a < MaxTilesWide;a++)
{
whichList[a] = 0; //Reset it
}
}



//add the starting square to open list
openList[1].xcoord = parentx;
openList[1].ycoord = parenty;
openList[1].g = 0;
int tempxchange = parentx - tx;
int tempychange = parenty - ty;
if(tempxchange < 0)
{
tempxchange = tempxchange * -1;
}
if(tempychange < 0)
{
tempychange = tempychange * -1;
}

openList[1].h = (tempxchange + tempychange) * 10;
openList[1].f = openList[1].g + openList[1].h;
//openList[1].parentcost = openList[1].g;
//increase number on openlist
NumOnOpenList += 1;
whichList[parentx][parenty] = 1; //Its on open now

NumOnOpenList = 1; //There is one less


do
{
int openListNumber = 0; //The number of the item we are checking
if(NumOnOpenList != 0) //While theres items in openList
{
//Find the lowest f value on the list
int lowestF; //the lowest f
int NumHolder; //The number of the item in the open List
for(int open = 1; open < NumOnOpenList + 1;open++)
{
if(open == 1) //The first enty
{
lowestF = openList[open].f;
NumHolder = open;
}
if(openList[open].f < lowestF)
{
lowestF = openList[open].f;
NumHolder = open;
}
}

whichList[openList[NumHolder].xcoord][openList[NumHolder].ycoord] = 1;
parentx = openList[NumHolder].xcoord;
parenty = openList[NumHolder].ycoord;

//We have the lowest score
//Add this squares parent
for(b = parenty - 1; b <= parenty + 1;b++)
{
for(a = parentx - 1;a <= parentx + 1;a++)
{
if(a >= 0 && a < 15 && b >= 0 && b < 15) //Its on the map
{
if(whichList[a] == 1) //Its on the open list already
{

//Check to see if the score would be lower using the current square
//Find the number of that square
for(int start1 = 1; start1 < NumOnOpenList + 1; start1++)
{
if(openList[start1].xcoord == a && openList[start1].ycoord == b)
{
//We found the item
openListNumber = start1;
}
}

int tempG = openList[NumHolder].g; //The temp g is the parents g

//The travel is the parents plus the amount to child
xchange = parentx - openList[openListNumber].xcoord;
//Change to positive if needed
if(xchange < 0)
{
xchange *= -1;
}
ychange = parenty - openList[openListNumber].ycoord;
//Change to positive if needed
if(ychange < 0)
{
ychange *= -1;
}

if(xchange == 1 && ychange == 1)
{
//The move is diagonal
tempG += 14; //Add 14
}
else
{
//Its a normal move
tempG += 10;
}

//See if it was easier
if(tempG < openList[openListNumber].g) //Its easier
{
openList[openListNumber].parentx = parentx; //Change the parent
openList[openListNumber].parenty = parenty; //Change the parent
openList[openListNumber].g = tempG; //Change the g cost
//Recalculate cost
openList[openListNumber].f = openList[openListNumber].g + openList[openListNumber].h;
}
}//If it was on the list already
//If it was not better nothing gets changed

//Now if it wasn't on list then add it
if(whichList[a] == 0) //If it isn't on the list
{
if(map[a].surface != 1) //Not blocked
{
//Now add it to openList
NumOnOpenList += 1;

openList[NumOnOpenList].parentx = parentx;
openList[NumOnOpenList].parenty = parenty;
openList[NumOnOpenList].xcoord = a;
openList[NumOnOpenList].ycoord = b;
openList[NumOnOpenList].g = openList[NumHolder].g; //The parents cost

xchange = parentx - openList[NumOnOpenList].xcoord;
if(xchange < 0) //Its negative so make positive
{
xchange *= 1;
}
ychange = parenty - openList[NumOnOpenList].ycoord;
if(ychange < 0)
{
ychange *= -1; //Change to positive
}
openList[NumOnOpenList].h = (xchange + ychange) * 10;

//Now find the distances from parent to child
xchange = parentx - openList[NumOnOpenList].xcoord;
if(xchange < 0) //Its negative so make positive
{
xchange *= 1;
}
ychange = parenty - openList[NumOnOpenList].ycoord;
if(ychange < 0)
{
ychange *= -1; //Change to positive
}

if(xchange == 1 && ychange == 1)
{
//Its diagonal
openList[NumOnOpenList].g += 14;
}
else
{
//Its a normal move
openList[NumOnOpenList].g += 10;
}
//Now change the f score
openList[NumOnOpenList].f = openList[NumOnOpenList].g + openList[NumOnOpenList].h;
//change the child to the closed list
whichList[a] = 1;
}//Was not blocked
}//If it wasn't on a list
}//If it was on the map
}//For a
}//For b

//Now that we checked that square( parent) move it to closed list
///Add starting square to closed list
//Transfer to closed list first
closedList[NumOnClosedList].xcoord = openList[NumHolder].xcoord;
closedList[NumOnClosedList].ycoord = openList[NumHolder].ycoord;
closedList[NumOnClosedList].parentx = openList[NumHolder].parentx;
closedList[NumOnClosedList].parenty = openList[NumHolder].parenty;

NumOnClosedList += 1; //There is another item on closed list
whichList[openList[openListNumber].xcoord][openList[openListNumber].ycoord];

//Now use the last item in the list and move it to the cleared place
//If its not last on list we have to change it
if(NumHolder != NumOnOpenList)
{
openList[NumHolder].xcoord = openList[NumOnOpenList].xcoord;
openList[NumHolder].ycoord = openList[NumOnOpenList].ycoord;
openList[NumHolder].parentx = openList[NumOnOpenList].parentx;
openList[NumHolder].parenty = openList[NumOnOpenList].parenty;
openList[NumHolder].f = openList[NumOnOpenList].f;
openList[NumHolder].g = openList[NumOnOpenList].g;
openList[NumHolder].h = openList[NumOnOpenList].h;
}

//Decrease the number on the open list
NumOnOpenList -= 1;


}//If there are items on openList
else
{
MessageBox(NULL,"Sorry cannot find path.","sorry",MB_OK);
path = false;
return false;
}
path = true; //a path was found
}while(parentx != tx || parenty != ty);

if(path)
{
//MessageBox(NULL,"PathFound","YES",MB_OK);
TracePath(parentx,parenty,sx,sy);
}
return true;
}

void TracePath(int endx,int endy, int startx,int starty)
{
extern int currentMove; //Reset the moves so when we travel it works
currentMove = 0;

//Reset the lists
for(int q = 0; q < 50;q++)
{
moves[q].xcoord = NULL;
moves[q].ycoord = NULL;
endmoves[q].ycoord = NULL;
endmoves[q].xcoord = NULL;
}

int ParentNum = 0; //The number on the list
int ChildNum = 0; //The number of the child

for(int Num = 1;Num < NumOnClosedList + 1;Num++)
{
if(closedList[Num].xcoord == endx && closedList[Num].ycoord == endy)
{
//Find the child
ChildNum = Num;
}
}
moves[0].xcoord = endx;
moves[0].ycoord = endy;
PathLength = 0;

do
{

//If it is right beside target then we don't have to search anymore
if(abs(startx - endx) == 0 || abs(startx - endx) == 1)
{
if(abs(starty - endy) == 0 || abs(starty - endy) == 1)
{
break;
}
}

//Find the parent of the child
for(int Num1 = 1;Num1 < NumOnClosedList;Num1++)
{
if(closedList[ChildNum].parentx == closedList[Num1].xcoord &&
closedList[ChildNum].parenty == closedList[Num1].ycoord) //This is parent
{
ParentNum = Num1;
PathLength++;
moves[PathLength].xcoord = closedList[ChildNum].parentx;
moves[PathLength].ycoord = closedList[ChildNum].parenty;
}
}
ChildNum = ParentNum;
} while(closedList[ParentNum].parentx != startx || closedList[ParentNum].parenty != starty);

int curMove = -1;


for(int t = PathLength + 1; t >= -1 ; t--)
{
curMove++;
endmoves[curMove].xcoord = moves[t].xcoord;
endmoves[curMove].ycoord = moves[t].ycoord;

}

// MessageBox(NULL,"PathTraced","YES",MB_OK);

}



Thanks for the help
vbuser




Share this post


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

  • Advertisement