Fixed time-step implementation in Box2D | UNAgames

http://www.unagames.com/blog/daniele/2010/06/fixed-time-step-implementation-box2d

Fixed time-step implementation in Box2D

If you are interested in how to implement Glenn Fiedler's "fix your timestep" technique, here you will find a brief C++ implementation for Box2D. The technique is needed to keep stable the numerical integration performed by the physics simulation while running the video game with a variable frame-rate.

As Glenn's article has all the details, read it to understand because this technique is useful and because this solution works.

The implementation makes these assumptions:

  • forces are applied for the whole frame, and are preserved for each sub-step (i.e., multiple calls to b2World::Step());
  • to implement low-level physics behaviors (like buoyancy, wind drag, etc.) for which numerical stability must be guaranteed, Physics Controllers are used: special objects that are executed at each sub-step applying impulses to controlled objects;
  • at each sub-step some game logic could be called (e.g. to manage collisions).

Initialization

const float FIXED_TIMESTEP = 1.f / 60.f;
 
 
 
PhysicsSystem::PhysicsSystem ()
	: fixedTimestepAccumulator_ (0),
	  fixedTimestepAccumulatorRatio_ (0)
{
	// ...
 
	world_ = new b2World (gravity, doSleep);
	world_->SetAutoClearForces (false);
 
	// ...
}

In PhysicsSystem's constructor we build the b2World instance. The call to SetAutoClearForces() method inhibits the automatic reset of forces when calling b2World::Step(). We also initialize two auxiliary member variables that will be used to manage the fixed time-step algorithm: fixedTimestepAccumulator_ will contain the elapsed time still left un-processed, fixedTimestepAccumulatorRatio_ is the previous value scaled in the range [0, 1) (it will be used to smooth movements).

Fixed time-step update

The update method uses the following parameters:

  • FIXED_TIMESTEP: the fixed time-step value that will be always passed to b2World::Step().
  • MAX_STEPS: an upper-bound value used to avoid a "spiral of death": the game slows-down, the physics system must processes a longer "frame" performing multiple sub-steps, but this requires more time that will slows-down further the game, and so on until the game will become unresponsive. If the game will need more sub-steps than MAX_STEPS, it will simply progress slowly until the scene becomes simpler and the normal behavior will be restored.
void PhysicsSystem::update (float dt)
{
	// Maximum number of steps, to avoid degrading to an halt.
	const int MAX_STEPS = 5;
 
	fixedTimestepAccumulator_ += dt;
	const int nSteps = static_cast<int> (
		std::floor (fixedTimestepAccumulator_ / FIXED_TIMESTEP)
	);
	// To avoid rounding errors, touches fixedTimestepAccumulator_ only
	// if needed.
	if (nSteps > 0)
	{
		fixedTimestepAccumulator_ -= nSteps * FIXED_TIMESTEP;
	}
 
	assert (
		"Accumulator must have a value lesser than the fixed time step" &&
		fixedTimestepAccumulator_ < FIXED_TIMESTEP + FLT_EPSILON
	);
	fixedTimestepAccumulatorRatio_ = fixedTimestepAccumulator_ / FIXED_TIMESTEP;
 
	// This is similar to clamp "dt":
	//	dt = std::min (dt, MAX_STEPS * FIXED_TIMESTEP)
	// but it allows above calculations of fixedTimestepAccumulator_ and
	// fixedTimestepAccumulatorRatio_ to remain unchanged.
	const int nStepsClamped = std::min (nSteps, MAX_STEPS);
	for (int i = 0; i < nStepsClamped; ++ i)
	{
		// In singleStep_() the CollisionManager could fire custom
		// callbacks that uses the smoothed states. So we must be sure
		// to reset them correctly before firing the callbacks.
		resetSmoothStates_ ();
		singleStep_ (FIXED_TIMESTEP);
	}
 
	world_->ClearForces ();
 
	// We "smooth" positions and orientations using
	// fixedTimestepAccumulatorRatio_ (alpha).
	smoothStates_ ();
}

The algorithm is simple:

  1. using the requested time to consume (input parameter dt) and the previous, unprocessed accumulated time (fixedTimestepAccumulator_), computes the natural number of steps, each of length FIXED_TIMESTEP, that must be simulated; the remainder is stored back in the accumulator (fixedTimestepAccumulator_).
  2. computes the fraction of unprocessed time, respect to FIXED_TIMESTEP, and stores it into fixedTimestepAccumulatorRatio_.
  3. simulates the required number of physics steps.
  4. calls b2World::ClearForces() method to reset applied forces.
  5. smooths positions and orientations of physics objects.

Each single step activates the Physics Controllers, calls b2World::Step() and processes collisions:

