Sign in to follow this  
Aztral

Navigating a path on a grid

Recommended Posts

Aztral    1200
I've got a pathfinder up and running such that it can successfuly find a path through a tile grid. Now my issue is with getting my character to smoothly animate between grid nodes. Basically my question is how can I make the character travel from one node to another node without getting off the path. Keep in mind my character only moves at 45 degree angles. These are my thoughts: I know the width/height (nodes are square) of a single node in the game in terms of pixels. Therefore I know the distance that needs to be traveled in order to get from one node to another node. Say a node has a width of 15 pixels. Say my player has a speed of 7 pixels per frame and say I'm moving perfectly horizontally. After two frames I'll have moved 14 pixels. This is relatively close and I can just say ok then and start moving to the next node (at a 45 degree angle). The issue here is that after moving over 200 nodes it's possible that I will be off of where I should be by 200 pixels which is not good. My solution to this, which might be too complicated, is as follows: I know the distance I have to travel to get from one node to the other. I can easily determine the distance I have left to travel each frame in order to reach the next node in the path. If this distance is less than my player speed, I can simply add to my playerx and playery the remaining distance to get to that node. At this point, say I only have moved 2 units this frame, I have 5 pixels left. I can start moving towards the next node in the path. This guarantees that I travel the correct distance each frame, without getting off center. Is this a reasonable solution? Am I somehow overcomplicating things? Thanks for any advice.

Share this post


Link to post
Share on other sites
Captain P    1092
Quote:
If this distance is less than my player speed, I can simply add to my playerx and playery the remaining distance to get to that node. At this point, say I only have moved 2 units this frame, I have 5 pixels left. I can start moving towards the next node in the path.

Sounds like a good solution. Check the distance to the current destination, and if it's less than your movement distance, put yourself at that destination, subtract that distance from your movement distance and determine the next destination. Then repeat all that until you have no movement distance left. And of course, if you can't reach a destination, move towards it as far as you can.


EDIT: I noticed you're mentioning playerx and playery variables - did you consider writing/using a class for positions/velocities? With some properly overloaded operators (+, -, etc.) and some other functions (length, setLength) it'll make working with positions and velocities more natural.

[Edited by - Captain P on February 12, 2010 5:14:31 AM]

Share this post


Link to post
Share on other sites
Kuraitou    250
Your solution is probably the easiest way, but there's no reason for you to not be a little more precise in your measurements.

The formula for distance is d = st, where d is distance, s is speed, and t is time.

It's easy to derive an equation for speed from the above information:
s = d/t

Substitute the distance between tiles (15px) for distance, and time you want it to take for the time between one tile (i.e. 2s):
s = 15px/2s
s = 7.5px/s

You could define pixels-per-frame (I do this a lot in my projects where I need frame-precise movement) as the reciprocal of the FPS.

So if your game is guaranteed to run at 60FPS, the formula would become:
s' = s * (1 frame / 60 frames per second)
s' = 7.5px/s * (1 frame / 60 frames per second)
s' = ~0.125px/frame

After 120 update frames, the equivalent to two seconds in this case, you will have moved no more than and no less than 15 pixels, assuming your game is timing frames correctly.

I also suggest that you use a vector class like Captain P mentioned; it will greatly simplify much of your code. Speed in this case should be replaced with velocity, a vector quantity. The distance formula holds true for both the X and Y components of velocity.

Share this post


Link to post
Share on other sites
Aztral    1200
Thanks for the responses, sorry I've taken a while to get back.

I think I will write a class to handle positions/velocities. Unfortunately I'm using AS3 and I can't overload operators, but I'll make do.

Since I posted my classmates have proposed a different solution. . Personally I like the original better but let me run this by you.

They propose that rather than restricting movement to the center of a node, I do this:

When I start the pathfinding process I also take into account the speed the player is traveling:

Say I'm at node 5, 5 - and each node is 10 pixels by 10 pixels. Say my exact world location is (5.3, 5.5). Say my speed is 8. If I want to check the node north of me, I'd add my speed (say 8) to my precise worldy location. I'd be trying to move to (5.3, 5.5 + 8) = (5.3, 13.5). To check to see if this is valid I'd just check if the node at (5, 13) is a wall or not. Then, rather than returning a list of nodes to travel to, I'd return a list of points to travel to.

I don't like this approach for a couple of reasons:

1.) It's not 'uniform.' That is, it does not hold for all possible speeds. I.e. if I'm moving at a speed that is greater than the size of a node, I could skip over a node and potentially move through a wall. I'd have to add a lot more logic to the pathfinder.

2.) It's possible to move from the current node to the same node, and I'd have to add more logic to the pathfinder to account for that.

2.) The path would have to be recalculated every time a players speed changes.

What do you guys think?

Share this post


Link to post
Share on other sites
Captain P    1092
Quote:
Original post by Aztral
I think I will write a class to handle positions/velocities. Unfortunately I'm using AS3 and I can't overload operators, but I'll make do.

In that case, you might as well use flash.geom.Point.

Quote:
When I start the pathfinding process I also take into account the speed the player is traveling:

Speed should have no effect on the pathfinding, only on following the path. These are two seperate steps, but it looks like your friends are mixing them. That's only making things more complicated for no real benefit.

There is little difference between a list of nodes and a list of positions anyway: you're likely using the centers of these nodes as positions already.

Share this post


Link to post
Share on other sites
Aztral    1200
Thanks Captain P those were my thoughts as well.

This solution brings up another question in my mind, which is animating a character as it walks a path:

Will it look awkward if the character moves diagonally to a destination then starts moving vertically in the same frame? Should I animate based on the kind of movement happening at the end of the frame?

It seems like it will look bad if the character covers a large enough distance and changes it's direction mid frame.

Share this post


Link to post
Share on other sites
Captain P    1092
Quote:
Original post by Aztral
Will it look awkward if the character moves diagonally to a destination then starts moving vertically in the same frame? Should I animate based on the kind of movement happening at the end of the frame?

Shouldn't look awkward - it'll happen so fast that you likely won't even notice. All you will see is a character that, at the end of frame one, walks diagonally, and at the end of frame 2, walks vertically. And yes, render things after you've updated them (that is, after you've updated everything in the scene) - otherwise the game will lag one frame behind, visually.

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