Jump to content
  • Advertisement
Sign in to follow this  
-justin-

Newb doing A*, help?

This topic is 4830 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'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 < MAPX; x++)
{

// go through x

    for (int y = 0; y < MAPY; y++)
    {

/// go through y

      // if F value is lower than lowest at time then update
      if((path[x][y].F < 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 < MAPX; x++)
{

// go through x

    for (int y = 0; y < 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 <= MAPX)
{
adjSquares(tempMapX+1, tempMapY, targetX, targetY, tempMapX, tempMapY, 10);
}

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

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

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

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

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

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

if((tempMapX+1 <= MAPX) && (tempMapY-1 >= 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)
{

if(path[adjX][adjY].list == -1)
{
  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
  path[adjX][adjY].H = 10*(abs((adjX)-targetX) + abs(adjY-targetY));

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

  // figure out F
  path[adjX][adjY].F = path[adjX][adjY].G + path[adjX][adjY].H;

  // add to open list
  path[adjX][adjY].list = 0;

  // update the last square added to open list
  lastSquareX = adjX;
  lastSquareY = adjY;

}

else if(path[adjX][adjY].list == 0)
{

  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
  if (tempG < path[adjX][adjY].G)
  {
      path[adjX][adjY].parentX = currentX;
      path[adjX][adjY].parentY = currentY;
  }
  
}

}

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


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


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


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

path[adjX][adjY].G = path[parentGx][parentGy].G + modifier;

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


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


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


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


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


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


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

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!