3 ms·

Once you get the basic Euler setup working it is worth it to try out a more accurate integration method. Anytime someone posts a simulation using Euler Integra

by Simucal 16y ago

Once you get the basic Euler setup working it is worth it to try out a more accurate integration method. Anytime someone posts a simulation using Euler Integration someone usually links to the following[1]. It describes why Euler integration isn't good enough (with the famous line, "If you are use Euler then you are a bloody idiot"). It then proceeds to show how to implement RK4 or Runge Kutta order 4. This method will evaluate the derivative at four points in between the previous and current timestep to detect the curvature of an objects velocity. It will then take a weighted average to get the best approximation of the derivative for that timestep. This accounts for acceleration in between timesteps rather than assuming a constant velocity between them. [1] http://gafferongames.com/game-physics/integration-basics/ http://gafferongames.com/game-physics/integration-basics/

camtarn 16y ago
Fascinating - thanks for the link. I've unknowingly implemented the Euler method in simple games before without knowing its name, since it's the more or less intuitive way to do things - it's quite amusing to see how terrible it can be under some situations.
grogers 16y ago
Yep, and from Runge-Kutta you can get better by switching to variable (and/or independent) step size. Eg. Adaptive Runge-Kutta (variable timestep based on local error estimate from two different orders). Or you can go to predictor-corrector which is pretty interesting as well: http://www.sns.ias.edu/~starlab/kira/ http://www.sns.ias.edu/~starlab/kira/
- teamonkey 16y ago
  Not necessarily better. It reduces the number of calculations per unit time, in some cases. Unfortunately changing the step size dynamically also increases error in the system (because of the way most integrators works). It's a trade-off between CPU time and accuracy.
  - grogers 16y ago
    I'm not sure that's the right way of looking at it. With most numerical simulations, the only thing that matters is the level of accuracy. By changing the accuracy, you change how fast it runs (less accuracy->faster). So for a given level of error tolerance, adaptive step size will typically run faster, because it can use larger steps when able, and smaller steps when required. For fixed time steps you have to stay at the smallest the whole time.
    - teamonkey 16y ago
      With fixed time step for the same level of error you have to stay small, but not as small as you have to sometimes go with variable timestep. In a large-but-simple n-body simulation like this, where every body is integrated at once, variable timestep has to keep the pace of the body that potentially has the most error. With variable timestep, as you add more bodies you end up running at a fairly steady but very slow pace, not only with the slightly slower timestep but also with the added overhead of the error prediction calculations. The solution we used when I was studying this was to group nearby bodies together, and groups could be integrated independently and at different timesteps to each other. To bodies outside the group, the group appeared as a single point mass positioned at the centre of mass of the group.

by Simucal 16y ago

camtarn 16y ago

Fascinating - thanks for the link. I've unknowingly implemented the Euler method in simple games before without knowing its name, since it's the more or less intuitive way to do things - it's quite amusing to see how terrible it can be under some situations.

grogers 16y ago

Yep, and from Runge-Kutta you can get better by switching to variable (and/or independent) step size. Eg. Adaptive Runge-Kutta (variable timestep based on local error estimate from two different orders). Or you can go to predictor-corrector which is pretty interesting as well: http://www.sns.ias.edu/~starlab/kira/ http://www.sns.ias.edu/~starlab/kira/

teamonkey 16y ago
Not necessarily better. It reduces the number of calculations per unit time, in some cases. Unfortunately changing the step size dynamically also increases error in the system (because of the way most integrators works). It's a trade-off between CPU time and accuracy.
- grogers 16y ago
  I'm not sure that's the right way of looking at it. With most numerical simulations, the only thing that matters is the level of accuracy. By changing the accuracy, you change how fast it runs (less accuracy->faster). So for a given level of error tolerance, adaptive step size will typically run faster, because it can use larger steps when able, and smaller steps when required. For fixed time steps you have to stay at the smallest the whole time.
  - teamonkey 16y ago
    With fixed time step for the same level of error you have to stay small, but not as small as you have to sometimes go with variable timestep. In a large-but-simple n-body simulation like this, where every body is integrated at once, variable timestep has to keep the pace of the body that potentially has the most error. With variable timestep, as you add more bodies you end up running at a fairly steady but very slow pace, not only with the slightly slower timestep but also with the added overhead of the error prediction calculations. The solution we used when I was studying this was to group nearby bodies together, and groups could be integrated independently and at different timesteps to each other. To bodies outside the group, the group appeared as a single point mass positioned at the centre of mass of the group.