Top Numerical Integration Schemes for Game Physics

Real-time game physics requires a delicate balance between computational efficiency and physical accuracy, where numerical integration computes an object's position and velocity over discrete time steps. While highly accurate methods like Runge-Kutta 4 exist, they often consume too many CPU cycles and fail to preserve energy over long periods. Conversely, simple methods like Explicit Euler introduce artificial energy that quickly destabilizes simulations. The industry standard instead relies on symplectic integrators—specifically Semi-Implicit Euler and Verlet variants—which offer the optimal trade-off by bounding energy errors over time while requiring minimal computational overhead.

The Energy Conservation vs. Speed Dilemma

In game engines, physics updates are constrained by tight frame budgets (often under 2 to 4 milliseconds). Numerical integrators approximate the differential equations governing motion:

\[\frac{dx}{dt} = v(t), \quad \frac{dv}{dt} = \frac{F(t)}{m}\]

Non-symplectic integrators, such as Explicit (Forward) Euler, fail to conserve phase space volume. As a result, closed-loop systems—like an orbiting body or an undamped spring—continually gain energy, leading to "explosions" where positions and velocities spiral toward infinity. To counteract this, engines must either use smaller timesteps (killing performance) or introduce heavy artificial damping. Symplectic integrators solve this not by eliminating error, but by ensuring that energy errors oscillate within a bounded range over infinite time, preventing runaway instability without sacrificing performance.

1. Semi-Implicit Euler (Symplectic Euler)

Semi-Implicit Euler—also known as Symplectic Euler or Euler-Cromer—is the default workhorse across major commercial engines, including Box2D, Bullet, and NVIDIA PhysX.

  • The Algorithm: It computes the new velocity first using current acceleration, and then uses that updated velocity to determine the new position: \[v_{t+\Delta t} = v_t + a_t \Delta t\] \[x_{t+\Delta t} = x_t + v_{t+\Delta t} \Delta t\]
  • Computational Cost: Negligible. It requires only one force evaluation per update step and a few basic arithmetic operations, identical in cost to Explicit Euler.
  • Energy Conservation: Because the position update depends on the next velocity step, the phase space area is preserved. Energy oscillates around the true analytical value instead of exponentially diverging.
  • Best Used For: General-purpose rigid body dynamics, vehicle systems, and standard gameplay interactions.

2. Velocity Verlet

Velocity Verlet is an algebraically equivalent alternative to the standard Verlet scheme, offering second-order accuracy compared to the first-order accuracy of Semi-Implicit Euler.

  • The Algorithm: It updates position and velocity concurrently, storing positions, velocities, and accelerations: \[x_{t+\Delta t} = x_t + v_t \Delta t + \frac{1}{2} a_t \Delta t^2\] \[v_{t+\Delta t} = v_t + \frac{1}{2} (a_t + a_{t+\Delta t}) \Delta t\]
  • Computational Cost: Extremely low. While it evaluates acceleration twice, the value at \(t + \Delta t\) can be cached and reused as \(a_t\) in the subsequent frame, effectively maintaining a cost of one force evaluation per frame.
  • Energy Conservation: Excellent. It is fully symplectic, time-reversible, and maintains higher trajectory accuracy over Semi-Implicit Euler without a noticeable performance penalty.
  • Best Used For: Molecular dynamics, complex orbital mechanics, and systems requiring high visual fidelity without sacrificing stability.

3. Position-Based Verlet (Verlet Integration)

Standard Verlet integration avoids explicit velocity variables entirely, calculating motion based on current and previous positions: \[x_{t+\Delta t} = 2x_t - x_{t-\Delta t} + a_t \Delta t^2\]

  • Computational Cost: Minimal vector arithmetic per particle.
  • Energy Conservation: Highly stable, self-correcting, and inherently handles constraints through iterative projection without introducing velocity errors.
  • Best Used For: Particle systems, cloth simulation, ropes, and ragdolls (commonly referred to as Position Based Dynamics or PBD).

Why Fourth-Order Runge-Kutta (RK4) is Usually Avoided

RK4 is frequently cited in academic contexts for its high mathematical accuracy (\(O(\Delta t^4)\)). However, it is rarely chosen for general real-time game development for two main reasons:

  1. Computational Overhead: RK4 requires four separate force evaluations per timestep. In scenes with hundreds of rigid bodies, collision queries and constraint solving make four evaluations per frame prohibitively expensive.
  2. Lack of Symplecticity: RK4 is not symplectic. Despite its high short-term precision, it dampens energy over time. For oscillating systems without friction, RK4 will cause orbital decay or spring decay unless explicitly counteracted.

Verdict

For almost all game physics scenarios, Semi-Implicit Euler provides the best overall balance between simplicity, speed, and energy stability for rigid-body simulations. When higher positional accuracy is required for conservative mechanical or celestial systems, Velocity Verlet is the superior choice, delivering second-order accuracy while preserving bounded energy at virtually the same performance cost.