void PhysicsSystem::singleStep_ (float dt)
{
	// ...
 
	updateControllers_ (dt);
	world_->Step (dt, velocityIterations, positionIterations);
	consumeContacts_ ();
 
	// ...
}

resetSmoothStates_() and smoothStates_() methods depend on the chosen smoothing algorithm, and are described below.

Smoothing

Smoothing is very important to avoid visual artifacts: due to the variable frame rate, fast moving objects will "flicker" on screen (each time the accumulator is full, additional steps will be performed moving objects apparently "faster"); if running in "slow-motion", objects position will "jump" each time the accumulated virtual time exceeds FIXED_TIMESTEP (as multiple frames are executed without any physics computations).

You can choose between two implementations:

  • interpolation: the smoothed state is computed from the last two known states:
    	state = currentState * alpha + previousState * (1-alpha)

    It's accurate because it always smooths between two computed states; but lags one sub-step (i.e. one FIXED_TIMESTEP; because alpha < 1, currentState is never returned), needs double buffering of smoothed states, "events" (if not cached) will be "anticipated" of one sub-step (they are triggered when computing currentState).
  • extrapolation: the smoothed state is predicted using the last known state and its first derivative:
    	state = currentState + currentStateDerivative * alpha

    It's very efficient to compute; but it will deviate from the real "next" state producing "jumps" when the new state becomes the active one.

You can see the two main problems (interpolation lag and extrapolation error) in the following figure, that shows how an object position is smoothed with the two methods.

Interpolation and extrapolation of features.

In the following, PhysicsComponent is a wrapper class for b2Body objects; used to decouple the game code from all the details of this article.

Extrapolation

I will start with extrapolation because its implementation is easier.

Note that extrapolation is the exact same thing that Dead Reckoning (read also Jesse Aronson's article "Dead Reckoning: Latency Hiding for Networked Games"), and it can become a very complex argument. But if you need a better solution, as we play with very little latency, you can simply use the interpolation technique (see later).

For each smoothed state, PhysicsComponent has one member variable: for the position is used smoothedPosition_, for the orientation is used smoothedAngle_.

void PhysicsSystem::smoothStates_ ()
{
	const float dt = fixedTimestepAccumulatorRatio_ * FIXED_TIMESTEP;
 
	for (b2Body * b = world_->GetBodyList (); b != NULL; b = b->GetNext ())
	{
		if (b->GetType () == b2_staticBody)
		{
			continue;
		}
 
		PhysicsComponent & c = PhysicsComponent::b2BodyToPhysicsComponent (* b);
		c.smoothedPosition_ = b->GetPosition () + dt * b->GetLinearVelocity ();
		c.smoothedAngle_ = b->GetAngle () + dt * b->GetAngularVelocity ();
	}
}
 
 
 
void PhysicsSystem::resetSmoothStates_ ()
{
	for (b2Body * b = world_->GetBodyList (); b != NULL; b = b->GetNext ())
	{
		if (b->GetType () == b2_staticBody)
		{
			continue;
		}
 
		PhysicsComponent & c = PhysicsComponent::b2BodyToPhysicsComponent (* b);
		c.smoothedPosition_ = b->GetPosition ();
		c.smoothedAngle_ = b->GetAngle ();
	}
}

Interpolation

Interpolation should be the preferred smoothing implementation.

For each smoothed state, PhysicsComponent has one further member variable to store the previous known state: for the position is used previousPosition_, for the orientation is used previousAngle_.

void PhysicsSystem::smoothStates_ ()
{
	const float oneMinusRatio = 1.f - fixedTimestepAccumulatorRatio_;
 
	for (b2Body * b = world_->GetBodyList (); b != NULL; b = b->GetNext ())
	{
		if (b->GetType () == b2_staticBody)
		{
			continue;
		}
 
		PhysicsComponent & c = PhysicsComponent::b2BodyToPhysicsComponent (* b);
		c.smoothedPosition_ =
			fixedTimestepAccumulatorRatio_ * b->GetPosition () +
			oneMinusRatio * c.previousPosition_;
		c.smoothedAngle_ =
			fixedTimestepAccumulatorRatio_ * b->GetAngle () +
			oneMinusRatio * c.previousAngle_;
	}
}
 
 
 
void PhysicsSystem::resetSmoothStates_ ()
{
	for (b2Body * b = world_->GetBodyList (); b != NULL; b = b->GetNext ())
	{
		if (b->GetType () == b2_staticBody)
		{
			continue;
		}
 
		PhysicsComponent & c = PhysicsComponent::b2BodyToPhysicsComponent (* b);
		c.smoothedPosition_ = c.previousPosition_ = b->GetPosition ();
		c.smoothedAngle_ = c.previousAngle_ = b->GetAngle ();
	}
}