Sign in to follow this  
kylecrass

Help with acceleration

Recommended Posts

Hi! Okay I have been working on my game for awhile and its been nmissing something crucial, acceleration. The game would be fine if it were just characters moving around, but i am making a sci-fi game that uses space ships, and they need to model acceleration My collision detection system uses delta t and velocity vectors atm, first off if i use acceleration will i have to modify existing collision routine? Now, how do i implement acceleration? I am at a loss I thought i would do this: speed = speed + (delta t) * acceleration but that does not seem to work...am i missing something?

Share this post


Link to post
Share on other sites
1. use a force and a mass on your spaceship. Say like force 10, mass 2 => accel 10/2 =5 or with the same force but with a bigger mass like 5 you only get accelation to 2. The bigger the ship the slower the acceleration.

2.
speed = speed + (delta t) * acceleration

this seems correct. Do you remember that accelaration and speed is a vector. And did you also do position = position + speed * (delta t) to get the new position. Position is also a vector.

Share this post


Link to post
Share on other sites
Quote:
Original post by kylecrass
I thought i would do this:

speed = speed + (delta t) * acceleration

but that does not seem to work...am i missing something?


This would work all right (assuming of course you're doing the same to find position from speed, as Zyberant suggested), it is -in fact- numerical integration, but this one (euler's method) is prone to some problems and it's not that accurate for more advanced simulations.

Make sure to use a constant, small enough timestep. Else you'll get jittering objects and the time will not be uniform... I suggest you do sth like this:

void SimulationHeartBeat()
{

1. const float dt = 1.f/60.f; (max)
2. unprocessed_time += (time - last_update_time);
3. while( unprocessed_time > dt )
{
4. update_simulation_objects();
5. unprocessed_time -= dt;
}
6. last_update_time = time;
}


This will make sure that the required number of simulations will have been performed, anytime...

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
... but this one (euler's method) is prone to some problems and it's not that accurate for more advanced simulations.

What I coincident! I have just released a demo showing the differerence in accurucy between the Euler integration and the more sophisticated 4th order Runge-Kutta integration (aka RK4).

Check out the thread RK4 vs Euler integration (for physics in games) demo, GPL:ed C#/MDX app to get more information. Spoiler: Euler integration sucks for non trivial games.

[Edited by - Enselic on March 12, 2006 5:56:18 AM]

Share this post


Link to post
Share on other sites
Well, to start with theory, Euler's method is a 2nd order method while the spcific RK is 4th order. This means that the cutoff error from the entire Taylor expansion is -in 1st case- of the order of magintude of dt3, while in the RK it reduces to order of dt5. (!)

Euler's method introduces severe errors especially with integrands that have quite large (and quite often) maximum values of second derivative (like stiff spring forces). This quantity can be considered a measure of how fast the rate of change of the integrand is, and affects immediately the stability of Euler's method since it controls how much of the function's curve may end up completely missed/ignored by the method...

However, don't rush to deem it useless. Considering the CPU overhead in both cases, many would opt for Euler instead, especially in games where maximum possible precision isn't *that* necessary...

Share this post


Link to post
Share on other sites
Well, I would also like to use jerk in my simulation, the third order derivative of velocity right?

v = dp / dt
a = dv / dt
j = da / dt

so, if i use the formula of f(x) = xi + vi * (x) + [a * (x)²] / 2

implementing jerk would expand the equation to this right? (Using integration)

f(x) = xi + vi * (x) + [a * (x)²] / 2 + [j * (x)³] / 6

if so, then i would do this if using a time step right?

a += j * dt
v += a * dt
p += v * dt

am i right?

Also, If I am using jerk, (or even if not), if delta t can fluctuate, how badly will it mess up my simulation? Obviously if delta time is 1 second, it will be very off course, will jerk make the error more pronounce using the euler method? I mean, I know if delta t was ideal it would be the limit as it approches 0 :P But in this particular situation I will never get delta t below 1/120th a second and delta t will never go above 1 second.

Share this post


Link to post
Share on other sites
f(x) = xi + vi * (x) + [a * (x)²] / 2
f(x) = xi + vi * (x) + [a * (x)²] / 2 + [j * (x)³] / 6

isn't it f(t). t instead of x. You use time to get the position.

Also this is the exact method. Given some start condition and the time, you get the exact position. The delta time is another method.

If the start condition change with the time then i don't think you can use the exact method then. This is where the delta time method come in.

Share this post


Link to post
Share on other sites
@Kylecrass
If you've figured out an (independent) way to calculate the derivative of the acceleration, and then calculate all other quantities (acceleration, velocity, position) from it, then theoretically, yes, you would have better accuracy. You would have limited the cutoff error by a whole order of magnitude!
This is theoretical though; I don't know whether the extra integration will cost any precision loss, but it should be better.
Notice though, that you'll have to come up with a way to calculate the derivative of acceleration first.
I mean, don't do something like that: (It's not gonna make a difference!)

