Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (769) Games in Android Showcase (230) games submitted by our members Games in WIP (856) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1] 2
 ignore  |  Print
 Calculating acceleration and decelleration to reach a certain point in time  (Read 21288 times) 0 Members and 1 Guest are viewing this topic.
cylab

JGO Kernel

Medals: 187

 « Posted 2009-03-16 12:45:35 »

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...

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).

Mathias - I Know What [you] Did Last Summer!
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #1 - Posted 2009-03-16 13:24:38 »

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)?
s = ut + ½at²
Did you want an additional constraint that v(T) = 0?

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).
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?
CommanderKeith
 « Reply #2 - Posted 2009-03-16 13:28:39 »

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

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

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

cylab

JGO Kernel

Medals: 187

 « Reply #3 - Posted 2009-03-16 15:49:06 »

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.

Mathias - I Know What [you] Did Last Summer!
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #4 - Posted 2009-03-16 16:15:35 »

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.
cylab

JGO Kernel

Medals: 187

 « Reply #5 - Posted 2009-03-16 16:23:02 »

OMG I feel so dumb. Thank you!!!

Hope nobody noticed that I have a degree in Electrical Engineering

Mathias - I Know What [you] Did Last Summer!
h3ckboy

JGO Coder

Medals: 5

 « Reply #6 - Posted 2009-03-16 16:26:11 »

OMG I feel so dumb. Thank you!!!

Hope nobody noticed that I have a degree in Electrical Engineering

know the feeling lol
cylab

JGO Kernel

Medals: 187

 « Reply #7 - Posted 2009-03-16 16:34:11 »

Mathias - I Know What [you] Did Last Summer!
cylab

JGO Kernel

Medals: 187

 « Reply #8 - Posted 2009-03-18 13:55:42 »

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.

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...

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

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

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

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... :/

Mathias - I Know What [you] Did Last Summer!
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #9 - Posted 2009-03-18 15:01:44 »

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 `[ 1, 3, 5, 7, 9, 9, 7, 5, 3, 1 ]`

would give the desired smoothing.
DzzD
 « Reply #10 - Posted 2009-03-18 15:27:14 »

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:

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

cylab

JGO Kernel

Medals: 187

 « Reply #11 - Posted 2009-03-18 16:43:25 »

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.

Mathias - I Know What [you] Did Last Summer!
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #12 - Posted 2009-03-18 16:49:15 »

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).
cylab

JGO Kernel

Medals: 187

 « Reply #13 - Posted 2009-03-18 16:57:26 »

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)

Mathias - I Know What [you] Did Last Summer!
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #14 - Posted 2009-03-18 17:38:34 »

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)
I did. I'm not sure what your point is.
cylab

JGO Kernel

Medals: 187

 « Reply #15 - Posted 2009-03-18 17:53:41 »

Maybe I didn't understand your post

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.

Mathias - I Know What [you] Did Last Summer!
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #16 - Posted 2009-03-18 21:30:57 »

I also might not get, if you think that the curve "jumps" are at sample occasions. If so, that's not true.
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?
cylab

JGO Kernel

Medals: 187

 « Reply #17 - Posted 2009-03-18 23:49:24 »

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

Mathias - I Know What [you] Did Last Summer!
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #18 - Posted 2009-03-19 01:06:17 »

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.
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #19 - Posted 2009-03-20 10:39:46 »

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

JGO Kernel

Medals: 187

 « Reply #20 - Posted 2009-03-20 12:14:39 »

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

I didn't notice your last post. The forums "show unread posts" is notoriously broken... thanks for the input. I'll try it on the weekand and will give some feedback.

Mathias - I Know What [you] Did Last Summer!
Jono
 « Reply #21 - Posted 2009-03-21 19:37:03 »

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.

