Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Gaffer on games timestep: std::chrono implementation

If you're not familiar with the Gaffer on Games article "Fix your Timestep", you can find it here: https://gafferongames.com/post/fix_your_timestep/

I'm building a game engine, and in an effort to get more comfortable with std::chrono I've been trying to implement a fixed time step using std::chrono for.. a couple of days now and I can't seem to wrap my head around it. Here is the pseudo-code I'm working towards:

double t = 0.0;
double dt = 0.01;

double currentTime = hires_time_in_seconds();
double accumulator = 0.0;

State previous;
State current;

while ( !quit )
{
    double newTime = time();
    double frameTime = newTime - currentTime;
    if ( frameTime > 0.25 )
        frameTime = 0.25;
    currentTime = newTime;

    accumulator += frameTime;

    while ( accumulator >= dt )
    {
        previousState = currentState;
        integrate( currentState, t, dt );
        t += dt;
        accumulator -= dt;
    }

    const double alpha = accumulator / dt;

    State state = currentState * alpha + 
        previousState * ( 1.0 - alpha );

    render( state );
}

Goals:

  • I don't want rendering to be frame-rate bound. I should render in the busy loop
  • I want a fully fixed time-step where I call my update function with a float delta time
  • No sleeps

My current attempt (semi-fixed):

#include <algorithm>
#include <chrono>
#include <SDL.h>

namespace {
    using frame_period = std::chrono::duration<long long, std::ratio<1, 60>>;
    const float s_desiredFrameRate = 60.0f;
    const float s_msPerSecond = 1000;
    const float s_desiredFrameTime = s_msPerSecond / s_desiredFrameRate;
    const int s_maxUpdateSteps = 6;
    const float s_maxDeltaTime = 1.0f;
}


auto framePrev = std::chrono::high_resolution_clock::now();
auto frameCurrent = framePrev;

auto frameDiff = frameCurrent - framePrev;
float previousTicks = SDL_GetTicks();
while (m_mainWindow->IsOpen())
{

    float newTicks = SDL_GetTicks();
    float frameTime = newTicks - previousTicks;
    previousTicks = newTicks;

    // 32 ms in a frame would cause this to be .5, 16ms would be 1.0
    float totalDeltaTime = frameTime / s_desiredFrameTime;

    // Don't execute anything below
    while (frameDiff < frame_period{ 1 })
    {
        frameCurrent = std::chrono::high_resolution_clock::now();
        frameDiff = frameCurrent - framePrev;
    }

    using hr_duration = std::chrono::high_resolution_clock::duration;
    framePrev = std::chrono::time_point_cast<hr_duration>(framePrev + frame_period{ 1 });
    frameDiff = frameCurrent - framePrev;

    // Time step
    int i = 0;
    while (totalDeltaTime > 0.0f && i < s_maxUpdateSteps)
    {
        float deltaTime = std::min(totalDeltaTime, s_maxDeltaTime);
        m_gameController->Update(deltaTime);
        totalDeltaTime -= deltaTime;
        i++;
    }

    // ProcessCallbackQueue();
    // ProcessSDLEvents();
    // m_renderEngine->Render();
}

Problems with this implementation

  • Rendering, handling input, etc is tied to the frame rate
  • I'm using SDL_GetTicks() instead of std::chrono

My actual question

  • How can I replace SDL_GetTicks() with std::chrono::high_resolution_clock::now()? It seems like no matter what I need to use count() but I read from Howard Hinnant himself this quote:

If you use count(), and/or you have conversion factors in your chrono code, then you're trying too hard. So I thought maybe there was a more intuitive way.

  • How can I replace all the floats with actual std::chrono_literal time values except for the end where I get the float deltaTime to pass into the update function as a modifier for the simulation?
like image 229
Josh Sanders Avatar asked Dec 22 '19 04:12

Josh Sanders


1 Answers

