• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Sign up now

# A-Star Path Following Questions

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1Psychopathetica  Members

Posted 18 December 2012 - 03:40 PM

Hi. Im currently working on a 2D RPG with a tile engine, and got a pretty solid A* Pathfinding engine, but as for A* pathfollowing, I ran into some issues. Ok before I begin, I have two sprites. One is the player than you can freely move across in the tile engine and the other is the monster that is moving node to node with the A* path. Currently I'm using this pseudo code to help the sprite follow the path:

[source lang="cpp"]speed_per_tick = 1; //constant speed you want the object to move atdelta_x = x_goal - x_current;delta_y = y_goal - y_current;goal_dist = sqrt((delta_x * delta_x) + (delta_y * delta_y));if (goal_dist > speed_per_tick){ Ratio = speed_per_tick / goal_dist; x_move = Ratio * delta_x; y_move = Ratio * delta_y; new_x_pos = x_move + x_current; new_y_pos = y_move + y_current;}Else{ new_x_pos = x_goal; new_y_pos = y_goal;}[/source]

It works great when the player isn't moving, but when he does move, it seems ok for a bit but sometimes once in awhile I'll notice some jitteryness with the monster as its following the path when the A* Path gets cleared or changed. Which leaves some questions I can't seem to find on google.

First of all, when the player moves and passes the next node, I obviously need to clear the A* Path and recalculate, but do I need to also clear and recalculate it when the monster reaches the next node?

Secondly It seems the path following code shown above doesn't work too well with diagnal cause the monster gets locked in between the two nodes and bounces back and forth as the player moves, but stops when the player stands still and the monster continues following the path as nortmal. And believe me, Its not the A* pathfinding code I have thats causing this cause the last following code I used didnt lock the sprite between nodes. Yet I had to change it cause I had too many problems with the last code I used.

Third, I found that using the top left of every tile as a node brought about too many problems. Moving right and down is normal. But when moving left and up, it tends to skip tiles, or drags against the wall when about to turn. I basically had to rethink this, draw some tiles on a sheet of paper, make little thick squares, and solve this on my own. My solution was to use the center of the tiles as nodes. As a result it moved normal in all 8 directions. In other words, any side of the player passing the center of a tile will be the next node. My question is that would this be the correct way of doing this? I'm sure many of you had similar problems. And I'm looking for solutions. Thanks in advance.

Edited by Psychopathetica, 19 December 2012 - 12:19 AM.

### #2Morphex  Members

Posted 21 December 2012 - 09:28 AM

You A* algortim shouldnt use a coordinate in a tile. It should use the tile itself. A simple explanation, if you are at tile H (H being the representation of the tile in your engine), if you want to move left you go to tile H(x-1,y), and your engine should move the sprite to the correct position.

That way you have a constant movement function for all the game, and will prevent jerkiness and other stuff. Other than that. I need more clarification in what you are tring to atempt because I don't get the monster/player functions. The monster is following a serie of nodes right? So the order of operations would be something like this:
Call this to generate the path:

Monster.FindPath(Monster.Position,NodeB);

In your update Function you would have something like this

If(!Monster.DestinationReached)
{
bool validate = Monster.WalkPath(); //Returns true if it was able to move, otherwise if the current path is blocked rreturns false.
if ( !validate)
Monster.FindPath(Monster.Position,NodeB);
}


Now about that validate boolean, it is a fail safe mechanism, that will take in account if something crosses the monster predefined path, you have diferent possibilities there, you can wait for the path to be unblocked, or you make the monster change its course to avoid the obstacle. This way it would avoid the obstacle.
Similar to what you did with the monster, the player would operate in the same way.

Hope this helps

Check out my new blog: Morphexe

### #3Psychopathetica  Members

Posted 23 December 2012 - 08:42 AM

Basically the player is you or anyone that plays the game. When you, the player, move and end up on the next tile, the entire A* Path of the monster changes by getting cleared, then it recalculates the A* Path for a new path for the monster to follow. That way the monster can goto the proper end destination, which is at the player itself. I never thought of using the tiles themselves but its probably gonna be hell changing it all to do that. But now that I think about it... it all makes sense. Heres why. I had the A* Path collect a series of coordinates based on the pixel location of every node. When the monster moves left towards the next tile, the first pixel from the top left of the monster being inside the left tile will recalculate the coordinates of the monster showing its inside the next tile.And since my path following code was having the monster move to the next tile being (-1) of the next path, this would make the monster try move to the tile after that! Its no wonder why the monster was draging on the walls in corners moving left / up, while right / down was normal.

### #4Psychopathetica  Members

Posted 06 January 2013 - 12:07 AM

Ok I figured it out. Here is the actual solution. I had to create a variable as part of the Sprite structure called Moving for the monster, declared as a boolean which is used to check if the monster is currently moving to the next node. If it reaches the node, itll be declared as false for one frame. Then be true as it continues to move to the next node. I also created a static variable inside my Follow_AStar function called Temp_AStar_Path declared as a 2D point, which has just X and Y. This variable just gets the next node the monster is gonna move and stores it temporarily. Now before the movement even begins, If Moving = False then temporarily store the next node the monster is gonna move. If it hasnt reached the next node, the monster will continue moving and Moving is true. If it reaches the next node, Moving is false.

Now in my code, if you, the player, moves to the next node, the AStar path will be cleared and recalculated regardless if the monster aint done moving to the next node. Now with my above solution, t doesnt matter where the player moves anymore. The monster will not follow the new Astar node until its done following the old node. No more jitteryness. Couldn't believe it took me months to figure this out because there is zero code on this crap on Google except just on getting the AStar path.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.