So I went ahead and programmed in A* pathfinding for my RPG, but I'm having difficulties.
I'll try to do my best to explain what I've done: please don't laugh at my lack of understanding of A* (Or the fact that I refer to myself as 'we' in my comments [Its a bad habit] )...
First, I declared a boundary in which the A* acts in, in this case, a 21x17 rectanagle around the destination object. Than, when the monsters comes within range of the player (Player being the destination object), it maps the monsters onto the 21x17 grid (Which of the course, the player is in the very center.) and followings A* to get there.
Some important details.
-> All terrain has the same cost.
-> Diagonal movement is not possible.
Why this is very important is, I can get away with not worrying about this occuring..
Quote:GameDev.net A* Tutorial
"If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change."
least, I hope so, and Timkin says so =)
Quote:
Another few things that may help is...
gaoObjects - A linear array of gtObjects (These are the generic creature structure in my game.
gaoMap - Also a linear array, however, its a linear 2D array (x+y*width). Its a pointer grid, so that instead of searching though every object, I just lookup the pointer grid to see if it points to any objects that may be standing there (Because my map can have some 500,000 creatures, looping through each object checking if it was near a player would be very CPU intensive). Its width 1500, and you'll see it in my code. The element loCreature is a pointer to the creature on that tile.
The structure of my A* nodes are as follows (I'm using just a plain array instead of linked list).
struct gtAStarNode
{
/* This is used by the Open/Closed lists. */
int luiHofX; /* Manhatten. */
int luiGofX; /* Distance Travelled. */
unsigned char lucDirection;
/* lucSpecial == 0 -> 'Not Used'
lucSpecial == 1 -> 'Used' */
unsigned char lucSpecial;
/* If this node is closed, than don't apply pathfinding
on it since its already been done! */
unsigned char lucClosed;
/* This is used by the open list. */
unsigned short lusGridX;
unsigned short lusGridY;
};
And than of course in my sStartServer()
gaoOpenList = calloc(21*17, sizeof(struct gtAStarNode));
gaoClosedList = calloc(21*17, sizeof(struct gtAStarNode));
In building the nodes on the closed and open lists, I wrote this function (Instead of popping and pushing from the open list, I just had a flag that indicates wheter the specified node has been used in a path (lucClosed), and of course, lucSpeical indicates whether the node exists or not (This should really be called lucUsed, lol).
Note that the point (10,6) is the very middle of this rectangle.
Here are my flags too, just incase..
/* Direction Facing */
#define flag_North 2
#define flag_East 3
#define flag_South 0
#define flag_West 1
/* A* Pathfinding. */
#define flag_AStarNoGo 0
#define flag_AStarNorth 1
#define flag_AStarSouth 2
#define flag_AStarWest 3
#define flag_AStarEast 4
/* Helper: This helper procedure builds a node in both the open and closed lists. */
void sAddNode(unsigned short lusGridX, unsigned short lusGridY, unsigned char lucDirection, int liSourceCreature, unsigned char lucOverride)
{
int liX;
/* The first step is to make sure the path is valid.*/
if((fTileConditions(gaoObjects[liSourceCreature].lusGridX + (lusGridX-10),gaoObjects[liSourceCreature].lusGridY + (lusGridY-6)) == flag_Walkable &&
gaoMap[gaoObjects[liSourceCreature].lusGridX+ (lusGridX-10) + (gaoObjects[liSourceCreature].lusGridY + (lusGridY-6))*1500].loCreature == NULL) ||
lucOverride == 1)
{
/* First step is to build the node on the closed list. */
gaoClosedList[lusGridX + lusGridY*17].lucClosed = 1;
gaoClosedList[lusGridX + lusGridY*17].lucDirection = lucDirection;
switch(lucDirection)
{
case flag_AStarNoGo:
gaoClosedList[lusGridX + lusGridY*17].luiGofX = 0;
break;
case flag_AStarWest:
gaoClosedList[lusGridX + lusGridY*17].luiGofX = 1 +
gaoClosedList[lusGridX+1 + lusGridY*17].luiGofX;
break;
case flag_AStarEast:
gaoClosedList[lusGridX + lusGridY*17].luiGofX = 1 +
gaoClosedList[lusGridX-1 + lusGridY*17].luiGofX;
break;
case flag_AStarNorth:
gaoClosedList[lusGridX + lusGridY*17].luiGofX = 1 +
gaoClosedList[lusGridX + (lusGridY+1)*17].luiGofX;
break;
case flag_AStarSouth:
gaoClosedList[lusGridX + lusGridY*17].luiGofX = 1 +
gaoClosedList[lusGridX+1 + (lusGridY-1)*17].luiGofX;
break;
}
gaoClosedList[lusGridX + lusGridY*17].luiHofX =
abs(lusGridX - 10) +
abs(lusGridY - 6);
gaoClosedList[lusGridX + lusGridY*17].lusGridX = lusGridX;
gaoClosedList[lusGridX + lusGridY*17].lusGridY = lusGridY;
gaoClosedList[lusGridX + lusGridY*17].lucSpecial = 1;
/* Ok, now copy this over to the open list. */
for(liX=0;liX<21*17;liX++)
if(gaoOpenList[liX].lucSpecial == 0)
{
gaoOpenList[liX] = gaoClosedList[lusGridX + lusGridY*17];
break;
}
/* All done. =) */
}
}
And lastly, the actual A* stuff itself. This function puts the objects on the A* 21x17 grid, and than perceeds with the algorithm to find the path.
/* This procedure generates the path for a monster trying to reach a grid X,Y. If it cannot
generate the path, it returns zero, else it returns 1. */
int fGeneratePath(int liSourceCreature, int liDestinationCreature)
{
int liX, liFValue,liFLocation, liRecursionCount=0, liAttempt = 0;
unsigned short lusGridX, lusGridY;
/* First step is to clear the pathfinding buffers. */
memset(gaoOpenList, 0, 21*17*sizeof(struct gtAStarNode));
memset(gaoClosedList, 0, 21*17*sizeof(struct gtAStarNode));
/* Step 1: Find the spawning point relative to the destination creature:
the destination is always the middle of the rectangle. */
sAddNode((unsigned short)(10 - (gaoObjects[liSourceCreature].lusGridX - gaoObjects[liDestinationCreature].lusGridX)) ,
(unsigned short)(6 - (gaoObjects[liSourceCreature].lusGridY - gaoObjects[liDestinationCreature].lusGridY)),
flag_AStarNoGo, liSourceCreature, 1);
/* Until we either run out of spaces, or we finally find the player, continue calculating. ;D */
while(liAttempt != 10000)
{
//liAttempt++;
/* Find the lowest F value. */
liFValue = 99999;
for(liX=0;liX<21*17;liX++)
if(gaoOpenList[liX].lucSpecial == 1)
{
if(gaoOpenList[liX].luiGofX + gaoOpenList[liX].luiHofX <= liFValue)
{
liFValue = gaoOpenList[liX].luiGofX + gaoOpenList[liX].luiHofX;
liFLocation = liX;
}
}
else if(gaoOpenList[liX].lucSpecial == 0)
{
break;
}
/* Now, lets extract the components of the location, and from it, compute the costs to
go in each direction. */
lusGridX = gaoOpenList[liFLocation].lusGridX;
lusGridY = gaoOpenList[liFLocation].lusGridY;
gaoOpenList[liFLocation].lucSpecial = 2;
/* Build four more adjacent paths (If there is room) */
if(lusGridX-1 >= 0 && gaoClosedList[lusGridX-1 + lusGridY*17].lucClosed == 0)
{
if(lusGridX == 10 && lusGridY == 6)
{sAddNode((unsigned short)(lusGridX-1),lusGridY,flag_AStarWest,liSourceCreature,1);}
else
{sAddNode((unsigned short)(lusGridX-1),lusGridY,flag_AStarWest,liSourceCreature,0);}
}
if(lusGridX+1 < 21 && gaoClosedList[lusGridX+1 + lusGridY*17].lucClosed == 0)
{
if(lusGridX == 10 && lusGridY == 6)
{sAddNode((unsigned short)(lusGridX+1),lusGridY,flag_AStarEast,liSourceCreature,1);}
else
{sAddNode((unsigned short)(lusGridX+1),lusGridY,flag_AStarEast,liSourceCreature,0);}
}
if(lusGridY-1 >= 0 && gaoClosedList[lusGridX + (lusGridY-1)*17].lucClosed == 0)
{
if(lusGridX == 10 && lusGridY == 6)
{sAddNode(lusGridX,(unsigned short)(lusGridY-1),flag_AStarNorth,liSourceCreature,1);}
else
{sAddNode(lusGridX,(unsigned short)(lusGridY-1),flag_AStarNorth,liSourceCreature,0);}
}
if(lusGridY+1 < 17 && gaoClosedList[lusGridX + (lusGridY+1)*17].lucClosed == 0)
{
if(lusGridX == 10 && lusGridY == 6)
{sAddNode(lusGridX,(unsigned short)(lusGridY+1),flag_AStarSouth,liSourceCreature,1);}
else
{sAddNode(lusGridX,(unsigned short)(lusGridY+1),flag_AStarSouth,liSourceCreature,0);}
}
/* If the destination node has been written to, than we KNOW the pathfinding is completed. */
if(gaoClosedList[10+6*17].lucClosed == 1)
{
/* Ok, because the list is backwards (Hehehe), we gotta know a few things. First of all,
if we know the number of elements that composes the list, we can place the path into
the creature's path list without the need of a buffer (This is a good idea), so lets
do that. */
sHelperReverseMovePath(10,6,0,fHelperFindElements(10,6),liSourceCreature);
return 1;
}
/* Instead of letting this thing search continously, lets check if we're all out of spots. */
else if(gaoOpenList[17*21-1].lucClosed == 1)
{
/* Well, this is a sad day for this monster. It cannot find his player. =( */
printf("Unable to find a path. \n");
return 0;
}
}
/* Step 4, work backwords and get the path to the user. */
return 0;
}
And now the problem, simply put, its not finding the destination. It will proceed in an infinite loop of sAddNode() being rejected over and over again. [depressed]
[Edited by - Thevenin on August 4, 2005 1:53:03 AM]
