Sign in to follow this  
Fluxing

Algorithm for an object that follows another object, with acceleration.

Recommended Posts

I'm trying to figure out the math to get one sprite to follow another, and I can't seem to figure it out.
I've got two objects, a target and a follower, that both have 2D vectors for their position. I want the follower to always try to get as close to the target as possible. However, to make the movement somewhat realistic, I added velocity and acceleration so that the follower slowly gets going, picking up speed, and then slows down again when it needs to change direction (because the target moved somewhere else, for instance).
What i'm currently doing is the following:

I'm calculating the direction of the target from the follower's perspective by subtracting the follower's position vector from the target's position vector, and normalizing the resulting vector. This gives me a unit vector pointing towards the target (from the follower's perspective).
Then, I check if the follower's velocity vector's length (which is initially zero) isn't larger than a predefined maxSpeed value, and if so, I change the velocity by multiplying the direction unit vector by a predefined acceleration value and adding that to the current velocity vector.
This, however, results in the follower constantly picking up speed, overshooting the target (because it missed it), slowing down again to change direction, and then picking up speed and overshooting the target again.

I'm fairly sure there's a pretty simple algorithm for this, but I just can't seem to figure it out. Can anyone help?

Share this post


Link to post
Share on other sites
This is the normal behaviour of such systems.

I would try do introduce some "damping" into the system. Damping is an acceleration (or force) that acts in the opposite direction of the velocity between the objects ([b]dv[/b] from now), and it should depend (maybe linearly) on [b]dv [/b](the length of [b]dv[/b]). The bigger the velocity, the stronger the damping is. Zero velocity, zero damping. This means this damping always tries to slow down motion.

This damping could only take effect when the follower is inside a given radius from the followed object (exists or doesn't exist). Or maybe the damping could also depend linearly on the on the radius (and could be zero if the follower is outside of it)

You could play with parameters to have the desired effect.


I said "try", because I can't visualize how it would work, but it shouldn't be hard to implement and test it. Just some ideas. Edited by szecs

Share this post


Link to post
Share on other sites
I'd do something along these lines:

[CODE]
#define RESISTANCE 0.2f
void Closing(float target[2], float follower[2])
{
follower[0] += (target[0]-follower[0])*RESISTANCE;
follower[1] += (target[1]-follower[1])*RESISTANCE;
}
[/CODE]

This would get follower as close to target as possible, without over reaching it.

Share this post


Link to post
Share on other sites
I think TMarques's code might not give the right feel of following a physical system.

This is what I would try first:
[code]
// Steering behavior
follower.acceleration = spring_constant * (target.position - follower.position);
if (length(follower.acceleration) > max_acceleration)
follower.acceleration = max_acceleration / length(follower.acceleration) * follower.acceleration;

// Euler integration step, with linear drag
follower.velocity += follower.acceleration * delta_t;
follower.velocity *= exp(-drag_coefficient * delta_t);
follower.position += follower.velocity * delta_t;
[/code]

You need to play with spring_constant, max_acceleration and drag_coefficient until you like the result.

You should also look into [url="http://www.red3d.com/cwr/steer/"]steering behaviors[/url], particularly the "seek" behavior.

Share this post


Link to post
Share on other sites
Following with acceleration/velocity can be tricky. My suggestion would be to estimate the time to reach the target, estimate the target's position at that time, and possibly iterate on that to improve.

As far as the flight profile, I would say start with max acceleration until either you reach max speed or you need to slow down, then max deceleration until stopped. I suggest this because you can use the standard physics equations easily in this case, e.g.:

Acceleration phase: d = vt + 0.5at^2
Cruising phase: d = vt
Deceleration phase: d = vt - 0.5at^2

Where d is the distance covered, v is the velocity at the start of the phase, t is the time taken, and a is the max acceleration.

Smoother acceleration could be used but the maths would be more challenging.

Share this post


Link to post
Share on other sites
If you want the follower motion to be smooth (continuous velocity) and not to lag behind the target, at least when the target is moving at a constant velocity, what you can do is:

1. Predict where the target will be in X seconds (so predictedTargetPos = currentTargetPos + currentTargetVel * X)

2. Calculate the acceleration you'd need to apply to your follower in order to reach the predicted target in Y seconds, assuming the acceleration stays constant over that period (it won't of course, but never mind). So basically you solve currentFollowerPos + currentFollowerVel * Y + 0.5 * desiredFollowerAcceleration * Y * Y = predictedTargetPos to give you desiredFollowerAcceleration. (this is just the s = v*t + 0.5*g*t^2 equation you might have seen before).

3. You could just apply the desiredFollowerAcceleration directly, or convert it to a force, or maybe you want to clamp it so your follower has limited capabilities.

For the follower to follow without lag, then of course X = Y. You might want a little bit of lag so your sprites don't sit on top of each other, in which case choose Y > X.

This should give you smooth follower motion that tracks the target exactly when the target is easy to predict, but will overshoot etc when the target changes direction. The overshoot/smoothness will be larger for larger X and Y values.

The other use for this might be in a camera system - where you want the camera to follow an object, but not exactly, and also not to lag behind it when it's moving fast. Actually, for a fast moving camera you might want to choose X > Y - that way when an object is moving to the right, then the camera places it on the left side of the display, because where it's going to is more interesting than where it's come from. Edited by MrRowl

Share this post


Link to post
Share on other sites
To make this smooth and realistic in terms of acceleration, it's not sufficient to calculate a trajectory only on the distance between the objects, the trick is to arrive / get close to the target object while simultaneously achieving the same velocity as the target.

I wrote here earlier about a solution for this in 3D. (The principle is the same in 2D.) The solution uses the chasing vessel's/object's acceleration capability and doesn't require any 'damping' or similar to achieve a realistic effect. It might be overkill for your requirements but it gives an optimal and smooth trajectory. The code should be straight-forward to adapt to 2D. If you're interested you can find the solution here:

[url="http://mmoarch.blogspot.se/2012/05/computing-space-travel-implementation.html"]http://mmoarch.blogspot.se/2012/05/computing-space-travel-implementation.html[/url]

Share this post


Link to post
Share on other sites
Thanks for all the replies, this has been quite helpful.

I've experimented with many of the suggestions here, but they either weren't suited for this particular scenario or went over my head. In the end I went with the following:

Each frame, I determine the stopping distance of the follower using the formula d=v2/(2a) (where d is distance, v is velocity and a is acceleration). This is the distance required to come to a full stop at the current speed and acceleration rate. If the distance between the follower and the target is equal to or smaller than the stopping distane, I calculate the speed the follower should have in order to be able to stop exactly in time using vr = d/(2/(2a)) (where vr is the required velocity) and give the follower that velocity.

If the follower is far enough away from the target, I calculate the target direction (the normalized vector of target.position - follower.position), multiply it by the normal acceleration rate and adding the result to the follower's current velocity.

This works, except for the fact that in some situations the follower can't make a turn fast enough (because the acceleration is too low) and keeps circling around the target forever. I solved this by calculating the dot product between the target direction and the follower's normalized velocity, and checking if it is below a certain threshold (0.99 in this case). If it's below that threshold, it means the direction the follower is travelling in and the direction of the target are too far apart, and a higher turning acceleration is used instead of the regular acceleration.

This results in the follower accelerating at a normal rate when travelling in approximately the right direction, but turning at a faster rate when a more drastic change in direction is required. This doesn't always look completely natural, but works for this scenario. Also, the follower sort of bobs around in place at all times, which helps to mask any strange stops or sharp turns that occasionally pop up.

Many thanks to all who contributed for helping me get to this point!

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