# Newb doing A*, help?

This topic is 4897 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm attempting to do A* for my pathfinding for my upcoming Pac-Man clone which I wish to implement. Obviously, one of the Ghosts will use A* to track down Pac-Man. I haven't compiled this or anything, but I'd like to know if how I'm proceeding is overall correct (I'll compile when I get home, right now I'm at a computer lab in my Uni) (i will attempt to make the code more readable later) here's the example of the lvl (this is small for starters ^++&* *++** *+++* ***** the * is the walkable, the + is the non-walkable, the ^ is the player, the & is the destination so assume (0,0) is starting point and, (3,0) is ending point
#define MAPX 4
#define MAPY 3

struct aStar
{
int F, G, H;
int list;  // -1 = no list, 0 = open, 1 = closed, 2 = unwalkable
int parentX, parentY;
}  path[MAPX][MAPY];

int lastSquareX, lastSquareY, targetX = 3, targetY = 0;

void main()
{
// this is the chunk of the program... just for example
while((lastSquareX != targetX) && (lastSquareY != targetY))
{
runAStar();
}
// go through path
// this is where the enemy would go through the path... i'm thinking of using another struct called pathToFollow for this

}

void runAStar()
{
int tempF, lowestF, tempMapX, tempMapY;
bool firstTime = true;

tempF = 5000;  // any number should be lower than this... this gets the ball rolling so to speak

if(firstTime != true)
{

for(int x = 0; x &lt; MAPX; x++)
{

// go through x

for (int y = 0; y &lt; MAPY; y++)
{

/// go through y

// if F value is lower than lowest at time then update
if((path[x][y].F &lt; tempF) && (path[x][y].list = 0))
{
tempF = path[x][y].F  // new lowest F cost
tempMapX = x;
tempMapY = y;
}
}
}

}

else
{
tempMapX = 0;
tempMapY = 0;
firstTime = false;

// go through the map and make everything so that it isn't on either open or closed list

for(int x = 0; x &lt; MAPX; x++)
{

// go through x

for (int y = 0; y &lt; MAPY; y++)
{

// go through y

// set path on NO list
path[x][y].list = -1;

}
}

}

path[tempMapX][tempMapY].list = 1;  // put current square on closed list

// now check the adjacent squares and make sure they are valid

if(tempMapX+1 &lt;= MAPX)
{
adjSquares(tempMapX+1, tempMapY, targetX, targetY, tempMapX, tempMapY, 10);
}

if(tempMapY+1 &lt;= MAPY)
{
adjSquares(tempMapX, tempMapY+1, targetX, targetY, tempMapX, tempMapY, 10);
}

if(tempMapX-1 &gt;= 0)
{
adjSquares(tempMapX-1, tempMapY, targetX, targetY, tempMapX, tempMapY, 10);
}

if(tempMapY-1 &gt;= 0)
{
adjSquares(tempMapX, tempMapY-1, targetX, targetY, tempMapX, tempMapY, 10);
}

// diagonal
if((tempMapX+1 &lt;= MAPX) && (tempMapY+1 &lt;= MAPY))
{
adjSquares(tempMapX+1, tempMapY+1, targetX, targetY, tempMapX, tempMapY, 14);
}

if((tempMapX-1 &gt;= 0) && (tempMapY-1 &gt;= 0))
{
adjSquares(tempMapX-1, tempMapY-1, targetX, targetY, tempMapX, tempMapY, 14);
}

if((tempMapX-1 &gt;= 0) && (tempMapY+1 &lt;= MAPY))
{
adjSquares(tempMapX-1, tempMapY+1, targetX, targetY, tempMapX, tempMapY, 14);
}

if((tempMapX+1 &lt;= MAPX) && (tempMapY-1 &gt;= 0))
{
adjSquares(tempMapX+1, tempMapY-1, targetX, targetY, tempMapX, tempMapY, 14);
}

}

void adjSquares(int adjX, int adjY, int targetX, int targetY, int currentX, int currentY, int starting X, int starting Y, int modifier)
{

{
int parentGx, parentGy;  // this holds our temporary parent data;  it tells us what the next parent is

// if it isn't on a list
parentGx = currentX;
parentGy = currentY;

// determine heuristic

// now the fun part, determine the G value
while ((parentGx != startingX) && (parentGy != startingY))
{
parentGx = path[parentGx][parentGy].parentX;
parentGy = path[parentGx][parentGy].parentY;
}

// figure out F

// update the last square added to open list

}

{

int tempG;  // holds G to compare to current G value of square

// if it's on the open list
// get parent G value, add modifier, determine if that's lower than its current cost
tempG = path[currentX][currentY].G + modifier

// if lower than current cost than make that square the parent square
{
}

}

}


thanks, and if i'm totally off track then plz give me some pointers! i was following a tutorial... (i don't care much about speed right now but any comments on that as well will be helpful!)