Below I implement a couple of different versions of "final touch" from Fix your Timestep using <chrono>. My hope is that this example will translate to your desired code.

The main challenge is figuring out what unit each double represents in Fix your Timestep. Once that is done, the transformation to <chrono> is fairly mechanical.

Front matter

So that we can easily change out the clock, start with a Clock type, for example:

using Clock = std::chrono::steady_clock;

Later I'll show that one can even have Clock be implemented in terms of SDL_GetTicks() if desired.

If you have control over the signature of the integrate function, I recommend double-based seconds units for the time parameters:

void
integrate(State& state,
          std::chrono::time_point<Clock, std::chrono::duration<double>>,
          std::chrono::duration<double> dt);

This will allow you to pass anything you want in (as long the time_point is based on Clock), and not have to worry about explicit casting to the correct units. Plus physics computations are often done in floating point, so this lends itself to that as well. For example if State simply holds an acceleration and a velocity:

struct State
{
    double acceleration = 1;  // m/s^2
    double velocity = 0;  // m/s
};

and integrate is supposed to compute the new velocity:

void
integrate(State& state,
          std::chrono::time_point<Clock, std::chrono::duration<double>>,
          std::chrono::duration<double> dt)
{
    using namespace std::literals;
    state.velocity += state.acceleration * dt/1s;
};

The expression dt/1s simply converts the double-based chrono seconds into a double so it can participate in the physics computation.

std::literals and 1s are C++14. If you are stuck at C++11, you can replace these with seconds{1}.

Version 1

using namespace std::literals;
auto constexpr dt = 1.0s/60.;
using duration = std::chrono::duration<double>;
using time_point = std::chrono::time_point<Clock, duration>;

time_point t{};

time_point currentTime = Clock::now();
duration accumulator = 0s;

State previousState;
State currentState;

while (!quit)
{
    time_point newTime = Clock::now();
    auto frameTime = newTime - currentTime;
    if (frameTime > 0.25s)
        frameTime = 0.25s;
    currentTime = newTime;

    accumulator += frameTime;

    while (accumulator >= dt)
    {
        previousState = currentState;
        integrate(currentState, t, dt);
        t += dt;
        accumulator -= dt;
    }

    const double alpha = accumulator / dt;

    State state = currentState * alpha + previousState * (1 - alpha);
    render(state);
}

This version keeps everything almost exactly the same from Fix your Timestep, except some of the doubles get changed to type duration<double> (if they represent time durations), and others get changed to time_point<Clock, duration<double>> (if they represent points in time).

dt has units of duration<double> (double-based seconds), and I presume that the 0.01 from Fix your Timestep is a type-o, and the desired value is 1./60. In C++11 1.0s/60. can be changed to seconds{1}/60..

local type-aliases for duration and time_point are set up to use Clock and double-based seconds.

And from here on out, the code is nearly identical to Fix your Timestep, except for using duration or time_point in place of double for types.

Note that alpha is not a unit of time, but a dimension-less double coefficient.

  • How can I replace SDL_GetTicks() with std::chrono::high_resolution_clock::now()? It seems like no matter what I need to use count()

As above. There is no use of SDL_GetTicks() nor .count().

  • How can I replace all the floats with actual std::chrono_literal time values except for the end where I get the float deltaTime to pass into the update function as a modifier for the simulation?

As above, and you don't need to pass a float delaTime to the update function unless that function signature is out of your control. And if that is the case, then:

m_gameController->Update(deltaTime/1s);

Version 2

Now let's go a little further: Do we really need to use floating point for the duration and time_point units?

Nope. Here's how you can do the same thing with integral-based time units:

using namespace std::literals;
auto constexpr dt = std::chrono::duration<long long, std::ratio<1, 60>>{1};
using duration = decltype(Clock::duration{} + dt);
using time_point = std::chrono::time_point<Clock, duration>;

time_point t{};

time_point currentTime = Clock::now();
duration accumulator = 0s;