1. prevAcc = a;
2. a = (total F)/mass;
3. v+= a*dt;
4. x += v*dt + (1/2)*a*dt2 + (1/6)*((a-prevAcc)/dt)*dt3



@Zyberant
Quote:

isn't it f(t). t instead of x. You use time to get the position.

Also this is the exact method. Given some start condition and the time, you get the exact position. The delta time is another method

You can use anything to get position, so long as it is expressed with respect to that quantity. Of course, its derivatives wouldn't be -then- velocity and acceleration, but it is perfectly legal...
The Taylor series expansion of a function, around any point x0 of its domain, is:
f(x) = f(x0) + (x-x0)*f'(x0) + (x-x0)2*f"(x0)/2 + ... + (x-x0)n*f(n)(x0)/n!

If "x" was time "t" instead, then substituting t=t0+dt in the formula, yields:
f(t0+dt) = f(t0) + dt*f'(t0) + dt2*f"(t0)/2 + dt3*f(3)(t0)/3! + ...

Therefore, the "dt" formula is the very same thing.
(You meant this one, didn't you?)

Share this post


Link to post
Share on other sites
sweet yeah I was thinking of that exact extra derivation


//ForcesApplied would be a list of forces, applied to an object
totalforcevector = Sum(ForcesApplied)

jerkvector = totalforcevector / mass

accelerationvector += (jerkvector * dt);
velocityvector += (acceleration * dt)
posvector += (velocityvector * dt);

This method should theoretically give me better precision?

I can use the extra processing in my game cuz its going to be used in one of those fancy new games coming up ;)

I have taken calc, quite a few classes actually....but the sad ting is they hadn't gone into much detail about this :(

Share this post


Link to post
Share on other sites
Quote:

This method should theoretically give me better precision?

I really doubt you can tweak the Euler method to get any better precision. The only way is to decrease the timestep, and it doesn't come cheap.

If you really need precision, I suggest you should turn to another integration method like Verlet or RK4, especially if you'll be dealing with springs and constraints.
Verlet is still 2nd order, however it calculates position without using any velocity, thus restricting the error to a minimum. Constraints are also very easy to implement with verlet.

RK on the other hand, is far more accurate, because it uses an estimated "average" value of the derivative throught the timestep, but be prepared to pay the price in cpu overhead.

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
Quote:

This method should theoretically give me better precision?

Verlet is still 2nd order... <snip>


Verlet is the same order as RK4.

Share this post


Link to post
Share on other sites
Quote:
Original post by jjd
Quote:
Original post by someusername
Quote:

This method should theoretically give me better precision?

Verlet is still 2nd order... <snip>


Verlet is the same order as RK4.

According to http://en.wikipedia.org/wiki/Verlet, verlet is third order.

Besides, Verlet is not particularily good when acceleration isn't constant, is it? I recall reading some article somewhere about that.

Share this post


Link to post
Share on other sites
Quote:

Origin post by kylecrass
i was wondering though, would the sum of forces, divided by the objects mass, times delta t, plus previous acceleration, is that the correct way to calculate acceleration ?

No. Total force divided by mass *is* current instantaneous acceleration.
If you want to keep that "euler integration" formula, what you say would be correct if you didn't use the sum of forces directly, but the sum of their derivatives (the derivative of the total force)


Quote:

Original post by jjd
Verlet is the same order as RK4.

Well, that's the exact text I had read in wikipedia:
Quote:

If we consider the global error in position between x(t) and x(t + T), where T = nΔt, it is clear that:

And therefore, the global (cumulative) error over a constant interval of time is given by:

Because the velocity is determined in a non-cumulative way from the positions in the Verlet integrator, the global error in velocity is also O(Δt2).

In molecular dynamics simulations, the global error is typically far more important than the local error, and the Verlet integrator is therefore known as a second-order integrator.


The word "third" only appears once, in a sentence explaining how the third order terms -of two different Taylor series- cancel out, thus providing greater accuracy than typical integration with Taylor series

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
Quote:

Origin post by kylecrass
i was wondering though, would the sum of forces, divided by the objects mass, times delta t, plus previous acceleration, is that the correct way to calculate acceleration ?

No. Total force divided by mass *is* current instantaneous acceleration.
If you want to keep that "euler integration" formula, what you say would be correct if you didn't use the sum of forces directly, but the sum of their derivatives (the derivative of the total force)


Quote:

Original post by jjd
Verlet is the same order as RK4.

Well, that's the exact text I had read in wikipedia:
Quote:

