• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Psychopathetica

A-Star Path Following Questions

3 posts in this topic

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 at
delta_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. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Edited by Psychopathetica
0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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.

1

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

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  
Followers 0