Calculating acceleration and decelleration to reach a certain point in time

Game Mechanics
#1

I am ashamed to have to ask such questions, since all this was covered in my math classes (but 10 years ago) and I hate to have become such a dumb blockhead after multiple years of j2ee development, but… :wink:

Say there is a train at point p0 travelling at speed v0 (which might be 0!) and has to reach a point p1 in constant time T. How would I compute the minimum needed acceleration ac and deceleration dc to reach p1 in exactly T with the constraints that ac <= dc and min(|ac|+|dc|). Any pointers on how to solve such problems (fast)?

And for alternative ideas: the real problem is, that I have to smooth abruptly changing input values to produce a smooth 2d-curve y’ over t where y is only accessible locally at t (I can’t query t+n, but could perhaps cache some t-n).

#2

s = ut + ½at²
Did you want an additional constraint that v(T) = 0?

Use a spring model? But that’s a rather short description, and I suspect that more detail will be needed to give a good answer. To be precise: given streaming input y(t) and assuming output y’(t), what is the function you’re trying to minimise and under what constraints?

#3

Haha, while I was typing pjt33 had the same idea…

s = ut + (1/2)*at^2

Solving for a, your unknown,

a = 2*(s - ut)/t^2

#4

See the attachment for a viusualization what I want to do. The upper curve is the simple case, while the lower represents the case where the input is changing unpredictable. The red curve is the input, the green the desired output. The input is not sampleable (does this word exist?:)) for t+n, but I could cache the input for t-n (more than one cached sample is undesired but possible).

The input is sampled once per frame (so the sample period might be varying due to rendering time). The output of this query should be the smoothed value at sample time.

#5

For the sample smoothing, what you are after is a low-pass filter. That page deals mainly with signal processing electronics guff, but look here for more useful information.

#6

OMG I feel so dumb. Thank you!!!

Hope nobody noticed that I have a degree in Electrical Engineering :persecutioncomplex:

#7

know the feeling lol :smiley:

#8

:smiley: Thanks

#9

While theoretically the right idea, the result is not what I am looking for (see attachment), so I am back to the acceleration deceleration thingy…

This would not be entirely correct, since this assumes that the acceleration is equal to the deceleration. Should be more lke

s = v0 * t0 + a1 * t^2 + a2 * (T-t)^2

I have s, v0, t0 and T. I need a1, a2 and t under the constraints that (T-t) >= 0, a1 >= 0, a2 <= 0, v(T)=0 and min(|a1| + |a2|). The problem is how to solve the min constraint… :confused:

#10

You can get the transitions you are after by jiggering with the weighting of the average. Try weighting the most and least recent samples lightly, but samples in the middle more heavily. A linear progression in weighting factors will probably work for you.

For instance, say you have the 10 most recent samples: a relative weighting factor array like

[ 1, 3, 5, 7, 9, 9, 7, 5, 3, 1 ]

would give the desired smoothing.

#11

maybe what you are looking for is a Polynomial => http://en.wikipedia.org/wiki/Polynomial.

you can find a polynomial that lie on any set of points (for any number of point, the difference will be the polynomial “order”), for example if you want a polynomial that go trough 2 points 3 points you will use an equation like : y=ax²+bx+c for three four points ax^3+bx²+cx+d etc…

you just have to set the equation and solve it, it will become pretty complexe for a lot of point, but the advantage is that you will have an unic and continuous function y=f(x). for a lot of point you will better use a subset of point like the neigbourgs points and interpolate them.

one of interpolation such as the following http://freespace.virgin.net/hugo.elias/models/m_perlin.htm, the cubic interpolation is a polynomial but it only use a subset of neighbourg points.

cubic one is polynomial with an order 3:

http://freespace.virgin.net/hugo.elias/models/m_inter4b.gif

EDIT : little error order 2 => 3 point not 2

#12

I tried this using a bezier spline with limited success, but the nature of the input sampling seems to make this too complicated. I may give this another try, but I will try the weighted average and the acelleration thingy first.

Thank you so far.

#13

Looking at your example I think all you want is to find a function f(x) with the following properties:
f(0) = 0
f(1) = 1
f’(0) = 0
f’(1) = 1
For all 0 < x < 1, f’(x) > 0

Then you could do a linear transform on f for each segment: if you sample y0 at t0 and y1 at t1 then your output in t0 < t <= t1 is y0 + (y1-y0) f((t-t0)/(t1-t0)).

There are various functions you could choose for f, although the simplest is probably f(x) = sin^2(2x / PI).

#14

Look at the first attachment I posted. The 0-1 sequence is just the simplest case. Usually you get unpredictable input values (by a random function or mouse movement or whatever)

#15

I did. I’m not sure what your point is.

#16

Maybe I didn’t understand your post :wink:

I don’t want to interpolate values and my input values are at arbitrary times with arbitrary numbers.

I also might not get, if you think that the curve “jumps” are at sample occasions. If so, that’s not true. Assume that the square curve in my example has a period of 2s. So each state lasts for 1s. The values are sampled at a rate of 60 per seconds. So I get 60 0 values and 60 1 values. For every sample I want to return a smoothed value instead of the original 0 or 1 value from the input.

So correct me if misunderstand your proposal, but it seems, it would only work for interpolating between sampled inputs or if the inputs don’t change while the transition is calculated. Another problem might be, if I use a sinusidal transition, I can’t lineary “sweep over” samples lying on the interpolation path without getting an ease in and ease out effect.

#17

I think this may be the source of confusion. How do you know the value of the curve other than at sample points? Could you redo your diagram showing where samples are taken?

#18

Maybe this sentence wasn’t clear. See the second post with an attachment. The red dots are the input samples.

#19

Ah, looking at the maths in the post with the second attachment I think I see what you’re trying to do.

At time t0 you have velocity v0.
You accelerate until t0 + t with acceleration a1. You then accelerate until t0 + T with acceleration a2. At t0 + T the velocity is zero.
The distance travelled from t0 to t0 + T is s.

Then s = v0 t + ½ a1 t² + ½ (T - t) (v0 + a1 t)
and (T - t) a2 = - (v0 + a1 t)

Since a1 > 0 and a2 < 0, |a1| + |a2| is a1 - a2 = (a1 T + v0) / (T - t).
Rearrange the expression for s to get a1 as a function of t - if I’m not mistaken it’s a1 = (2 s - 3 v0 t + T) / (Tt).
Substitute in: the expression you want to minimise is now (2 s - 2 v0 t + T) / (Tt - t²)
Differentiate with respect to t and set equal to zero and you should have a quadratic in t to solve.

#20

Is the absence of response an indication that the problem is solved or that you didn’t notice my last post?