Sign in to follow this  
DingOunan

Why I need the numerical integrator?

Recommended Posts

swiftcoder    18432
Quote:
Original post by DingOunan
If given the velocity and the acceleration,I can immediately get
Distance=1/2 a t^2 + v t
But what happens if the acceleration is constantly varying (i.e. the player is changing direction or speed)? You could get down and dirty with a bunch of calculus, but that could be very complicated (especially if acceleration is not controlled by a known function). Numerical integration is a very simple approach which approximates the (arbitrarily complicated) calculus required for this task.

Share this post


Link to post
Share on other sites
DingOunan    136
Thank you very much for the quick reply.
but,I think about another reason.
because the newtonian dynamic equation contains not only the external forces(applied by user),but also the constraining forces(like the force that attach the mass in a pendulum system)
the constraining force is difficult to calculate,so we use the lagrange dynamic equation,which is not easy to be integrated symboly.then we need the numerical integrator.

Am I right?

Share this post


Link to post
Share on other sites
swiftcoder    18432
Quote:
Original post by DingOunan
because the newtonian dynamic equation contains not only the external forces(applied by user),but also the constraining forces(like the force that attach the mass in a pendulum system) the constraining force is difficult to calculate,so we use the lagrange dynamic equation,which is not easy to be integrated symboly.then we need the numerical integrator.
You are correct, numerical integration can be used anytime we need to approximate a difficult integral.

Share this post


Link to post
Share on other sites
nilkn    960
As an addendum to what swiftcoder said, numerical integration is sometimes necessary because we don't actually know what function is being integrated.

If we're updating the character's position, for example, and the player can apply forces to the character with the keyboard, we can't predict what forces the player will choose to apply. Therefore, we don't know how the acceleration of the character will change with time except at the present moment and any moments in the past where we chose to remember the state of the system.

Share this post


Link to post
Share on other sites
alvaro    21246
Another reason to use numerical integration is that many functions don't have primitives that can be expressed in closed formulas in terms of well-known functions, so analytical integration is not possible.

Share this post


Link to post
Share on other sites
Emergent    982
I like the question. ;-)

The reasons people use numerical integration are that (1) it's easier than solving ODEs, and we are lazy (or would rather do other things), (2) accuracy doesn't matter much in games; it just has to 'look right,' and (3) since we need to know the value of the state every [small timestep] anyway, numerical integration can actually be faster than evaluating a complicated expression (the analytic solution to the differential equation) at all of those points.

But let me play devil's advocate for a second. I would assert that game physics, between collisions, can be evaluated symbolically in most cases. Because most of the time, what are you doing? Rigid body dynamics with collisions, and nothing more. (How often do you see lots of constraint forces in games, besides those that arise from collisions?) And what's more, evaluating the analytic solution to these differential equations is very cheap, so argument (3) above doesn't actually work.

I also disagree with the "unpredictable player input" argument, nilkn (Sorry!). But you see, over any time interval, the player is either hitting a key, or not hitting a key. The way you will probably interpret this -- if you say that keystrokes equate to forces (which I admit they usually don't; usually we just use kinematic models. But those are even simpler) is that over any time interval, the force exerted by the player is a constant. And we know the solution to the ODEs when the input is a constant!!

The only complication comes from handling collisions, but really the way that you do this won't be much different whether you're using analytic solutions or numerical integration. In fact, it might be faster when you use the analytic solution, because whereas when you use numerical integration, often what I've seen people do is use binary search to accurately determine the moment of collision, if you have the analytic solution then you have access to all the derivatives of your state trajectory and can use something that converges faster than binary search, like Newton-Raphson.

Plus, doing things this way will be more accurate, and avoid different-integrator-timestep issues, such as those that plagued Quake3 (players with different framerates could jump different heights. Naturally, you can also solve this problem with a constant physics rate, but this has its own problems).

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by alvaro
Emergent: I think your argument breaks down if you introduce some sort of drag, especially if you have random wind.


True -- if the drag in nonlinear (say, quadratic); otherwise it can be solved easily. Random wind also isn't necessarily a problem (if the ODE is linear), since you end up with a stochastic differential equation, which you can again solve.

But I see where you're going, and I think you're right: The real argument, I suppose, is that numerical integration is more flexible. If I have linear drag and then want to switch to a quadratic drag, I can, easily, if I'm using numerical integration. Whereas if I'm using analytic solutions then everything breaks -- I simply can't (since an analytic solution doesn't exist).

