Sign in to follow this  

My A* is not working, help! (Solved)

This topic is 4514 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

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:
Image Hosted by ImageShack.us
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]

Share this post


Link to post
Share on other sites
<yawn>

Ok, I'm back to working on this again (I took a detour to finish another part of the project (NPCs), cause I was lacking motivation+confidence to continue with the A*.

My memory is fresh now, so reading my code required me to decypher what I had wrote: and I think my 'Rectangle Mapping' code wrong.

When it calls sAddNode()

	sAddNode((unsigned short)(10 - (gaoObjects[liSourceCreature].lusGridX - gaoObjects[liDestinationCreature].lusGridX)) ,
(unsigned short)(6 - (gaoObjects[liSourceCreature].lusGridY - gaoObjects[liDestinationCreature].lusGridY)),
flag_AStarNoGo, liSourceCreature, 1);


... you can see it aligns it to be in the middle. Which is ok except...

.. <thinks> ...

Actually, it looks fine. But I'm rewriting it anyways to make the sAddNode() do the rectangle mapping. Inaddition, it doesn't appear to be placing the GofX value (Distance travelled).

Edit: I rewrote it, and I added the following to take into consideration the distance travelled. My new sAddNote() looks like this..
/* Helper: This helper procedure builds a node in both the open and closed lists. */
void sAddNode(short lusGridX, 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,gaoObjects[liSourceCreature].lusGridY + lusGridY) == flag_Walkable &&
gaoMap[gaoObjects[liSourceCreature].lusGridX + lusGridX + (gaoObjects[liSourceCreature].lusGridY + lusGridY)*1500].loCreature == NULL) ||
lucOverride == 1)
{

/* First step is to build the node on the closed list. */
gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].lucClosed = 1;
gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].lucDirection = lucDirection;

switch(lucDirection)
{
case flag_AStarNoGo:
gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].luiGofX = 0;
break;
case flag_AStarWest:
gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].luiGofX = 1 +
gaoClosedList[(10+lusGridX)+1 + (6+lusGridY)*17].luiGofX;
break;
case flag_AStarEast:
gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].luiGofX = 1 +
gaoClosedList[(10+lusGridX)-1 + (6+lusGridY)*17].luiGofX;
break;
case flag_AStarNorth:
gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].luiGofX = 1 +
gaoClosedList[(10+lusGridX) + ((6+lusGridY)+1)*17].luiGofX;
break;
case flag_AStarSouth:
gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].luiGofX = 1 +
gaoClosedList[(10+lusGridX)+1 + ((6+lusGridY)-1)*17].luiGofX;
break;
}

gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].luiHofX =
abs((10+lusGridX) - 10) +
abs((6+lusGridY) - 6);

gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].lusGridX = (10+lusGridX);
gaoClosedList[(10+lusGridX) + (6+lusGridY)*17].lusGridY = (6+lusGridY);
gaoClosedList[(10+lusGridX) + (6+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[(10+lusGridX) + (6+lusGridY)*17];
break;
}

/* All done. =) */
}
}





and of course, its called like such from the beginning of fGeneratePath()

	sAddNode((short)(gaoObjects[liSourceCreature].lusGridX - gaoObjects[liDestinationCreature].lusGridX) ,
(short)(gaoObjects[liSourceCreature].lusGridY - gaoObjects[liDestinationCreature].lusGridY),
flag_AStarNoGo, liSourceCreature, 1);


Double Edit: Having the sAddNote() do the relativities is making the rest of fGeneratePath() become quite mind boggling, I might change it back.. just trying to think clearly past all this node pushing/pop recursion >.<.

Triple Edit: I'm going to add the following into my sAddNode() to reduce the confusions I'm having.

	unsigned short lusRealGridX, lusRealGridY;
unsigned short lusRelativeGridX, lusRelativeGridY;


[Edited by - Thevenin on August 3, 2005 11:55:16 PM]

Share this post


Link to post
Share on other sites
I solved it (I had the generally right code, it was just too bogged down with minor mistakes that made some pretty odd paths/errors).

If anyone is interested in hearing it, I'll go through in detail what mistakes I made, otherwise, I'll let this thread die.

This newbie has successfully implemented A* pathfinding in his RPG, Yahoo! (And I was on the verge of giving up when it finally clicked in, let this be a lessson never to give up) [grin]

Share this post


Link to post
Share on other sites

This topic is 4514 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this