##### Share on other sites
Hmm, you're re-using the map structure as the A* node structure - good for performance, bad for clarity. (And it only works for grid maps and the like, not for some more abstract searches.)

Your G calculation seems to be using a loop - why? G should just be the G of the previous node plus the cost of moving to G.

And I don't see the point of that if (firsttime) business - why not separate out the initialisation?

Which tutorial are you following? By the looks of it, it's probably not the clearest of explanations.

##### Share on other sites
i'm using this tutorial:

http://www.gamedev.net/reference/articles/article2003.asp

i totally get the theory but to be honest when i looked at the source i was little lost :-/ so i just tried to implement the code myself...

so i tried to ask one of the AI professors but he told me i need to enroll in the course -_-' can't do othat for 2 years...

i mean, will my A* search work? (after i fix some of the problems) b/c all i need it for is pac-man i'm not looking for the next amazing algorithm :P

thanks for the help Kylotan, i really appreciate it :)

EDIT: looked at sample code again and it looks complex but doable, i'll get to it after classes; think i was just being wimpy...

##### Share on other sites
It's a little hard for me to say if the code will work, because it's quite complex. Basically your G calculation should be:

But I think overall, what you have there will work ok, for grid maps, with no teleporters or tunnels from one side to the other, or other discontinuities.

##### Share on other sites
awesome, i will try it later on tonight! are there any other good (particularly aimed at newbie AI'ers) tutorials to check out??

thanks for all your help! :)

##### Share on other sites
I don't know any tutorials off-hand. Amit Patel's pages have some details I think, but I've no idea if they're good or not. Ideally you'll find somewhere which describes A* in terms of how it relates to best-first search or breadth-first search. A good understanding of search methods in general is very useful for AI.

##### Share on other sites
yea best-first search and breadth-first search, neural networks, and the one that starts with a D are on my list of things to do after i get A* working with my pac-man clone; although these probably won't come till later when i work on an RTS or something similar

##### Share on other sites
Bear in mind that A* is based on those search methods. They're not advanced methods to be learned after A*, rather, A* is the advanced method to be learned after the basic search types. :) Obviously many game programmers skip these fundamentals, and therefore sometimes have problems understanding why the algorithm works or why their implementation doesn't. Then someone throws words like "monotonic" or "admissible" at them and their eyes glaze over...

Sadly the only decent tutorials on these things that I can find seem to come in books.

##### Share on other sites
I like this for a general overview...
http://www.gamasutra.com/features/19990212/sm_01.htm
and then this for A* specific...
http://www.gamedev.net/reference/articles/article2003.asp

##### Share on other sites
@tonyg thanks, yea that gamedev one is the one i used to setup my A* (still not tested... have to release last game first [polishing it up]); and yea, i'm mad at gamesultra b/c when i try to look at the tutorials they always ask for registration; i registered there once and i couldn't login, needless to say it made me mad; if i find something that sounds particularly good then i will go ahead and register there; most likely it was just b/c i didn't have cookies enabled or somethin of the like...

@kylotan yea, i have Tricks of the Windows Game Programming Gurus and it just sorta skims over them. When I get better at game-programming in general I'll have to get a book that goes over them. However, as of now I don't have any games that use AI which is why I'd like to get into it. I'm about to release a game that could be called a fighting-type; it'd be nice to use a state-machine for that but I haven't read up on that enough!!!

yea i guess i'm one of those n00bs that is trying to learn A* first...monotonic? admissible??? *eyes glaze over* :-D

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 29
• 16
• 11
• 10
• 11
• ### Forum Statistics

• Total Topics
634112
• Total Posts
3015585
×