Perhaps the "perfect" way to deal with these things is to abstract away the dynamics, so that to the rest of the code -- collision detection, etc -- it doesn't matter whether what's going on under the hood is numerical integration or the evaluation of analytic expressions (I know this partially contradicts what I said before about Newton-Raphson vs. binary search, but in truth, if you really want to, you can get derivatives out of your numerical integrator). But if you're not going to do that abstraction, then numerical integration is more flexible.

Share this post


Link to post
Share on other sites
nilkn    960
Quote:
Original post by Emergent
But you see, over any time interval, the player is either hitting a key, or not hitting a key. The way you will probably interpret this -- if you say that keystrokes equate to forces (which I admit they usually don't; usually we just use kinematic models. But those are even simpler) is that over any time interval, the force exerted by the player is a constant. And we know the solution to the ODEs when the input is a constant!!


The point I was trying to make is that the ODE you're talking about is itself an approximation that is only valid locally (i.e., it's only valid for that specified time interval where you know exactly which keys are pressed).

Share this post


Link to post
Share on other sites
Raghar    96
Quote:
Original post by DingOunan
If given the velocity and the acceleration,I can immediately get
Distance=1/2 a t^2 + v t

what is the numerical integrator used for?
You are asking wrong question. A programmer invents new algorithms, he is not supposed to try to find a use for a some strange mathematical function, because he is not mathematician.



An integrator is used by people that don't know calculus, and by people who, while they know calculus, prefer simpler methods.

Share this post


Link to post
Share on other sites
swiftcoder    18432
Quote:
Original post by Raghar
A programmer invents new algorithms
Since we appear to be arguing semantics, a programmer writes code - nothing more, nothing less.
Quote:
he is not supposed to try to find a use for a some strange mathematical function, because he is not mathematician.
A computer scientist, on the other hand, is both a programmer and a mathematician, and as such he must spend a great deal of time messing around with 'strange mathematical functions'.

Quote:
An integrator is used by people that don't know calculus, and by people who, while they know calculus, prefer simpler methods.
Or, more commonly, to solve a problem so complex as to either defy an analytical approach or render it too expensive to be calculated in the time allotted.

Share this post


Link to post
Share on other sites
Emergent    982
Quote:
Original post by nilkn
The point I was trying to make is that the ODE you're talking about is itself an approximation that is only valid locally (i.e., it's only valid for that specified time interval where you know exactly which keys are pressed).


It's not an approximation. It is exact. But let me be explicit so we're not talking past each other. Here's an example:

Consider the ODE,

(d^2/dt^2) x = u