If I've read those graphs correctly, in the second diagram attached the final velocity is not zero. It is equal to the starting velocity of the next segment. Also, A1 > 0 is not necessarily true, since he's shown it moving downward as well =(

As it's described there is an infinite number of solutions. Some extra constraints, like t = T/2 (make the acceleration and deceleration times the same) might help, but depending on the number of segments may still have no unique solution.

As it stands I'd get all the constraints together and find the least squares solution: en.wikipedia.org/wiki/Least_squares

Edit: Just re-read the first post and noticed that you want min(|ac|+|dc|). Least squares isn't right here.. this is a linear programming problem.
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #22 - Posted 2009-03-21 20:15:35 »

I just did this the other day, actually, and needed to spend 20 minutes figuring it out with pencil and paper.

However, my case was a little simpler so I just used a summation to find it.

d = v + v-a + v-2a + v-3a + v-4a ...

Basically because you're decelerating by a every time then each timestep you velocity will be a multiple of a smaller. That ends up simplifying to
d = nv - s(n-1)*a

Where s(n-1) is the summation (sigma) from n-1 to 1. Then I could easily solve for the deceleration knowing the distance I wanted, or I could also solve for a depending upon how long I wanted to take to stop by knowing that v = d/t.

See my work:
OTC Software
Jono
 « Reply #23 - Posted 2009-03-22 19:40:39 »

I just did this the other day, actually, and needed to spend 20 minutes figuring it out with pencil and paper.

However, my case was a little simpler so I just used a summation to find it.

d = v + v-a + v-2a + v-3a + v-4a ...

Basically because you're decelerating by a every time then each timestep you velocity will be a multiple of a smaller. That ends up simplifying to
d = nv - s(n-1)*a

Where s(n-1) is the summation (sigma) from n-1 to 1. Then I could easily solve for the deceleration knowing the distance I wanted, or I could also solve for a depending upon how long I wanted to take to stop by knowing that v = d/t.

Yeah, that's the discrete (sampled) version of the formula pjt33 posted earlier: s = ut + (1/2)*at^2

The summation s(n-1) can be simplified to n(n-1)/2, and then the relation between the two equations becomes more obvious.
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #24 - Posted 2009-03-23 17:32:04 »

If I've read those graphs correctly, in the second diagram attached the final velocity is not zero.
Yes, indeed. That's why I said "Looking at the maths in the post...", which say "v(T)=0" and are inconsistent with the diagram.
cylab

JGO Kernel

Medals: 187

 « Reply #25 - Posted 2009-03-23 18:52:41 »

The final velocity after T is 0, but only in case there are no more updates til t = T is reached. Otherwise I would take the current velocity as v0 and restart the calculation. I still had no time to have another shot on this, but I will post with the results of the various strategies in this thread, if I get at it again.

Mathias - I Know What [you] Did Last Summer!
Jono
 « Reply #26 - Posted 2009-03-23 20:43:28 »

Yes, indeed. That's why I said "Looking at the maths in the post...", which say "v(T)=0" and are inconsistent with the diagram.
Ah, sorry if I took that out of context.
The final velocity after T is 0, but only in case there are no more updates til t = T is reached. Otherwise I would take the current velocity as v0 and restart the calculation. I still had no time to have another shot on this, but I will post with the results of the various strategies in this thread, if I get at it again.
So the second diagram doesn't show a sequence of locations that were known ahead of time.. it's showing the results of a sequence of moves where v(T) was expected to be 0, but were often interrupted by the next move. If that's the case - where you just have to solve it one move at a time - then it looks like pjt33 has pretty much got that sorted.

I get the feeling that even when v(0) > 0 the min(|A1|+|A2|) is when A1 = -A2. If so, the equation will simplify a lot.

Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #27 - Posted 2009-04-20 21:18:41 »

Hm, so what about an equation to compute acceleration needed to go from one velocity to another in a given distance? It seems like you should be able to use the above but I'm having trouble solving for it.

Basically, at t(0) the object has v(0), and after going d it has v(f). Those 4 values are known, but I need to know an a that can get me there. I guess it's all a matter of simplifying v to d/t and a to d/t^2 but I'm still having trouble. Any help?

See my work:
OTC Software
DzzD
 « Reply #28 - Posted 2009-04-20 21:43:55 »

V=V0+t*A

knowing V,V0 and t maybe something like that ?

A=(V-V0)/t

EDIT:

forget. I miss something in reading  .... ...

EDIT2:

not sure you can solve it for a distance and a time at the same time, cause acceleration give the velocity and is not related to distance, if you compute acceleration based on distance as an input you will need to use V0 , and so you can compute for a given distance and time but also a given initial velocity:

A=(2*(d-V0*t))/t²

or

A=(V-V0)/t

Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #29 - Posted 2009-04-20 22:35:47 »

V=V0+t*A

knowing V,V0 and t maybe something like that ?

A=(V-V0)/t

EDIT: forget. I miss something in reading  .... ...

Hm I don't think V = V0 + t*A is correct. It should be V = V0 + A + V0 + 2A + V0 + 3A ... v0 + tA which simplifies to V = t*V0 + ((t * (t+1))/2) * A .

Even so that doesn't really help, because d is nowhere in this equation.

Like say I have the following values:
v(0) = 10 m/s
v(f) = 2 m/s
d = 51 m

When we are at t(0), our position is 0. When we are at t(f), our position is 100. Because I had this pre-calculated, you can see that with an acceleration of -1 m/s we end up at v(f) when we reach d. Time is nowhere in the equation - we don't care how long it takes.

v(0) = 10
d(0) = 0

v(1) = 10
d(1) = 9

v(2) = 8
d(2) = 19

v(3) = 7
d(3) = 27

v(4) = 6
d(4) = 33

v(5) = 5
d(5) = 39

v(6) = 4
d(6) = 44

v(7) = 3
d(7) = 48

v( = 2
d( = 51

Maybe someone else can see some pattern in that? It's easy to figure out d or t, but not a when given a d - at least I'm having trouble with it.

See my work:
OTC Software
Pages: [1] 2
 ignore  |  Print

 EgonOlsen (1670 views) 2018-06-10 19:43:48 EgonOlsen (1707 views) 2018-06-10 19:43:44 EgonOlsen (1159 views) 2018-06-10 19:43:20 DesertCoockie (1585 views) 2018-05-13 18:23:11 nelsongames (1186 views) 2018-04-24 18:15:36 nelsongames (1709 views) 2018-04-24 18:14:32 ivj94 (2533 views) 2018-03-24 14:47:39 ivj94 (1758 views) 2018-03-24 14:46:31 ivj94 (2836 views) 2018-03-24 14:43:53 Solater (971 views) 2018-03-17 05:04:08
 Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20Deployment and Packagingby philfrei2018-08-19 23:54:46
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org