State previousState;
State currentState;

while (!quit)
{
    time_point newTime = Clock::now();
    auto frameTime = newTime - currentTime;
    if (frameTime > 250ms)
        frameTime = 250ms;
    currentTime = newTime;

    accumulator += frameTime;

    while (accumulator >= dt)
    {
        previousState = currentState;
        integrate(currentState, t, dt);
        t += dt;
        accumulator -= dt;
    }

    const double alpha = std::chrono::duration<double>{accumulator} / dt;

    State state = currentState * alpha + previousState * (1 - alpha);
    render(state);
}

There is really very little that has changed from Version 1:

  • dt now has the value 1, represented by a long long, and has units of 1/60 of a second.

  • duration now has a strange type that we don't even have to know the details about. It is the same type as the resultant sum of a Clock::duration and dt. This will be the coarsest precision that can exactly represent both a Clock::duration and 1/60 of a second. Who cares what it is. What is important is that the time-based arithmetic will have no truncation error, or not even any round-off error if Clock::duration is integral-based. (Who said that one can not exactly represent 1/3 on a computer?!)

  • The 0.25s limit gets transformed instead into 250ms (milliseconds{250} in C++11).

  • The computation of alpha should aggressively convert to double-based units to avoid the truncation associated with integral-based division.

More about Clock

  • Use steady_clock if you don't need to map t to a calendrical time in your physics, and/or you don't care if t slowly drifts away from the exact physical time. No clock is perfect, and steady_clock never gets adjusted to the correct time (such as by an NTP service).

  • Use system_clock if you need to map t to a calendrical time, or if you want t to stay in sync with UTC. This will require a few small (probably millisecond-level or smaller) adjustments to Clock as the game plays.

  • Use high_resolution_clock if you don't care whether you get steady_clock or system_clock and want to be surprised which you get each time you port your code to a new platform or compiler. :-)

  • Finally, you can even stick with SDL_GetTicks() if you want by writing your own Clock like this:

E.g.:

struct Clock
{
    using duration = std::chrono::milliseconds;
    using rep = duration::rep;
    using period = duration::period;
    using time_point = std::chrono::time_point<Clock>;
    static constexpr bool is_steady = true;

    static
    time_point
    now() noexcept
    {
        return time_point{duration{SDL_GetTicks()}};
    }
};

Switching between:

  • using Clock = std::chrono::steady_clock;
  • using Clock = std::chrono::system_clock;
  • using Clock = std::chrono::high_resolution_clock;
  • struct Clock {...}; // SDL_GetTicks based

requires zero changes to the event loop, the physics engine, or the render engine. Just recompile. Conversion constants get updated automatically. So you can easily experiment with which Clock is best for your application.

Appendix

My full State code for completeness:

struct State
{
    double acceleration = 1;  // m/s^2
    double velocity = 0;  // m/s
};

void
integrate(State& state,
          std::chrono::time_point<Clock, std::chrono::duration<double>>,
          std::chrono::duration<double> dt)
{
    using namespace std::literals;
    state.velocity += state.acceleration * dt/1s;
};

State operator+(State x, State y)
{
    return {x.acceleration + y.acceleration, x.velocity + y.velocity};
}

State operator*(State x, double y)
{
    return {x.acceleration * y, x.velocity * y};
}

void render(State state)
{
    using namespace std::chrono;
    static auto t = time_point_cast<seconds>(steady_clock::now());
    static int frame_count = 0;
    static int frame_rate = 0;
    auto pt = t;
    t = time_point_cast<seconds>(steady_clock::now());
    ++frame_count;
    if (t != pt)
    {
        frame_rate = frame_count;
        frame_count = 0;
    }
    std::cout << "Frame rate is " << frame_rate << " frames per second.  Velocity = "
              << state.velocity << " m/s\n";
}
like image 184
Howard Hinnant Avatar answered Sep 20 '22 02:09

Howard Hinnant