If we consider the global error in position between x(t) and x(t + T), where T = nΔt, it is clear that:

And therefore, the global (cumulative) error over a constant interval of time is given by:

Because the velocity is determined in a non-cumulative way from the positions in the Verlet integrator, the global error in velocity is also O(Δt2).

In molecular dynamics simulations, the global error is typically far more important than the local error, and the Verlet integrator is therefore known as a second-order integrator.


The word "third" only appears once, in a sentence explaining how the third order terms -of two different Taylor series- cancel out, thus providing greater accuracy than typical integration with Taylor series


The order of a method usually refers to the truncation of the Taylor series. Verlet is 4th order in the displacement, which is the variable you are solving for. This is the same order as RK4. Calculating the velocity from the displacements obtained using Verlet is not very accurate, and the results are 2nd order. The Verlet integrator is not generally known as a 2nd order integrator (unless specifically stated with reference to velocity) in the molecular dynamics community, see Dennis Rapaports "The art of molecular dynamics" as an alternative to Wikipedia.

Quote:
Original post by Enselic
According to http://en.wikipedia.org/wiki/Verlet, verlet is third order.

Besides, Verlet is not particularily good when acceleration isn't constant, is it? I recall reading some article somewhere about that.

It is definitely not 3rd order.

You are probably referring to Lonesock's article, which is also posted here on Gamedev.net. It is wrong. There is absolutely no need to assume that acceleration is constant.

Share this post


Link to post
Share on other sites
Oh, I got it now. I was confused that in the derivation of Verlet Taylor polynoms of order 3 were used. However, since two of them are used, I guess you get better accurucy. It is mentioned below:
Quote:

This offers the clear advantage that the third-order term from the Taylor expansion cancels out, thus making the Verlet integrator an order more accurate than integration by simple Taylor expansion alone.

Share this post


Link to post
Share on other sites
Well, I don't know if there's anything wrong with my implementation of verlet, but it always yields the very same result as simple euler. They are -almost always- identical up to the 4th/5th decimal digit, no matter how small or large the actual value they should converge to...

I've never had to use anything other than euler, I had just setup a small app to test various integration methods, and verlet seemed to -pretty much- suck just as bad as euler!

typedef double real;

// *** EULER ***
v = v0;
p = p0;
a = ((real)0);
// start at t=t1
for( t = timestep; t<=duration; t+= timestep )
{
p += v*timestep;

a = acc(t);
v += a*timestep;
}
real EulerPos = p;
real EulerVel = v;


// *** VERLET ***
real secondlastPos = p0; // position at t0
real lastPos = p0 + v0*timestep;// position at t1
a = acc(timestep); // acceleration at t1
real lastVel = 0;

// start at t=t2
for( t = ((real)2)*timestep; t<=duration; t+=timestep )
{
p = ((real)2)*lastPos - secondlastPos + a*timestep*timestep;
lastVel = (p-secondlastPos)/(((real)2)*tstep) + a*timestep;
a = acc(t);


secondlastPos = lastPos;
lastPos = p;
}
real VerletPos = p;
real VerletVel = lastVel + a*timestep;




For a 5sec long simulation at 60Hz, integrating non-problematic functions of acceleration (like c/(t+1) for t>0), I would get an average error of 1.5% on position and .5% on velocity with both! (The RK2 and RK4 were at .0001% and .00003% respectively!)

When integrating relatively fast oscillating sinusoidals (like sin(c1*t+phase1)*cos(c2*t+phase2) ), for the same simulated duration, the average error of euler and verlet -in position- turned out at ~15%, when RK2 and RK4 where at .15% and .002% respectively.

Naturally, I tried using different timesteps and see how the simulated duration affected the errors... I believe I've tested a satisfactory number of cases/parameters... The results seemed quite reasonable...
And -of course- the errors were calculated from analytical formulas. (symbolic integration of acceleration)

It strikes me surprisingly; assuming my verlet is ok, is it possible that a 4th order method is *sooo* way off, compared to other 4th order methods? I should stick to my modified euler then! :)

Share this post


Link to post
Share on other sites
Well, that is odd. The code (although ugly [wink]) looks like it should do the job. However, I'm unclear what acc() is; Is it the function you described in the text? If so, you might want to consider your initial conditions on Verlet. You are using an Euler approximation to start Verlet. This can affect the overall error more or less depending upon the forcing function. This highlights one of the disadvantages of Verlet: it is a multistep method and that can be an issue when it comes to starting it up. I'd be interested to see if using the analytic solution for the t1 step ameliorates the discrepancy you observe.

[Edit] I've been meaning to put together a demo using Verlet for a while, so I'll try to do that tonight to see if I get the same results uisng your forcing function.