where 'u' is the input, and 'x' is the state (in this case a scalar). And for simplicity let's say that you can hit one of two keys, UP or DOWN, so that u can take one of three values:
- UP key pressed <==> u = +1
- DOWN key pressed <==> u = -1
- No key pressed <==> u = 0
[For completeness, I suppose we should also lump "Both UP and DOWN pressed" in with "No key pressed," (as in, "they cancel each other out"), but this isn't terribly important.]

Then, let's say that your input as a function of time is,
       { +1  if  0 <= t < 1
u(t) = { 0 if 1 <= t < 2
{ -1 if 2 <= t < 3

Then the exact solution for x(t), (assuming x(0)=0) is,
       { t^2      if  0 <= t < 1
x(t) = { 1 if 1 <= t < 2
{ 1 - t^2 if 2 <= t < 3

See what I mean? The solution is exact. If you can solve your ODE for a constant input, then you've also solved it for piecewise constant inputs.

Share this post


Link to post
Share on other sites
Raghar    96
Quote:
Original post by swiftcoder
Quote:
Original post by Raghar
A programmer invents new algorithms
Since we appear to be arguing semantics, a programmer writes code - nothing more, nothing less.

A programmer is supposed to create a program, if he would be unable to create a new algorithm, he'd be unable to do his work. The term programmer is also used by SW engineers as a non arrogant description of theirs capabilities. What you described is code monkey, or coder.

My point was a programmer (SW engineer, computer "scientist" with ability to create a working program) isn't seeking a use for an algorithm, or math equation, he is creating/modifying algorithms that are relevant to his code.

While history knows situations where an author of an algorithm desperately tried to find at least some use for his algorithm, majority of reliable programs were created by people who threw part of design specifications out of window, and rather created theirs own solutions.

Quote:
Quote:
he is not supposed to try to find a use for a some strange mathematical function, because he is not mathematician.
A computer scientist, on the other hand, is both a programmer and a mathematician, and as such he must spend a great deal of time messing around with 'strange mathematical functions'.
Wow, I'd call that pink glasses. It reminded me of Peter Molyneux's speeches. In the real world, a common computer scientist ends in the strange world of string manipulations. ~_^

Quote:
Quote:
An integrator is used by people that don't know calculus, and by people who, while they know calculus, prefer simpler methods.
Or, more commonly, to solve a problem so complex as to either defy an analytical approach or render it too expensive to be calculated in the time allotted.
How is that different from "prefer simpler methods?



Back to topic.

While few first terms of the Taylor series can be used as an approximation (and sometimes they work well), there is also problem called frame lag. A player don't see what happens now, he sees what happened while ago.

D = v0 + a/2 works, but D = v0 + a works better. The whole system responds more readily, and feels more snappy. There are also pesky problems with limited accuracy on computers, which in better situations only lose energy, in worst situation they make the whole system explode. Integrator offers greater flexibility than analytic solution. Is system gaining energy? Add limiter to that small part where it matters. Is system losing energy? Bump it up, or bias integrating function a little. Analytic solutions are more pesky to work with.

Share this post


Link to post
Share on other sites
swiftcoder    18432
Quote:
Original post by Raghar
...
Fair enough. However, when I go to sort a list of integers, I find an existing sorting method which has been proven by someone else. If I develop an entirely new algorithm, then the onus is on me to provide a proof (in the mathematical sense), that my algorithm functions as advertised - thus to create a new algorithm I must wield at least some portion of the mathematician's skill.

Quote:
Quote:
Quote:
An integrator is used by people that don't know calculus, and by people who, while they know calculus, prefer simpler methods.
Or, more commonly, to solve a problem so complex as to either defy an analytical approach or render it too expensive to be calculated in the time allotted.
How is that different from "prefer simpler methods?
I took mild offence at your implication that the only reason to use numerical integration is a lack of facility with mathematics.

Share this post


Link to post
Share on other sites
nilkn    960
Quote:
Original post by Emergent
Quote:
Original post by nilkn
The point I was trying to make is that the ODE you're talking about is itself an approximation that is only valid locally (i.e., it's only valid for that specified time interval where you know exactly which keys are pressed).


It's not an approximation. It is exact. But let me be explicit so we're not talking past each other. Here's an example:

Consider the ODE,

(d^2/dt^2) x = u

where 'u' is the input, and 'x' is the state (in this case a scalar). And for simplicity let's say that you can hit one of two keys, UP or DOWN, so that u can take one of three values:
- UP key pressed <==> u = +1
- DOWN key pressed <==> u = -1
- No key pressed <==> u = 0
[For completeness, I suppose we should also lump "Both UP and DOWN pressed" in with "No key pressed," (as in, "they cancel each other out"), but this isn't terribly important.]

Then, let's say that your input as a function of time is,
       { +1  if  0 <= t < 1
u(t) = { 0 if 1 <= t < 2
{ -1 if 2 <= t < 3

Then the exact solution for x(t), (assuming x(0)=0) is,
       { t^2      if  0 <= t < 1
x(t) = { 1 if 1 <= t < 2
{ 1 - t^2 if 2 <= t < 3

See what I mean? The solution is exact. If you can solve your ODE for a constant input, then you've also solved it for piecewise constant inputs.


Ah, I see much more clearly what you mean now.

You present a convincing argument, so I stand corrected. [smile]

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