Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (483)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Calculating acceleration and decelleration to reach a certain point in time  (Read 9546 times)
0 Members and 1 Guest are viewing this topic.
Offline cylab

JGO Ninja


Medals: 43



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

Mathias - I Know What [you] Did Last Summer!
Offline pjt33
« 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?
Offline 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

Solving for a, your unknown,

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

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline cylab

JGO Ninja


Medals: 43



« 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?Smiley) 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!
Offline ryanm

Senior Member


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

JGO Ninja


Medals: 43



« 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  persecutioncomplex

Mathias - I Know What [you] Did Last Summer!
Offline 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  persecutioncomplex

know the feeling lol Cheesy
Offline cylab

JGO Ninja


Medals: 43



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

know the feeling lol Cheesy
Cheesy Thanks

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

JGO Ninja


Medals: 43



« 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

Solving for a, your unknown,

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!
Offline ryanm

Senior Member


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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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:
Click to Play


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

Offline cylab

JGO Ninja


Medals: 43



« 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!
Offline pjt33
« 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).
Offline cylab

JGO Ninja


Medals: 43



« 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!
Offline pjt33
« 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.
Offline cylab

JGO Ninja


Medals: 43



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

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.


Mathias - I Know What [you] Did Last Summer!
Offline pjt33
« 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?
Offline cylab

JGO Ninja


Medals: 43



« 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!
Offline pjt33
« 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.
Offline pjt33
« 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?
Offline cylab

JGO Ninja


Medals: 43



« 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!
Offline 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.
Offline 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.  Tongue

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

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.
Offline pjt33
« 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.
Offline cylab

JGO Ninja


Medals: 43



« 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!
Offline 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.

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

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


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

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(Cool = 2
d(Cool = 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  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CopyableCougar4 (18 views)
2014-08-22 19:31:30

atombrot (29 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (24 views)
2014-08-16 06:12:11

Rayexar (63 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (38 views)
2014-08-06 19:49:38
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!