Share this post


Link to post
Share on other sites
Well, yes, the code is very ugly! Sorry about that... I had written it within another app(!) in like half an hour, and -naturally- it wasn't intended to be seen by anyone. :)
I just searched/replaced some of the variables' names into something more comprehensible...

The function acc(t) returns a value for the acceleration at time 't' from an analytical formula.

Quote:

You are using an Euler approximation to start Verlet. This can affect the overall error more or less depending upon the forcing function. This highlights one of the disadvantages of Verlet: it is a multistep method and that can be an issue when it comes to starting it up.

[/quote]
Hmm, indeed.. I suppose this was the right way to get it going...

Quote:

I'd be interested to see if using the analytic solution for the t1 step ameliorates the discrepancy you observe.

You mean finding the initial positions from the analytical solution for position... I'll give that a shot...

Share this post


Link to post
Share on other sites
Well, I tried it...
Instead of calculating the position at t1 from p1 = p0 + v0*dt, I'm now calculating it from the analytical formula... The error is now reduced by at least 2/3!
I also adjusted the calculation of the final velocity (which also involved euler) and the error -in velocity- is reduced to the half...
It seems that the error in initial conditions would propagate (if not escalate) throughout the entire integration...

The error still seems a little too high for a 4th order method, but at least it's not identical to euler anymore!

It's obvious that different initial conditions will lead to the solution for a different problem, but what is the correct way to start up a verlet?

I mean, I tried to use initial conditions as close as possible to the actual functions I was approximating, and you saw how much error accumulated...
What good would it be if I had just chosen to use the same values for the initial "lastPos" and "secondlastPos", presumably with zero velocity at t==0?

How do you start the damn thing? :)

Share this post


Link to post
Share on other sites
There is no "right" way, unless you use the analytic solution... of course, you normally won't have that available, unlike in testing. The Euler step is probably the most common approach. You could even use some kind of RK step if you wanted better accuracy. However, Euler is generally sufficient for a lot of simulations (even molecular dynamics). One of the best things about Verlet is that it is pretty stable and fast. For game programming that is often enough. In molecular dynamics the long simulations times usually mean that global accuracy is out the window anyway, so the long term stability is the main attraction there as well.

The need for accuracy is low in game programs, so it is not something to fret about. If you want accruacy, my first choice for most problems is Runge-Kutta-Fehlberg 4th order (Dormand-Prince coeffs) with adaptive stepping.

Share this post


Link to post
Share on other sites
I see... Well, verlet made an impression on me because I was expecting it to be far more accurate. I didn't expect the initial conditions to affect the result at that extent...
I'm not planning on solving any ODEs (apart from the usual scheme in simple games), I just wanted a "first hand" experience, so I can have an opinion about these... It seems I was a little mislead with verlet...

For the most simple purposes, I prefer to use a custom euler implementation, which is far more accurate (more than 60-70%) than the regular one. Instead of approximating the area under the curve of acceleration by adding rectangles of area==dt*a(ti), I add trapezoids with area==.5*dt*(a(ti)+a(ti-1)).
The velocity is known for the previous timestep only (like verlet), but considering the speed and improved accuracy (with respect to simple forward euler), it has become my favourite for quite some time now...

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
I see... Well, verlet made an impression on me because I was expecting it to be far more accurate. I didn't expect the initial conditions to affect the result at that extent...
I'm not planning on solving any ODEs (apart from the usual scheme in simple games), I just wanted a "first hand" experience, so I can have an opinion about these... It seems I was a little mislead with verlet...


I still think Verlet should be performing on par with RK4 since your forcing function is smooth, however, I'm not 100% sure so I want to check it out when I get home tonight.

One last note, Verlet will be superior to RK4 if the system is Hamiltonian. Verlet will always stay close to the solution of a Hamiltonian system, unlike most other integrators. That is probably not too important for most of our applications, but you never know when these little facts will become useful [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by jjd
One last note, Verlet will be superior to RK4 if the system is Hamiltonian. Verlet will always stay close to the solution of a Hamiltonian system, unlike most other integrators.


I'm gonna have to look up the definition for that one... :) Thanks though.
Keep me posted if you get to try this afterall.

Share this post


Link to post
Share on other sites
Quote:
Original post by jjd
Verlet will always stay close to the solution of a Hamiltonian system, unlike most other integrators. That is probably not too important for most of our applications, but you never know when these little facts will become useful [smile]


From the little I've managed to read so far, what you say makes sense, because verlet calculates position only from position and acceleration (no velocity). Since velocities (which introduce error O(dt^2) in verlet) cannot affect accelerations in such a system, it seems that the solution of verlet will generally be more stable.

But then again I may be totally wrong!

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