Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualL. Spiro

Posted 15 July 2013 - 12:52 PM

Time                                           

Keeping track of time is important for any game, and it can often be difficult to do just right, as there are many small nuances to handle that, when done improperly, can lead to significant bugs that can be very difficult to trace and fix.  Contributing to this is the fact that, at face value, keeping track of time seems to be a very simple task, luring many into a false sense of security when implementing their timers.  This section will outline the important features a game timer should have, discuss some common pitfalls when implementing game timers, and provide a solid game timer implementation.

Important Features           

Before anything else, it is important to outline what features a game timer should have and what it should do.

▪     Drift must be minimized.  “Drift” refers to the accumulation of small amounts of error in time that cause the game’s timer to drift slowly away from what the actual game time should be.

▪     It must have some mechanism for pausing.  This will be achieved by keeping a second time accumulator that only increments when the game is not paused.

▪     It should be in a resolution higher than milliseconds.  Even though iOS devices are capped at rendering at 60 times per second, that still only leaves an accuracy of 16 (truncated) milliseconds per frame.  The framework we will create will use a resolution of microseconds.

▪     It should have features to accommodate stepping through the game logic and the rendering logic at different rates, effectively decoupling them.

o    Note that this type of decoupling is not related to multi-threaded rendering—moving the renderer onto its own thread is an entirely different subject.

▪     It must provide an interface for making it easy to get the delta time since the last frame in both microseconds and as a floating-point value.  Floating-point values are better for physics simulations while microseconds are better for things that need to accumulate how much time has passed accurately and with as little drift as possible.

o    Again, a focus on avoiding drift will be an important factor in how this is actually implemented.

▪     Overflow of the timers should be impractical.  “Overflow” refers to the integral counter used to tell time accumulating beyond the limits of its integral form (as imposed by computer science) and wrapping back around to or past 0, which would trick sub-systems into thinking that a massive amount of time has passed since the last update (due to the unsigned nature of the integrals we will be using) which will effectively freeze most systems and cause unpredictable havoc with others.  Given enough time, any timer will eventually overflow, so our objective is to make that it takes an unreasonable time to do so, for example over 100 years.

Common Pitfalls

If at first implementing a timer seems straightforward, reading over the previous section’s list of important features may make it more obvious that there is a lot of room for error, and these errors can be very hard to detect and trace, especially if they only occur over a long period of time.

▪     Using 32-bit floating-point values to store time is one of the biggest follies an inexperienced programmer will make, as due to its decreasing precision with higher numbers, your game will become noticeably choppier in a short amount of time, from somewhat choppy after a few hours to heavily choppy after a few days.
More advanced readers may instead use 64-bit floating-point values to accumulate time, but this has more subtle flaws, particularly related to drift.  Small floating-point errors will accumulate over time, and while it may not be noticeable for a while it is also just as easy to accumulate time in the system’s native resolution with an unsigned 64-bit integer and eliminate drift to the best of the hardware’s capability.  64-bit doubles can still be used, but they should be re-derived each frame instead of accumulated directly.

▪     Updating the time more than once per game cycle, or in the most extreme case always getting the current time whenever you need it for any calculation is another common pitfall.  Related time systems should be updated at specific intervals and only at those intervals.  Examples of related time systems are those used for the sound thread, input timestamps, and the game’s primary timer.
In the event of input events, the timer for that system will be updated on each event it catches.  For the sound thread, the timer will be updated once each time the sound manager updates.  All sounds in it will then be advanced by that same amount of time to prevent any of them from updating faster or slower than the other sounds in the manager.
As for the game’s main timer, this should be updated once and only once on each game cycle, or game loop.  Imagine the worst-case scenario in which the time is read from the system every time “time” is needed in an equation.  If 2 balls fall from the same height at the same time, they should fall side-by-side.  However, if the delta time—that is the time since the last update of each ball—is obtained by always checking the current system time, any hiccups in the physics system could trick one ball into believing it has fallen for a longer time on that frame and sneak ahead of the other ball.

▪     Using milliseconds instead of microseconds is a minor pitfall and may not show a significant change on iOS devices, but using microseconds is just as easy and just more accurate.  As we will be using a macro for the resolution of our timers, however, any timer resolution will be easy to test in the end.

▪     Using a fixed framerate (such as always updating by 16.6 milliseconds, which will show slowdown when too many objects are on the screen etc.) is itself not a pitfall—it is entirely appropriate for some single-player games.  The pitfall is when you make assumptions based on the framerate, especially when those assumptions impact other parts of the engine.  There is an appropriate way to get a fixed framerate related only to the timer system and should be preferred over any assumptions that may impact other parts of the game such as the physics system.  This method will be explained later.

Implementation: Basics                  

With the features went want to have and the pitfalls we want to avoid in mind we can begin our implementation of a timer class.  The file will be part of the TKFoundation library and will be named TKFTime.  The class declaration begins with the basic members we need to keep track of time without drift and a wrapper function for getting the current system time in its own native resolution.  This is the time we will be accumulating.

 

Listing 2.3  TKFTime.h

namespace tkf {

    class CTime {
    public :
        CTime();

       
        // == Functions.
        /** Gets the real system time in its own resolution.
         *    Not to be used for any reason except random-number
         *    seeding and internal use.  Never use in game code! */
        u64                        GetRealTime() const;
   
    protected :
        // == Members.
        /** The time resolution. */
        u64                        m_f64Resolution;
       
        /** The time accumulator which always starts at 0. */
        u64                        m_u64CurTime;
       
        /** The time of the last update. */
        u64                        m_u64LastTime;
       
        /** The last system time recorded. */
        u64                        m_u64LastRealTime;
    };
 

}      // namespace tkf

TKFTime.cpp contains only the important includes, the constructor, and the implementation of GetRealTime().

Listing 2.4  TKFTime.cpp

#include "TKFTime.h"

#include <mach/mach.h>
#include <mach/mach_time.h>
   
namespace tkf {
   
    CTime::CTime() :
        m_u64CurTime( 0ULL ),
        m_u64LastTime( 0ULL ) {
        // Get the resolution.
        mach_timebase_info_data_t mtidTimeData;
        ::mach_timebase_info( &mtidTimeData );
        m_f64Resolution = static_cast<f64>(mtidTimeData.numer) /
            static_cast<f64>(mtidTimeData.denom) / 1000.0;
             
        m_u64LastRealTime = GetRealTime();
    }
   
    // == Functions.
    /** Gets the real system time in its own resolution.
     *    Not to be used for any reason except random-number
     *    seeding and internal use.  Never use in game code! */
    u64 CTime::GetRealTime() const {
        return ::mach_absolute_time();
    }
   

}    // namespace tkf

mach_absolute_time() returns the number of ticks since the device has been turned on and will be in a resolution native to the device.  The values returned by mach_timebase_info() provide the numerator and denominator necessary to convert the system ticks into nanoseconds.  Note that while we are using a 64-bit floating-point value for the conversion from system ticks to microseconds, we are not using it for any accumulation purposes, and as such it does not contribute to drift.  Because it is used in multiplication later it has been divided by 1,000.0 so that it converts to microseconds rather than nanoseconds.

The next step is to add accumulation methods.  This will be split into 2 functions: One that allows the number of system ticks by which to update and one that calls the former after actually determining how many ticks have passed since the last update.  By splitting the update into these 2 functions we can keep other timers as slaves to another so that as the main timer updates, the amount by which it updates can be cascaded down to other timers so that they all update by the same amount.  This will be important later.

Listing 2.5  TKFTime.cpp

    /** Calculates how many system ticks have passed

     *    since the last update and calls UpdateBy()
     *    with that value. */
    void CTime::Update( bool _bUpdateVirtuals ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
        m_u64LastRealTime = u64TimeNow;
       
        UpdateBy( u64Delta, _bUpdateVirtuals );
    }
   
    /** Updates by the given number of system ticks. */
    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;

    }

Accumulating time in system resolution is simple.  Note that inside of Update() the delta was calculated with a simple subtraction without any special-case handling for the wrap-around of the system tick counter.  Due to how machines handle integer math, this is correct, as the wrap-around case will still result in the correct delta time.

Our timer will need to return the current microseconds at any given time so it is best to calculate that value up-front.  Doing so is simple as it is just a matter of a single multiplication with the timer resolution.  The CTime class will receive a new member called m_u64CurMicros and UpdateBy() will be modified.

Listing 2.6  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);

    }

Next, we need microsecond values for the current time and for how much time has passed.  Handling this in a way that avoids drift is trickier.  Let’s consider only the case of determining the number of microseconds since the last frame, as a u64 type.  Inside of UpdateBy() we could simply convert _u64Ticks to microseconds, since that represents the amount of time that has passed since the last update.  However this always truncates and we never get back any of those truncates microseconds, which is exactly what causes drift.  Instead, microseconds since the last update must be calculated based off the raw ticks of the last update subtracted from the raw current ticks (after the update).  This will add a member to CTime called m_u64DeltaMicros, and with it UpdateBy() must be modified.

Listing 2.7  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        u64 u64LastMicros = m_u64CurMicros;
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);
        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;

    }

m_u64CurMicros and m_u64DeltaMicros can get returned by inlined methods GetCurMicros() and GetDeltaMicros(), not shown here for brevity.  Objects that want to accumulate time should accumulate with GetDeltaMicros().  Another time-related attribute that is commonly needed is the amount of time that has passed in seconds, often in 32-bit floating-point format since it is generally a small value.  This value will also be updated once inside UpdateBy() and obtained by an inlined accessor method called GetDeltaTime().

Listing 2.8  TKFTime.cpp

        …

        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;
        m_f32DeltaTime = m_u64DeltaMicros *

            static_cast<f32>(1.0 / 1000000.0);

Implementation: Pause

The time class updates in such a way as to avoid drift and overflow, and buffers common time values for fast access via inlined accessors.  The next feature to add is pausing.  This is very simple and largely a repeat of previous updating code.  Pausing is implemented via a second set of accumulators called “virtual” accumulators.  Virtual ticks will be optionally accumulated on each update, and the rest (virtual current microseconds, virtual delta microseconds, and virtual delta time) will be updated based off that in the same way the normal deltas and time values are updated.  A new set of “Virt” members are added to CTime and updated inside of UpdateBy().

Listing 2.9  TKFTime.cpp

        …

        if ( _bUpdateVirtuals ) {
            m_u64VirtCurTime += _u64Ticks;
            u64 u64VirtLastMicros = m_u64VirtCurMicros;
            m_u64VirtCurMicros = static_cast<u64>(m_u64VirtCurTime
                * m_f64Resolution);
            m_u64VirtDeltaMicros = m_u64VirtCurMicros - u64VirtLastMicros;
            m_f32VirtDeltaTime = m_u64VirtDeltaMicros *
                static_cast<f32>(1.0 / 1000000.0);

        }

Additionally, inlined accessors are added to access these virtual timers (not shown here for brevity).  When objects can be paused, they should always exclusively use the virtual set of time values.  The standard time values are incremented every frame and can be used to animate things that never pause such as menus.  Meanwhile, the game world will update based on the virtual set of time values and all game objects will stop moving when the game is paused.

Implementation: Fixed Time-Stepping

Fixed time-stepping is itself sometimes a difficult concept to grasp, and proper implementations are often difficult to get right.  Fixed time-stepping refers to decoupling the logical updates from the rendering (this form of decoupling is unrelated to multi-threaded rendering), executing logical updates only after a certain fixed amount of time has passed while rendering as often as possible, regardless of how much time has passed.  There are several important reasons why this is done.  Firstly, logical updates are where physics, AI, scripts, etc., are run.  By spacing these updates out over a few frames rather than every frame CPU usage is reduced and the overall framerate can increase.  Secondly, and most importantly, physics simulations require a constant update time each time they are run in order to avoid exploding scenes and other buggy behavior.  Finally, fixed time steps are essential for keeping synchronization over network play as close as possible.  While it is still possible for clients to lose sync and there does need to be a mechanism to re-sync clients anyway, things are greatly simplified when non-interactive parts of the scene are run by fixed time steps, which all but ensures they will remain in sync for all clients.

Conceptually it can be viewed as shown in Figure 2-7.  Logical updates, in a perfect world, would happen at perfectly even intervals.  Renders happen as fast as possible, on every game loop or game cycle, which means there may be longer delays between some renders and short delays between others.

 

Figure 2-7

Unfortunately the logical updates and renders are executed on the same thread, and since renders happen every loop it is impossible to actually place a logical update anywhere except on the same intervals as the renders.  That is, you cannot have a render every loop and somehow insert a logical update half-way into the loop.  It turns out, however, that this is nothing but a conceptual problem.  Inside of the game, actual universal time doesn’t matter.  Imagine scenario 1 in which a render is delayed for 3 seconds and logical updates occur every second.  In a perfect world, we would wait 1 second, perform 1 logical update, wait another second and update logic, wait 1 more second and update logic, and then render.  But to the player who is looking at the screen, this process yields exactly the same result as if we waited 3 seconds, then updated the logic 3 times quickly, each update by 1 second, and then rendered.  The simulation has, in either case, moved forward by 3 seconds before the render, and the render itself will be identical in both scenarios.  In other words, the logical updates don’t actually need to occur at the correct times in real time—the only thing that matters is if the same number of logical updates have been executed before the render.  In practice, it looks like Figure 2-8.

 

Figure 2-8

In Figure 2-8, the logical updates occur at the same time as the renders because they are on the same thread and can only execute inside of a single game loop.  The original spacing of the logical updates is shown in grey.  Instead of executing the logical updates at arbitrary times within the game loop, we simply change the number of time the logical updates occur on each game loop.  Notice that the second logical update was pushed back a bit due to some lag, but in total 2 logical updates took place before the second render, which means the game simulation had advanced by, let’s say 2 seconds (borrowing from our previous example), which means the render still depicts the game state the same way it would have had we been able to execute the logical update at literal 1-second intervals.

Notice also that if the game loop and render execute too quickly, sometimes too little time passes to justify another logical update.  In this case 0 logical updates were issued on that game loop and the loop goes straight to rendering.  This saves on CPU usage.  Although not shown here, it can be extrapolated that 0 and 1 are not the only number of times that might be necessary to run the logical update in a single game loop.  If there is a strong lag and the delay between frames increases enough, it may be necessary to run 2, 3, or more logical updates in a single loop.  Our CTime class is going to determine for us how many times to update the logic on each game loop.  Actually performing the updates will be covered in the next chapter.  Additionally, an astute reader may have realized that in these simple examples it doesn’t make sense to render unless a logical update has taken place because you would be rendering the exact same scene with all the objects in their same locations etc.  While this is true for the simple example provided here, there is also a solution to this involving interpolation.  Again, this is handled at a higher level in the system and will be explained in detail in the next chapter, but it is worth mentioning now because in order to perform that interpolation we will need the CTime class to give us an extra value back when it calculates how many logical updates to perform.

The main question we want the CTime class to answer is how many times we need to update the logical loop each tick.  For this, a new method is added to CTime called GetFixedStepUpdateCountFromTicks().

Listing 2.10  TKFTime.cpp

    /** Gets the the number logical updates necessary for a fixed time

     *    step of the given number of system ticks as well as the fraction
     *    between logical updates where the simulation will be after
     *    updating the returned number of times. */
    u32 CTime::GetFixedStepUpdateCountFromTicks( u64 _u64Ticks,
        f32 &_f32Ratio, u64 &_u64RemainderTicks ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
      
        u32 u32Count = static_cast<u32>(u64Delta / _u64Ticks);
        u64 u64AddMe = u32Count * _u64Ticks;
        m_u64LastRealTime += u64AddMe;
        _u64RemainderTicks = u64Delta - u64AddMe;
       
        _f32Ratio = static_cast<f32>(static_cast<f64>(u64AddMe) /
            static_cast<f64>(_u64Ticks));
        return u32Count;

    }

Notice that since GetRealTime() is called directly this should not be used in conjunction with Update().  This utility function is meant to be used with UpdateBy().  Notice that after getting the real time it doesn’t directly copy that into m_u64LastRealTime.  If it did, then the next time this is called on the next frame the delta would not include the previous frame’s time.  If the deltas don’t accumulate across frames, the proper number of logical updates per frame can’t be calculated—remember that it may take several frames before a logical update is needed.  Next, notice that m_u64LastRealTime is modified by adding the count multiplied by the ticks.  The CTime class will expect you to call UpdateBy() with the same number of ticks, u32Count times.  Again, this is to remove drift.  While we will lose a few ticks to rounded off fractions now, they will be regained on later frames.  Finally, when the logical update has executed u32Count number of times, each time adding _u64Ticks to its current simulation time, the logical update’s time will be a tick that is a multiple of _u64Ticks but the real game time will be somewhere between that time and the next logical update (the logical update’s time + _u64Ticks).  _f32Ratio is calculated to represent the fraction of the real time between logical updates.  This will be useful in the next chapter.  The actual number of ticks between logical ticks is stored in the return-by-reference parameter _u64RemainderTicks, which will later be needed to update the render time for each cycle.

 

 

L. Spiro


#4L. Spiro

Posted 15 July 2013 - 12:51 PM

Time                                           

Keeping track of time is important for any game, and it can often be difficult to do just right, as there are many small nuances to handle that, when done improperly, can lead to significant bugs that can be very difficult to trace and fix.  Contributing to this is the fact that, at face value, keeping track of time seems to be a very simple task, luring many into a false sense of security when implementing their timers.  This section will outline the important features a game timer should have, discuss some common pitfalls when implementing game timers, and provide a solid game timer implementation.

Important Features           

Before anything else, it is important to outline what features a game timer should have and what it should do.

▪     Drift must be minimized.  “Drift” refers to the accumulation of small amounts of error in time that cause the game’s timer to drift slowly away from what the actual game time should be.

▪     It must have some mechanism for pausing.  This will be achieved by keeping a second time accumulator that only increments when the game is not paused.

▪     It should be in a resolution higher than milliseconds.  Even though iOS devices are capped at rendering at 60 times per second, that still only leaves an accuracy of 16 (truncated) milliseconds per frame.  The framework we will create will use a resolution of microseconds.

▪     It should have features to accommodate stepping through the game logic and the rendering logic at different rates, effectively decoupling them.

o    Note that this type of decoupling is not related to multi-threaded rendering—moving the renderer onto its own thread is an entirely different subject.

▪     It must provide an interface for making it easy to get the delta time since the last frame in both microseconds and as a floating-point value.  Floating-point values are better for physics simulations while microseconds are better for things that need to accumulate how much time has passed accurately and with as little drift as possible.

o    Again, a focus on avoiding drift will be an important factor in how this is actually implemented.

▪     Overflow of the timers should be impractical.  “Overflow” refers to the integral counter used to tell time accumulating beyond the limits of its integral form (as imposed by computer science) and wrapping back around to or past 0, which would trick sub-systems into thinking that a massive amount of time has passed since the last update (due to the unsigned nature of the integrals we will be using) which will effectively freeze most systems and cause unpredictable havoc with others.  Given enough time, any timer will eventually overflow, so our objective is to make that it takes an unreasonable time to do so, for example over 100 years.

Common Pitfalls

If at first implementing a timer seems straightforward, reading over the previous section’s list of important features may make it more obvious that there is a lot of room for error, and these errors can be very hard to detect and trace, especially if they only occur over a long period of time.

▪     Using 32-bit floating-point values to store time is one of the biggest follies an inexperienced programmer will make, as due to its decreasing precision with higher numbers, your game will become noticeably choppier in a short amount of time, from somewhat choppy after a few hours to heavily choppy after a few days.
More advanced readers may instead use 64-bit floating-point values to accumulate time, but this has more subtle flaws, particularly related to drift.  Small floating-point errors will accumulate over time, and while it may not be noticeable for a while it is also just as easy to accumulate time in the system’s native resolution with an unsigned 64-bit integer and eliminate drift to the best of the hardware’s capability.  64-bit doubles can still be used, but they should be re-derived each frame instead of accumulated directly.

▪     Updating the time more than once per game cycle, or in the most extreme case always getting the current time whenever you need it for any calculation is another common pitfall.  Related time systems should be updated at specific intervals and only at those intervals.  Examples of related time systems are those used for the sound thread, input timestamps, and the game’s primary timer.
In the event of input events, the timer for that system will be updated on each event it catches.  For the sound thread, the timer will be updated once each time the sound manager updates.  All sounds in it will then be advanced by that same amount of time to prevent any of them from updating faster or slower than the other sounds in the manager.
As for the game’s main timer, this should be updated once and only once on each game cycle, or game loop.  Imagine the worst-case scenario in which the time is read from the system every time “time” is needed in an equation.  If 2 balls fall from the same height at the same time, they should fall side-by-side.  However, if the delta time—that is the time since the last update of each ball—is obtained by always checking the current system time, any hiccups in the physics system could trick one ball into believing it has fallen for a longer time on that frame and sneak ahead of the other ball.

▪     Using milliseconds instead of microseconds is a minor pitfall and may not show a significant change on iOS devices, but using microseconds is just as easy and just more accurate.  As we will be using a macro for the resolution of our timers, however, any timer resolution will be easy to test in the end.

▪     Using a fixed framerate (such as always updating by 16.6 milliseconds, which will show slowdown when too many objects are on the screen etc.) is itself not a pitfall—it is entirely appropriate for some single-player games.  The pitfall is when you make assumptions based on the framerate, especially when those assumptions impact other parts of the engine.  There is an appropriate way to get a fixed framerate related only to the timer system and should be preferred over any assumptions that may impact other parts of the game such as the physics system.  This method will be explained later.

Implementation: Basics                  

With the features went want to have and the pitfalls we want to avoid in mind we can begin our implementation of a timer class.  The file will be part of the TKFoundation library and will be named TKFTime.  The class declaration begins with the basic members we need to keep track of time without drift and a wrapper function for getting the current system time in its own native resolution.  This is the time we will be accumulating.

 

Listing 2.3  TKFTime.h

namespace tkf {

    class CTime {
    public :
        CTime();

       
        // == Functions.
        /** Gets the real system time in its own resolution.
         *    Not to be used for any reason except random-number
         *    seeding and internal use.  Never use in game code! */
        u64                        GetRealTime() const;
   
    protected :
        // == Members.
        /** The time resolution. */
        u64                        m_f64Resolution;
       
        /** The time accumulator which always starts at 0. */
        u64                        m_u64CurTime;
       
        /** The time of the last update. */
        u64                        m_u64LastTime;
       
        /** The last system time recorded. */
        u64                        m_u64LastRealTime;
    };
 

}      // namespace tkf

TKFTime.cpp contains only the important includes, the constructor, and the implementation of GetRealTime().

Listing 2.4  TKFTime.cpp

#include "TKFTime.h"

#include <mach/mach.h>
#include <mach/mach_time.h>
   
namespace tkf {
   
    CTime::CTime() :
        m_u64CurTime( 0ULL ),
        m_u64LastTime( 0ULL ) {
        // Get the resolution.
        mach_timebase_info_data_t mtidTimeData;
        ::mach_timebase_info( &mtidTimeData );
        m_f64Resolution = static_cast<f64>(mtidTimeData.numer) /
            static_cast<f64>(mtidTimeData.denom) / 1000.0;
             
        m_u64LastRealTime = GetRealTime();
    }
   
    // == Functions.
    /** Gets the real system time in its own resolution.
     *    Not to be used for any reason except random-number
     *    seeding and internal use.  Never use in game code! */
    u64 CTime::GetRealTime() const {
        return ::mach_absolute_time();
    }
   

}    // namespace tkf

mach_absolute_time() returns the number of ticks since the device has been turned on and will be in a resolution native to the device.  The values returned by mach_timebase_info() provide the numerator and denominator necessary to convert the system ticks into nanoseconds.  Note that while we are using a 64-bit floating-point value for the conversion from system ticks to microseconds, we are not using it for any accumulation purposes, and as such it does not contribute to drift.  Because it is used in multiplication later it has been divided by 1,000.0 so that it converts to microseconds rather than nanoseconds.

The next step is to add accumulation methods.  This will be split into 2 functions: One that allows the number of system ticks by which to update and one that calls the former after actually determining how many ticks have passed since the last update.  By splitting the update into these 2 functions we can keep other timers as slaves to another so that as the main timer updates, the amount by which it updates can be cascaded down to other timers so that they all update by the same amount.  This will be important later.

Listing 2.5  TKFTime.cpp

    /** Calculates how many system ticks have passed

     *    since the last update and calls UpdateBy()
     *    with that value. */
    void CTime::Update( bool _bUpdateVirtuals ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
        m_u64LastRealTime = u64TimeNow;
       
        UpdateBy( u64Delta, _bUpdateVirtuals );
    }
   
    /** Updates by the given number of system ticks. */
    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;

    }

Accumulating time in system resolution is simple.  Note that inside of Update() the delta was calculated with a simple subtraction without any special-case handling for the wrap-around of the system tick counter.  Due to how machines handle integer math, this is correct, as the wrap-around case will still result in the correct delta time.

Our timer will need to return the current microseconds at any given time so it is best to calculate that value up-front.  Doing so is simple as it is just a matter of a single multiplication with the timer resolution.  The CTime class will receive a new member called m_u64CurMicros and UpdateBy() will be modified.

Listing 2.6  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);

    }

Next, we need microsecond values for the current time and for how much time has passed.  Handling this in a way that avoids drift is trickier.  Let’s consider only the case of determining the number of microseconds since the last frame, as a u64 type.  Inside of UpdateBy() we could simply convert _u64Ticks to microseconds, since that represents the amount of time that has passed since the last update.  However this always truncates and we never get back any of those truncates microseconds, which is exactly what causes drift.  Instead, microseconds since the last update must be calculated based off the raw ticks of the last update subtracted from the raw current ticks (after the update).  This will add a member to CTime called m_u64DeltaMicros, and with it UpdateBy() must be modified.

Listing 2.7  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        u64 u64LastMicros = m_u64CurMicros;
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);
        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;

    }

m_u64CurMicros and m_u64DeltaMicros can get returned by inlined methods GetCurMicros() and GetDeltaMicros(), not shown here for brevity.  Objects that want to accumulate time should accumulate with GetDeltaMicros().  Another time-related attribute that is commonly needed is the amount of time that has passed in seconds, often in 32-bit floating-point format since it is generally a small value.  This value will also be updated once inside UpdateBy() and obtained by an inlined accessor method called GetDeltaTime().

Listing 2.8  TKFTime.cpp

        …

        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;
        m_f32DeltaTime = m_u64DeltaMicros *

            static_cast<f32>(1.0 / 1000000.0);

Implementation: Pause

The time class updates in such a way as to avoid drift and overflow, and buffers common time values for fast access via inlined accessors.  The next feature to add is pausing.  This is very simple and largely a repeat of previous updating code.  Pausing is implemented via a second set of accumulators called “virtual” accumulators.  Virtual ticks will be optionally accumulated on each update, and the rest (virtual current microseconds, virtual delta microseconds, and virtual delta time) will be updated based off that in the same way the normal deltas and time values are updated.  A new set of “Virt” members are added to CTime and updated inside of UpdateBy().

Listing 2.9  TKFTime.cpp

        …

        if ( _bUpdateVirtuals ) {
            m_u64VirtCurTime += _u64Ticks;
            u64 u64VirtLastMicros = m_u64VirtCurMicros;
            m_u64VirtCurMicros = static_cast<u64>(m_u64VirtCurTime
                * m_f64Resolution);
            m_u64VirtDeltaMicros = m_u64VirtCurMicros - u64VirtLastMicros;
            m_f32VirtDeltaTime = m_u64VirtDeltaMicros *
                static_cast<f32>(1.0 / 1000000.0);

        }

Additionally, inlined accessors are added to access these virtual timers (not shown here for brevity).  When objects can be paused, they should always exclusively use the virtual set of time values.  The standard time values are incremented every frame and can be used to animate things that never pause such as menus.  Meanwhile, the game world will update based on the virtual set of time values and all game objects will stop moving when the game is paused.

Implementation: Fixed Time-Stepping

Fixed time-stepping is itself sometimes a difficult concept to grasp, and proper implementations are often difficult to get right.  Fixed time-stepping refers to decoupling the logical updates from the rendering (this form of decoupling is unrelated to multi-threaded rendering), executing logical updates only after a certain fixed amount of time has passed while rendering as often as possible, regardless of how much time has passed.  There are several important reasons why this is done.  Firstly, logical updates are where physics, AI, scripts, etc., are run.  By spacing these updates out over a few frames rather than every frame CPU usage is reduced and the overall framerate can increase.  Secondly, and most importantly, physics simulations require a constant update time each time they are run in order to avoid exploding scenes and other buggy behavior.  Finally, fixed time steps are essential for keeping synchronization over network play as close as possible.  While it is still possible for clients to lose sync and there does need to be a mechanism to re-sync clients anyway, things are greatly simplified when non-interactive parts of the scene are run by fixed time steps, which all but ensures they will remain in sync for all clients.

Conceptually it can be viewed as shown in Figure 2-7.  Logical updates, in a perfect world, would happen at perfectly even intervals.  Renders happen as fast as possible, on every game loop or game cycle, which means there may be longer delays between some renders and short delays between others.

 

Figure 2-7

Unfortunately the logical updates and renders are executed on the same thread, and since renders happen every loop it is impossible to actually place a logical update anywhere except on the same intervals as the renders.  That is, you cannot have a render every loop and somehow insert a logical update half-way into the loop.  It turns out, however, that this is nothing but a conceptual problem.  Inside of the game, actual universal time doesn’t matter.  Imagine scenario 1 in which a render is delayed for 3 seconds and logical updates occur every second.  In a perfect world, we would wait 1 second, perform 1 logical update, wait another second and update logic, wait 1 more second and update logic, and then render.  But to the player who is looking at the screen, this process yields exactly the same result as if we waited 3 seconds, then updated the logic 3 times quickly, each update by 1 second, and then rendered.  The simulation has, in either case, moved forward by 3 seconds before the render, and the render itself will be identical in both scenarios.  In other words, the logical updates don’t actually need to occur at the correct times in real time—the only thing that matters is if the same number of logical updates have been executed before the render.  In practice, it looks like Figure 2-8.

 

Figure 2-8

In Figure 2-8, the logical updates occur at the same time as the renders because they are on the same thread and can only execute inside of a single game loop.  The original spacing of the logical updates is shown in grey.  Instead of executing the logical updates at arbitrary times within the game loop, we simply change the number of time the logical updates occur on each game loop.  Notice that the second logical update was pushed back a bit due to some lag, but in total 2 logical updates took place before the second render, which means the game simulation had advanced by, let’s say 2 seconds (borrowing from our previous example), which means the render still depicts the game state the same way it would have had we been able to execute the logical update at literal 1-second intervals.

Notice also that if the game loop and render execute too quickly, sometimes too little time passes to justify another logical update.  In this case 0 logical updates were issued on that game loop and the loop goes straight to rendering.  This saves on CPU usage.  Although not shown here, it can be extrapolated that 0 and 1 are not the only number of times that might be necessary to run the logical update in a single game loop.  If there is a strong lag and the delay between frames increases enough, it may be necessary to run 2, 3, or more logical updates in a single loop.  Our CTime class is going to determine for us how many times to update the logic on each game loop.  Actually performing the updates will be covered in the next chapter.  Additionally, an astute reader may have realized that in these simple examples it doesn’t make sense to render unless a logical update has taken place because you would be rendering the exact same scene with all the objects in their same locations etc.  While this is true for the simple example provided here, there is also a solution to this involving interpolation.  Again, this is handled at a higher level in the system and will be explained in detail in the next chapter, but it is worth mentioning now because in order to perform that interpolation we will need the CTime class to give us an extra value back when it calculates how many logical updates to perform.

The main question we want the CTime class to answer is how many times we need to update the logical loop each tick.  For this, a new method is added to CTime called GetFixedStepUpdateCountFromTicks().

Listing 2.10  TKFTime.cpp

    /** Gets the the number logical updates necessary for a fixed time

     *    step of the given number of system ticks as well as the fraction
     *    between logical updates where the simulation will be after
     *    updating the returned number of times. */
    u32 CTime::GetFixedStepUpdateCountFromTicks( u64 _u64Ticks,
        f32 &_f32Ratio, u64 &_u64RemainderTicks ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
      
        u32 u32Count = static_cast<u32>(u64Delta / _u64Ticks);
        u64 u64AddMe = u32Count * _u64Ticks;
        m_u64LastRealTime += u64AddMe;
        _u64RemainderTicks = u64Delta - u64AddMe;
       
        _f32Ratio = static_cast<f32>(static_cast<f64>(u64AddMe) /
            static_cast<f64>(_u64Ticks));
        return u32Count;

    }

Notice that since GetRealTime() is called directly this should not be used in conjunction with Update().  This utility function is meant to be used with UpdateBy().  Notice that after getting the real time it doesn’t directly copy that into m_u64LastRealTime.  If it did, then the next time this is called on the next frame the delta would not include the previous frame’s time.  If the deltas don’t accumulate across frames, the proper number of logical updates per frame can’t be calculated—remember that it may take several frames before a logical update is needed.  Next, notice that m_u64LastRealTime is modified by adding the count multiplied by the ticks.  The CTime class will expect you to call UpdateBy() with the same number of ticks, u32Count times.  Again, this is to remove drift.  While we will lose a few ticks to rounded off fractions now, they will be regained on later frames.  Finally, when the logical update has executed u32Count number of times, each time adding _u64Ticks to its current simulation time, the logical update’s time will be a tick that is a multiple of _u64Ticks but the real game time will be somewhere between that time and the next logical update (the logical update’s time + _u64Ticks).  _f32Ratio is calculated to represent the fraction of the real time between logical updates.  This will be useful in the next chapter.  The actual number of ticks between logical ticks is stored in the return-by-reference parameter _u64RemainderTicks, which will later be needed to update the render time for each cycle.

 

 

L. Spiro


#3L. Spiro

Posted 14 July 2013 - 11:51 PM

Time                                           

Keeping track of time is important for any game, and it can often be difficult to do just right, as there are many small nuances to handle that, when done improperly, can lead to significant bugs that can be very difficult to trace and fix.  Contributing to this is the fact that, at face value, keeping track of time seems to be a very simple task, luring many into a false sense of security when implementing their timers.  This section will outline the important features a game timer should have, discuss some common pitfalls when implementing game timers, and provide a solid game timer implementation.

Important Features           

Before anything else, it is important to outline what features a game timer should have and what it should do.

▪     Drift must be minimized.  “Drift” refers to the accumulation of small amounts of error in time that cause the game’s timer to drift slowly away from what the actual game time should be.

▪     It must have some mechanism for pausing.  This will be achieved by keeping a second time accumulator that only increments when the game is not paused.

▪     It should be in a resolution higher than milliseconds.  Even though iOS devices are capped at rendering at 60 times per second, that still only leaves an accuracy of 16 (truncated) milliseconds per frame.  The framework we will create will use a resolution of microseconds.

▪     It should have features to accommodate stepping through the game logic and the rendering logic at different rates, effectively decoupling them.

o    Note that this type of decoupling is not related to multi-threaded rendering—moving the renderer onto its own thread is an entirely different subject.

▪     It must provide an interface for making it easy to get the delta time since the last frame in both microseconds and as a floating-point value.  Floating-point values are better for physics simulations while microseconds are better for things that need to accumulate how much time has passed accurately and with as little drift as possible.

o    Again, a focus on avoiding drift will be an important factor in how this is actually implemented.

▪     Overflow of the timers should be impractical.  “Overflow” refers to the integral counter used to tell time accumulating beyond the limits of its integral form (as imposed by computer science) and wrapping back around to or past 0, which would trick sub-systems into thinking that a massive amount of time has passed since the last update (due to the unsigned nature of the integrals we will be using) which will effectively freeze most systems and cause unpredictable havoc with others.  Given enough time, any timer will eventually overflow, so our objective is to make that it takes an unreasonable time to do so, for example over 100 years.

Common Pitfalls

If at first implementing a timer seems straightforward, reading over the previous section’s list of important features may make it more obvious that there is a lot of room for error, and these errors can be very hard to detect and trace, especially if they only occur over a long period of time.

▪     Using 32-bit floating-point values to store time is one of the biggest follies an inexperienced programmer will make, as due to its decreasing precision with higher numbers, your game will become noticeably choppier in a short amount of time, from somewhat choppy after a few hours to heavily choppy after a few days.
More advanced readers may instead use 64-bit floating-point values to accumulate time, but this has more subtle flaws, particularly related to drift.  Small floating-point errors will accumulate over time, and while it may not be noticeable for a while it is also just as easy to accumulate time in the system’s native resolution with an unsigned 64-bit integer and eliminate drift to the best of the hardware’s capability.  64-bit doubles can still be used, but they should be re-derived each frame instead of accumulated directly.

▪     Updating the time more than once per game cycle, or in the most extreme case always getting the current time whenever you need it for any calculation is another common pitfall.  Related time systems should be updated at specific intervals and only at those intervals.  Examples of related time systems are those used for the sound thread, input timestamps, and the game’s primary timer.
In the event of input events, the timer for that system will be updated on each event it catches.  For the sound thread, the timer will be updated once each time the sound manager updates.  All sounds in it will then be advanced by that same amount of time to prevent any of them from updating faster or slower than the other sounds in the manager.
As for the game’s main timer, this should be updated once and only once on each game cycle, or game loop.  Imagine the worst-case scenario in which the time is read from the system every time “time” is needed in an equation.  If 2 balls fall from the same height at the same time, they should fall side-by-side.  However, if the delta time—that is the time since the last update of each ball—is obtained by always checking the current system time, any hiccups in the physics system could trick one ball into believing it has fallen for a longer time on that frame and sneak ahead of the other ball.

▪     Using milliseconds instead of microseconds is a minor pitfall and may not show a significant change on iOS devices, but using microseconds is just as easy and just more accurate.  As we will be using a macro for the resolution of our timers, however, any timer resolution will be easy to test in the end.

▪     Using a fixed framerate (such as always updating by 16.6 milliseconds, which will show slowdown when too many objects are on the screen etc.) is itself not a pitfall—it is entirely appropriate for some single-player games.  The pitfall is when you make assumptions based on the framerate, especially when those assumptions impact other parts of the engine.  There is an appropriate way to get a fixed framerate related only to the timer system and should be preferred over any assumptions that may impact other parts of the game such as the physics system.  This method will be explained later.

Implementation: Basics                  

With the features went want to have and the pitfalls we want to avoid in mind we can begin our implementation of a timer class.  The file will be part of the TKFoundation library and will be named TKFTime.  The class declaration begins with the basic members we need to keep track of time without drift and a wrapper function for getting the current system time in its own native resolution.  This is the time we will be accumulating.

 

Listing 2.3  TKFTime.h

namespace tkf {

    class CTime {
    public :
        CTime();

       
        // == Functions.
        /** Gets the real system time in its own resolution.
         *    Not to be used for any reason except random-number
         *    seeding and internal use.  Never use in game code! */
        u64                        GetRealTime() const;
   
    protected :
        // == Members.
        /** The time resolution. */
        u64                        m_f64Resolution;
       
        /** The time accumulator which always starts at 0. */
        u64                        m_u64CurTime;
       
        /** The time of the last update. */
        u64                        m_u64LastTime;
       
        /** The last system time recorded. */
        u64                        m_u64LastRealTime;
    };
 

}      // namespace tkf

TKFTime.cpp contains only the important includes, the constructor, and the implementation of GetRealTime().

Listing 2.4  TKFTime.cpp

#include "TKFTime.h"

#include <mach/mach.h>
#include <mach/mach_time.h>
   
namespace tkf {
   
    CTime::CTime() :
        m_u64CurTime( 0ULL ),
        m_u64LastTime( 0ULL ) {
        // Get the resolution.
        mach_timebase_info_data_t mtidTimeData;
        ::mach_timebase_info( &mtidTimeData );
        m_f64Resolution = static_cast<f64>(mtidTimeData.numer) /
            static_cast<f64>(mtidTimeData.denom) / 1000.0;
             
        m_u64LastRealTime = GetRealTime();
    }
   
    // == Functions.
    /** Gets the real system time in its own resolution.
     *    Not to be used for any reason except random-number
     *    seeding and internal use.  Never use in game code! */
    u64 CTime::GetRealTime() const {
        return ::mach_absolute_time();
    }
   

}    // namespace tkf

mach_absolute_time() returns the number of ticks since the device has been turned on and will be in a resolution native to the device.  The values returned by mach_timebase_info() provide the numerator and denominator necessary to convert the system ticks into nanoseconds.  Note that while we are using a 64-bit floating-point value for the conversion from system ticks to microseconds, we are not using it for any accumulation purposes, and as such it does not contribute to drift.  Because it is used in multiplication later it has been divided by 1,000.0 so that it converts to microseconds rather than nanoseconds.

The next step is to add accumulation methods.  This will be split into 2 functions: One that allows the number of system ticks by which to update and one that calls the former after actually determining how many ticks have passed since the last update.  By splitting the update into these 2 functions we can keep other timers as slaves to another so that as the main timer updates, the amount by which it updates can be cascaded down to other timers so that they all update by the same amount.  This will be important later.

Listing 2.5  TKFTime.cpp

    /** Calculates how many system ticks have passed

     *    since the last update and calls UpdateBy()
     *    with that value. */
    void CTime::Update( bool _bUpdateVirtuals ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
        m_u64LastRealTime = u64TimeNow;
       
        UpdateBy( u64Delta, _bUpdateVirtuals );
    }
   
    /** Updates by the given number of system ticks. */
    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;

    }

Accumulating time in system resolution is simple.  Note that inside of Update() the delta was calculated with a simple subtraction without any special-case handling for the wrap-around of the system tick counter.  Due to how machines handle integer math, this is correct, as the wrap-around case will still result in the correct delta time.

Our timer will need to return the current microseconds at any given time so it is best to calculate that value up-front.  Doing so is simple as it is just a matter of a single multiplication with the timer resolution.  The CTime class will receive a new member called m_u64CurMicros and UpdateBy() will be modified.

Listing 2.6  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);

    }

Next, we need microsecond values for the current time and for how much time has passed.  Handling this in a way that avoids drift is trickier.  Let’s consider only the case of determining the number of microseconds since the last frame, as a u64 type.  Inside of UpdateBy() we could simply convert _u64Ticks to microseconds, since that represents the amount of time that has passed since the last update.  However this always truncates and we never get back any of those truncates microseconds, which is exactly what causes drift.  Instead, microseconds since the last update must be calculated based off the raw ticks of the last update subtracted from the raw current ticks (after the update).  This will add a member to CTime called m_u64DeltaMicros, and with it UpdateBy() must be modified.

Listing 2.7  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        u64 u64LastMicros = m_u64CurMicros;
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);
        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;

    }

m_u64CurMicros and m_u64DeltaMicros can get returned by inlined methods GetCurMicros() and GetDeltaMicros(), not shown here for brevity.  Objects that want to accumulate time should accumulate with GetDeltaMicros().  Another time-related attribute that is commonly needed is the amount of time that has passed in seconds, often in 32-bit floating-point format since it is generally a small value.  This value will also be updated once inside UpdateBy() and obtained by an inlined accessor method called GetDeltaTime().

Listing 2.8  TKFTime.cpp

        …

        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;
        m_f32DeltaTime = m_u64DeltaMicros *

            static_cast<f32>(1.0 / 1000000.0);

Implementation: Pause

The time class updates in such a way as to avoid drift and overflow, and buffers common time values for fast access via inlined accessors.  The next feature to add is pausing.  This is very simple and largely a repeat of previous updating code.  Pausing is implemented via a second set of accumulators called “virtual” accumulators.  Virtual ticks will be optionally accumulated on each update, and the rest (virtual current microseconds, virtual delta microseconds, and virtual delta time) will be updated based off that in the same way the normal deltas and time values are updated.  A new set of “Virt” members are added to CTime and updated inside of UpdateBy().

Listing 2.9  TKFTime.cpp

        …

        if ( _bUpdateVirtuals ) {
            m_u64VirtCurTime += _u64Ticks;
            u64 u64VirtLastMicros = m_u64VirtCurMicros;
            m_u64VirtCurMicros = static_cast<u64>(m_u64VirtCurTime
                * m_f64Resolution);
            m_u64VirtDeltaMicros = m_u64VirtCurMicros - u64VirtLastMicros;
            m_f32VirtDeltaTime = m_u64VirtDeltaMicros *
                static_cast<f32>(1.0 / 1000000.0);

        }

Additionally, inlined accessors are added to access these virtual timers (not shown here for brevity).  When objects can be paused, they should always exclusively use the virtual set of time values.  The standard time values are incremented every frame and can be used to animate things that never pause such as menus.  Meanwhile, the game world will update based on the virtual set of time values and all game objects will stop moving when the game is paused.

Implementation: Fixed Time-Stepping

Fixed time-stepping is itself sometimes a difficult concept to grasp, and proper implementations are often difficult to get right.  Fixed time-stepping refers to decoupling the logical updates from the rendering (this form of decoupling is unrelated to multi-threaded rendering), executing logical updates only after a certain fixed amount of time has passed while rendering as often as possible, regardless of how much time has passed.  There are several important reasons why this is done.  Firstly, logical updates are where physics, AI, scripts, etc., are run.  By spacing these updates out over a few frames rather than every frame CPU usage is reduced and the overall framerate can increase.  Secondly, and most importantly, physics simulations require a constant update time each time they are run in order to avoid exploding scenes and other buggy behavior.  Finally, fixed time steps are essential for keeping synchronization over network play as close as possible.  While it is still possible for clients to lose sync and there does need to be a mechanism to re-sync clients anyway, things are greatly simplified when non-interactive parts of the scene are run by fixed time steps, which all but ensures they will remain in sync for all clients.

Conceptually it can be viewed as shown in Figure 2-7.  Logical updates, in a perfect world, would happen at perfectly even intervals.  Renders happen as fast as possible, on every game loop or game cycle, which means there may be longer delays between some renders and short delays between others.

 

Figure 2-7

Unfortunately the logical updates and renders are executed on the same thread, and since renders happen every loop it is impossible to actually place a logical update anywhere except on the same intervals as the renders.  That is, you cannot have a render every loop and somehow insert a logical update half-way into the loop.  It turns out, however, that this is nothing but a conceptual problem.  Inside of the game, actual universal time doesn’t matter.  Imagine scenario 1 in which a render is delayed for 3 seconds and logical updates occur every second.  In a perfect world, we would wait 1 second, perform 1 logical update, wait another second and update logic, wait 1 more second and update logic, and then render.  But to the player who is looking at the screen, this process yields exactly the same result as if we waited 3 seconds, then updated the logic 3 times quickly, each update by 1 second, and then rendered.  The simulation has, in either case, moved forward by 3 seconds before the render, and the render itself will be identical in both scenarios.  In other words, the logical updates don’t actually need to occur at the correct times in real time—the only thing that matters is if the same number of logical updates have been executed before the render.  In practice, it looks like Figure 2-8.

 

Figure 2-8

In Figure 2-8, the logical updates occur at the same time as the renders because they are on the same thread and can only execute inside of a single game loop.  The original spacing of the logical updates is shown in grey.  Instead of executing the logical updates at arbitrary times within the game loop, we simply change the number of time the logical updates occur on each game loop.  Notice that the second logical update was pushed back a bit due to some lag, but in total 2 logical updates took place before the second render, which means the game simulation had advanced by, let’s say 2 seconds (borrowing from our previous example), which means the render still depicts the game state the same way it would have had we been able to execute the logical update at literal 1-second intervals.

Notice also that if the game loop and render execute too quickly, sometimes too little time passes to justify another logical update.  In this case 0 logical updates were issued on that game loop and the loop goes straight to rendering.  This saves on CPU usage.  Although not shown here, it can be extrapolated that 0 and 1 are not the only number of times that might be necessary to run the logical update in a single game loop.  If there is a strong lag and the delay between frames increases enough, it may be necessary to run 2, 3, or more logical updates in a single loop.  Our CTime class is going to determine for us how many times to update the logic on each game loop.  Actually performing the updates will be covered in the next chapter.  Additionally, an astute reader may have realized that in these simple examples it doesn’t make sense to render unless a logical update has taken place because you would be rendering the exact same scene with all the objects in their same locations etc.  While this is true for the simple example provided here, there is also a solution to this involving interpolation.  Again, this is handled at a higher level in the system and will be explained in detail in the next chapter, but it is worth mentioning now because in order to perform that interpolation we will need the CTime class to give us an extra value back when it calculates how many logical updates to perform.

The main question we want the CTime class to answer is how many times we need to update the logical loop each tick.  For this, a new method is added to CTime called GetFixedStepUpdateCountFromTicks().

Listing 2.10  TKFTime.cpp

    /** Gets the the number logical updates necessary for a fixed time

     *    step of the given number of system ticks as well as the fraction
     *    between logical updates where the simulation will be after
     *    updating the returned number of times. */
    u32 CTime::GetFixedStepUpdateCountFromTicks( u64 _u64Ticks,
        f32 &_f32Ratio, u64 &_u64RemainderTicks ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
      
        u32 u32Count = static_cast<u32>(u64Delta / _u64Ticks);
        u64 u64AddMe = u32Count * _u64Ticks;
        m_u64LastRealTime += u64AddMe;
        _u64RemainderTicks = u64Delta - u64AddMe;
       
        _f32Ratio = static_cast<f32>(static_cast<f64>(u64AddMe) /
            static_cast<f64>(_u64Ticks));
        return u32Count;

    }

Notice that since GetRealTime() is called directly this should not be used in conjunction with Update().  This utility function is meant to be used with UpdateBy().  Notice that after getting the real time it doesn’t directly copy that into m_u64LastRealTime.  If it did, then the next time this is called on the next frame the delta would not include the previous frame’s time.  If the deltas don’t accumulate across frames, the proper number of logical updates per frame can’t be calculated—remember that it may take several frames before a logical update is needed.  Next, notice that m_u64LastRealTime is modified by adding the count multiplied by the ticks.  The CTime class will expect you to call UpdateBy() with the same number of ticks, u32Count times.  Again, this is to remove drift.  While we will lose a few ticks to rounded off fractions now, they will be regained on later frames.  Finally, when the logical update has executed u32Count number of times, each time adding _u64Ticks to its current simulation time, the logical update’s time will be a tick that is a multiple of _u64Ticks but the real game time will be somewhere between that time and the next logical update (the logical update’s time + _u64Ticks).  _f32Ratio is calculated to represent the fraction of the real time between logical updates.  This will be useful in the next chapter.  The actual number of ticks between logical ticks is stored in the return-by-reference parameter _u64RemainderTicks, which will later be needed to update the render time for each cycle.

 

 

L. Spiro


#2L. Spiro

Posted 14 July 2013 - 11:48 PM

Time                                           

Keeping track of time is important for any game, and it can often be difficult to do just right, as there are many small nuances to handle that, when done improperly, can lead to significant bugs that can be very difficult to trace and fix.  Contributing to this is the fact that, at face value, keeping track of time seems to be a very simple task, luring many into a false sense of security when implementing their timers.  This section will outline the important features a game timer should have, discuss some common pitfalls when implementing game timers, and provide a solid game timer implementation.

Important Features           

Before anything else, it is important to outline what features a game timer should have and what it should do.

▪     Drift must be minimized.  “Drift” refers to the accumulation of small amounts of error in time that cause the game’s timer to drift slowly away from what the actual game time should be.

▪     It must have some mechanism for pausing.  This will be achieved by keeping a second time accumulator that only increments when the game is not paused.

▪     It should be in a resolution higher than milliseconds.  Even though iOS devices are capped at rendering at 60 times per second, that still only leaves an accuracy of 16 (truncated) milliseconds per frame.  The framework we will create will use a resolution of microseconds.

▪     It should have features to accommodate stepping through the game logic and the rendering logic at different rates, effectively decoupling them.

o    Note that this type of decoupling is not related to multi-threaded rendering—moving the renderer onto its own thread is an entirely different subject.

▪     It must provide an interface for making it easy to get the delta time since the last frame in both microseconds and as a floating-point value.  Floating-point values are better for physics simulations while microseconds are better for things that need to accumulate how much time has passed accurately and with as little drift as possible.

o    Again, a focus on avoiding drift will be an important factor in how this is actually implemented.

▪     Overflow of the timers should be impractical.  “Overflow” refers to the integral counter used to tell time accumulating beyond the limits of its integral form (as imposed by computer science) and wrapping back around to or past 0, which would trick sub-systems into thinking that a massive amount of time has passed since the last update (due to the unsigned nature of the integrals we will be using) which will effectively freeze most systems and cause unpredictable havoc with others.  Given enough time, any timer will eventually overflow, so our objective is to make that it takes an unreasonable time to do so, for example over 100 years.

Common Pitfalls

If at first implementing a timer seems straightforward, reading over the previous section’s list of important features may make it more obvious that there is a lot of room for error, and these errors can be very hard to detect and trace, especially if they only occur over a long period of time.

▪     Using 32-bit floating-point values to store time is one of the biggest follies an inexperienced programmer will make, as due to its decreasing precision with higher numbers, your game will become noticeably choppier in a short amount of time, from somewhat choppy after a few hours to heavily choppy after a few days.
More advanced readers may instead use 64-bit floating-point values to accumulate time, but this has more subtle flaws, particularly related to drift.  Small floating-point errors will accumulate over time, and while it may not be noticeable for a while it is also just as easy to accumulate time in the system’s native resolution with an unsigned 64-bit integer and eliminate drift to the best of the hardware’s capability.  64-bit doubles can still be used, but they should be re-derived each frame instead of accumulated directly.

▪     Updating the time more than once per game cycle, or in the most extreme case always getting the current time whenever you need it for any calculation is another common pitfall.  Related time systems should be updated at specific intervals and only at those intervals.  Examples of related time systems are those used for the sound thread, input timestamps, and the game’s primary timer.
In the event of input events, the timer for that system will be updated on each event it catches.  For the sound thread, the timer will be updated once each time the sound manager updates.  All sounds in it will then be advanced by that same amount of time to prevent any of them from updating faster or slower than the other sounds in the manager.
As for the game’s main timer, this should be updated once and only once on each game cycle, or game loop.  Imagine the worst-case scenario in which the time is read from the system every time “time” is needed in an equation.  If 2 balls fall from the same height at the same time, they should fall side-by-side.  However, if the delta time—that is the time since the last update of each ball—is obtained by always checking the current system time, any hiccups in the physics system could trick one ball into believing it has fallen for a longer time on that frame and sneak ahead of the other ball.

▪     Using milliseconds instead of microseconds is a minor pitfall and may not show a significant change on iOS devices, but using microseconds is just as easy and just more accurate.  As we will be using a macro for the resolution of our timers, however, any timer resolution will be easy to test in the end.

▪     Using a fixed framerate (such as always updating by 16.6 milliseconds, which will show slowdown when too many objects are on the screen etc.) is itself not a pitfall—it is entirely appropriate for some single-player games.  The pitfall is when you make assumptions based on the framerate, especially when those assumptions impact other parts of the engine.  There is an appropriate way to get a fixed framerate related only to the timer system and should be preferred over any assumptions that may impact other parts of the game such as the physics system.  This method will be explained later.

Implementation: Basics                  

With the features went want to have and the pitfalls we want to avoid in mind we can begin our implementation of a timer class.  The file will be part of the TKFoundation library and will be named TKFTime.  The class declaration begins with the basic members we need to keep track of time without drift and a wrapper function for getting the current system time in its own native resolution.  This is the time we will be accumulating.

 

Listing 2.3  TKFTime.h

namespace tkf {

    class CTime {
    public :
        CTime();

       
        // == Functions.
        /** Gets the real system time in its own resolution.
         *    Not to be used for any reason except random-number
         *    seeding and internal use.  Never use in game code! */
        u64                        GetRealTime() const;
   
    protected :
        // == Members.
        /** The time resolution. */
        u64                        m_f64Resolution;
       
        /** The time accumulator which always starts at 0. */
        u64                        m_u64CurTime;
       
        /** The time of the last update. */
        u64                        m_u64LastTime;
       
        /** The last system time recorded. */
        u64                        m_u64LastRealTime;
    };
 

}      // namespace tkf

TKFTime.cpp contains only the important includes, the constructor, and the implementation of GetRealTime().

Listing 2.4  TKFTime.cpp

#include "TKFTime.h"

#include <mach/mach.h>
#include <mach/mach_time.h>
   
namespace tkf {
   
    CTime::CTime() :
        m_u64CurTime( 0ULL ),
        m_u64LastTime( 0ULL ) {
        // Get the resolution.
        mach_timebase_info_data_t mtidTimeData;
        ::mach_timebase_info( &mtidTimeData );
        m_f64Resolution = static_cast<f64>(mtidTimeData.numer) /
            static_cast<f64>(mtidTimeData.denom) / 1000.0;
             
        m_u64LastRealTime = GetRealTime();
    }
   
    // == Functions.
    /** Gets the real system time in its own resolution.
     *    Not to be used for any reason except random-number
     *    seeding and internal use.  Never use in game code! */
    u64 CTime::GetRealTime() const {
        return ::mach_absolute_time();
    }
   

}    // namespace tkf

mach_absolute_time() returns the number of ticks since the device has been turned on and will be in a resolution native to the device.  The values returned by mach_timebase_info() provide the numerator and denominator necessary to convert the system ticks into nanoseconds.  Note that while we are using a 64-bit floating-point value for the conversion from system ticks to microseconds, we are not using it for any accumulation purposes, and as such it does not contribute to drift.  Because it is used in multiplication later it has been divided by 1,000.0 so that it converts to microseconds rather than nanoseconds.

The next step is to add accumulation methods.  This will be split into 2 functions: One that allows the number of system ticks by which to update and one that calls the former after actually determining how many ticks have passed since the last update.  By splitting the update into these 2 functions we can keep other timers as slaves to another so that as the main timer updates, the amount by which it updates can be cascaded down to other timers so that they all update by the same amount.  This will be important later.

Listing 2.5  TKFTime.cpp

    /** Calculates how many system ticks have passed

     *    since the last update and calls UpdateBy()
     *    with that value. */
    void CTime::Update( bool _bUpdateVirtuals ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
        m_u64LastRealTime = u64TimeNow;
       
        UpdateBy( u64Delta, _bUpdateVirtuals );
    }
   
    /** Updates by the given number of system ticks. */
    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;

    }

Accumulating time in system resolution is simple.  Note that inside of Update() the delta was calculated with a simple subtraction without any special-case handling for the wrap-around of the system tick counter.  Due to how machines handle integer math, this is correct, as the wrap-around case will still result in the correct delta time.

Our timer will need to return the current microseconds at any given time so it is best to calculate that value up-front.  Doing so is simple as it is just a matter of a single multiplication with the timer resolution.  The CTime class will receive a new member called m_u64CurMicros and UpdateBy() will be modified.

Listing 2.6  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);

    }

Next, we need microsecond values for the current time and for how much time has passed.  Handling this in a way that avoids drift is trickier.  Let’s consider only the case of determining the number of microseconds since the last frame, as a u64 type.  Inside of UpdateBy() we could simply convert _u64Ticks to microseconds, since that represents the amount of time that has passed since the last update.  However this always truncates and we never get back any of those truncates microseconds, which is exactly what causes drift.  Instead, microseconds since the last update must be calculated based off the raw ticks of the last update subtracted from the raw current ticks (after the update).  This will add a member to CTime called m_u64DeltaMicros, and with it UpdateBy() must be modified.

Listing 2.7  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        u64 u64LastMicros = m_u64CurMicros;
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);
        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;

    }

m_u64CurMicros and m_u64DeltaMicros can get returned by inlined methods GetCurMicros() and GetDeltaMicros(), not shown here for brevity.  Objects that want to accumulate time should accumulate with GetDeltaMicros().  Another time-related attribute that is commonly needed is the amount of time that has passed in seconds, often in 32-bit floating-point format since it is generally a small value.  This value will also be updated once inside UpdateBy() and obtained by an inlined accessor method called GetDeltaTime().

Listing 2.8  TKFTime.cpp

        …

        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;
        m_f32DeltaTime = m_u64DeltaMicros *

            static_cast<f32>(1.0 / 1000000.0);

Implementation: Pause

The time class updates in such a way as to avoid drift and overflow, and buffers common time values for fast access via inlined accessors.  The next feature to add is pausing.  This is very simple and largely a repeat of previous updating code.  Pausing is implemented via a second set of accumulators called “virtual” accumulators.  Virtual ticks will be optionally accumulated on each update, and the rest (virtual current microseconds, virtual delta microseconds, and virtual delta time) will be updated based off that in the same way the normal deltas and time values are updated.  A new set of “Virt” members are added to CTime and updated inside of UpdateBy().

Listing 2.9  TKFTime.cpp

        …

        if ( _bUpdateVirtuals ) {
            m_u64VirtCurTime += _u64Ticks;
            u64 u64VirtLastMicros = m_u64VirtCurMicros;
            m_u64VirtCurMicros = static_cast<u64>(m_u64VirtCurTime
                * m_f64Resolution);
            m_u64VirtDeltaMicros = m_u64VirtCurMicros - u64VirtLastMicros;
            m_f32VirtDeltaTime = m_u64VirtDeltaMicros *
                static_cast<f32>(1.0 / 1000000.0);

        }

Additionally, inlined accessors are added to access these virtual timers (not shown here for brevity).  When objects can be paused, they should always exclusively use the virtual set of time values.  The standard time values are incremented every frame and can be used to animate things that never pause such as menus.  Meanwhile, the game world will update based on the virtual set of time values and all game objects will stop moving when the game is paused.

Implementation: Fixed Time-Stepping

Fixed time-stepping is itself sometimes a difficult concept to grasp, and proper implementations are often difficult to get right.  Fixed time-stepping refers to decoupling the logical updates from the rendering (this form of decoupling is unrelated to multi-threaded rendering), executing logical updates only after a certain fixed amount of time has passed while rendering as often as possible, regardless of how much time has passed.  There are several important reasons why this is done.  Firstly, logical updates are where physics, AI, scripts, etc., are run.  By spacing these updates out over a few frames rather than every frame CPU usage is reduced and the overall framerate can increase.  Secondly, and most importantly, physics simulations require a constant update time each time they are run in order to avoid exploding scenes and other buggy behavior.  Finally, fixed time steps are essential for keeping synchronization over network play as close as possible.  While it is still possible for clients to lose sync and there does need to be a mechanism to re-sync clients anyway, things are greatly simplified when non-interactive parts of the scene are run by fixed time steps, which all but ensures they will remain in sync for all clients.

Conceptually it can be viewed as shown in Figure 2-7.  Logical updates, in a perfect world, would happen at perfectly even intervals.  Renders happen as fast as possible, on every game loop or game cycle, which means there may be longer delays between some renders and short delays between others.

 

Figure 2-7

Unfortunately the logical updates and renders are executed on the same thread, and since renders happen every loop it is impossible to actually place a logical update anywhere except on the same intervals as the renders.  That is, you cannot have a render every loop and somehow insert a logical update half-way into the loop.  It turns out, however, that this is nothing but a conceptual problem.  Inside of the game, actual universal time doesn’t matter.  Imagine scenario 1 in which a render is delayed for 3 seconds and logical updates occur every second.  In a perfect world, we would wait 1 second, perform 1 logical update, wait another second and update logic, wait 1 more second and update logic, and then render.  But to the player who is looking at the screen, this process yields exactly the same result as if we waited 3 seconds, then updated the logic 3 times quickly, each update by 1 second, and then rendered.  The simulation has, in either case, moved forward by 3 seconds before the render, and the render itself will be identical in both scenarios.  In other words, the logical updates don’t actually need to occur at the correct times in real time—the only thing that matters is if the same number of logical updates have been executed before the render.  In practice, it looks like Figure 2-8.

 

Figure 2-8

In Figure 2-8, the logical updates occur at the same time as the renders because they are on the same thread and can only execute inside of a single game loop.  The original spacing of the logical updates is shown in grey.  Instead of executing the logical updates at arbitrary times within the game loop, we simply change the number of time the logical updates occur on each game loop.  Notice that the second logical update was pushed back a bit due to some lag, but in total 2 logical updates took place before the second render, which means the game simulation had advanced by, let’s say 2 seconds (borrowing from our previous example), which means the render still depicts the game state the same way it would have had we been able to execute the logical update at literal 1-second intervals.

Notice also that if the game loop and render execute too quickly, sometimes too little time passes to justify another logical update.  In this case 0 logical updates were issued on that game loop and the loop goes straight to rendering.  This saves on CPU usage.  Although not shown here, it can be extrapolated that 0 and 1 are not the only number of times that might be necessary to run the logical update in a single game loop.  If there is a strong lag and the delay between frames increases enough, it may be necessary to run 2, 3, or more logical updates in a single loop.  Our CTime class is going to determine for us how many times to update the logic on each game loop.  Actually performing the updates will be covered in the next chapter.  Additionally, an astute reader may have realized that in these simple examples it doesn’t make sense to render unless a logical update has taken place because you would be rendering the exact same scene with all the objects in their same locations etc.  While this is true for the simple example provided here, there is also a solution to this involving interpolation.  Again, this is handled at a higher level in the system and will be explained in detail in the next chapter, but it is worth mentioning now because in order to perform that interpolation we will need the CTime class to give us an extra value back when it calculates how many logical updates to perform.

The main question we want the CTime class to answer is how many times we need to update the logical loop each tick.  For this, a new method is added to CTime called GetFixedStepUpdateCountFromTicks().

Listing 2.10  TKFTime.cpp

    /** Gets the the number logical updates necessary for a fixed time

     *    step of the given number of system ticks as well as the fraction
     *    between logical updates where the simulation will be after
     *    updating the returned number of times. */
    u32 CTime::GetFixedStepUpdateCountFromTicks( u64 _u64Ticks,
        f32 &_f32Ratio, u64 &_u64RemainderTicks ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
      
        u32 u32Count = static_cast<u32>(u64Delta / _u64Ticks);
        u64 u64AddMe = u32Count * _u64Ticks;
        m_u64LastRealTime += u64AddMe;
        _u64RemainderTicks = u64Delta - u64AddMe;
       
        _f32Ratio = static_cast<f32>(static_cast<f64>(u64AddMe) /
            static_cast<f64>(_u64Ticks));
        return u32Count;

    }

Notice that since GetRealTime() is called directly this should not be used in conjunction with Update().  This utility function is meant to be used with UpdateBy().  Notice that after getting the real time it doesn’t directly copy that into m_u64LastRealTime.  If it did, then the next time this is called on the next frame the delta would not include the previous frame’s time.  If the deltas don’t accumulate across frames, the proper number of logical updates per frame can’t be calculated—remember that it may take several frames before a logical update is needed.  Next, notice that m_u64LastRealTime is modified by adding the count multiplied by the ticks.  The CTime class will expect you to call UpdateBy() with the same number of ticks, u32Count times.  Again, this is to remove drift.  While we will lose a few ticks to rounded off fractions now, they will be regained on later frames.  Finally, when the logical update has executed u32Count number of times, each time adding _u64Ticks to its current simulation time, the logical update’s time will be a tick that is a multiple of _u64Ticks but the real game time will be somewhere between that time and the next logical update (the logical update’s time + _u64Ticks).  _f32Ratio is calculated to represent the fraction of the real time between logical updates.  This will be useful in the next chapter.  The actual number of ticks between logical ticks is stored in the return-by-reference parameter _u64RemainderTicks, which will later be needed to update the render time for each cycle.

 

 

L. Spiro


#1L. Spiro

Posted 14 July 2013 - 11:37 PM

Time                                           

Keeping track of time is important for any game, and it can often be difficult to do just right, as there are many small nuances to handle that, when done improperly, can lead to significant bugs that can be very difficult to trace and fix.  Contributing to this is the fact that, at face value, keeping track of time seems to be a very simple task, luring many into a false sense of security when implementing their timers.  This section will outline the important features a game timer should have, discuss some common pitfalls when implementing game timers, and provide a solid game timer implementation.

Important Features           

Before anything else, it is important to outline what features a game timer should have and what it should do.

▪     Drift must be minimized.  “Drift” refers to the accumulation of small amounts of error in time that cause the game’s timer to drift slowly away from what the actual game time should be.

▪     It must have some mechanism for pausing.  This will be achieved by keeping a second time accumulator that only increments when the game is not paused.

▪     It should be in a resolution higher than milliseconds.  Even though iOS devices are capped at rendering at 60 times per second, that still only leaves an accuracy of 16 (truncated) milliseconds per frame.  The framework we will create will use a resolution of microseconds.

▪     It should have features to accommodate stepping through the game logic and the rendering logic at different rates, effectively decoupling them.

o    Note that this type of decoupling is not related to multi-threaded rendering—moving the renderer onto its own thread is an entirely different subject.

▪     It must provide an interface for making it easy to get the delta time since the last frame in both microseconds and as a floating-point value.  Floating-point values are better for physics simulations while microseconds are better for things that need to accumulate how much time has passed accurately and with as little drift as possible.

o    Again, a focus on avoiding drift will be an important factor in how this is actually implemented.

▪     Overflow of the timers should be impractical.  “Overflow” refers to the integral counter used to tell time accumulating beyond the limits of its integral form (as imposed by computer science) and wrapping back around to or past 0, which would trick sub-systems into thinking that a massive amount of time has passed since the last update (due to the unsigned nature of the integrals we will be using) which will effectively freeze most systems and cause unpredictable havoc with others.  Given enough time, any timer will eventually overflow, so our objective is to make that it takes an unreasonable time to do so, for example over 100 years.

Common Pitfalls

If at first implementing a timer seems straightforward, reading over the previous section’s list of important features may make it more obvious that there is a lot of room for error, and these errors can be very hard to detect and trace, especially if they only occur over a long period of time.

▪     Using 32-bit floating-point values to store time is one of the biggest follies an inexperienced programmer will make, as due to its decreasing precision with higher numbers, your game will become noticeably choppier in a short amount of time, from somewhat choppy after a few hours to heavily choppy after a few days.
More advanced readers may instead use 64-bit floating-point values to accumulate time, but this has more subtle flaws, particularly related to drift.  Small floating-point errors will accumulate over time, and while it may not be noticeable for a while it is also just as easy to accumulate time in the system’s native resolution with an unsigned 64-bit integer and eliminate drift to the best of the hardware’s capability.  64-bit doubles can still be used, but they should be re-derived each frame instead of accumulated directly.

▪     Updating the time more than once per game cycle, or in the most extreme case always getting the current time whenever you need it for any calculation is another common pitfall.  Related time systems should be updated at specific intervals and only at those intervals.  Examples of related time systems are those used for the sound thread, input timestamps, and the game’s primary timer.
In the event of input events, the timer for that system will be updated on each event it catches.  For the sound thread, the timer will be updated once each time the sound manager updates.  All sounds in it will then be advanced by that same amount of time to prevent any of them from updating faster or slower than the other sounds in the manager.
As for the game’s main timer, this should be updated once and only once on each game cycle, or game loop.  Imagine the worst-case scenario in which the time is read from the system every time “time” is needed in an equation.  If too balls fall from the same height at the same time, they should fall side-by-side.  However, if the delta time—that is the time since the last update of each ball—is obtained by always checking the current system time, any hiccups in the physics system could trick one ball into believing it has fallen for a longer time on that frame and sneak ahead of the other ball.

▪     Using milliseconds instead of microseconds is a minor pitfall and may not show a significant change on iOS devices, but using microseconds is just as easy and just more accurate.  As we will be using a macro for the resolution of our timers, however, any timer resolution will be easy to test in the end.

▪     Using a fixed framerate (such as always updating by 16.6 milliseconds, which will show slowdown when too many objects are on the screen etc.) is itself not a pitfall—it is entirely appropriate for some single-player games.  The pitfall is when you make assumptions based on the framerate, especially when those assumptions impact other parts of the engine.  There is an appropriate way to get a fixed framerate related only to the timer system and should be preferred over any assumptions that may impact other parts of the game such as the physics system.  This method will be explained later.

Implementation: Basics                  

With the features went want to have and the pitfalls we want to avoid in mind we can begin our implementation of a timer class.  The file will be part of the TKFoundation library and will be named TKFTime.  The class declaration begins with the basic members we need to keep track of time without drift and a wrapper function for getting the current system time in its own native resolution.  This is the time we will be accumulating.

 

Listing 2.3  TKFTime.h

namespace tkf {

    class CTime {
    public :
        CTime();

       
        // == Functions.
        /** Gets the real system time in its own resolution.
         *    Not to be used for any reason except random-number
         *    seeding and internal use.  Never use in game code! */
        u64                        GetRealTime() const;
   
    protected :
        // == Members.
        /** The time resolution. */
        u64                        m_f64Resolution;
       
        /** The time accumulator which always starts at 0. */
        u64                        m_u64CurTime;
       
        /** The time of the last update. */
        u64                        m_u64LastTime;
       
        /** The last system time recorded. */
        u64                        m_u64LastRealTime;
    };
 

}      // namespace tkf

TKFTime.cpp contains only the important includes, the constructor, and the implementation of GetRealTime().

Listing 2.4  TKFTime.cpp

#include "TKFTime.h"

#include <mach/mach.h>
#include <mach/mach_time.h>
   
namespace tkf {
   
    CTime::CTime() :
        m_u64CurTime( 0ULL ),
        m_u64LastTime( 0ULL ) {
        // Get the resolution.
        mach_timebase_info_data_t mtidTimeData;
        ::mach_timebase_info( &mtidTimeData );
        m_f64Resolution = static_cast<f64>(mtidTimeData.numer) /
            static_cast<f64>(mtidTimeData.denom) / 1000.0;
             
        m_u64LastRealTime = GetRealTime();
    }
   
    // == Functions.
    /** Gets the real system time in its own resolution.
     *    Not to be used for any reason except random-number
     *    seeding and internal use.  Never use in game code! */
    u64 CTime::GetRealTime() const {
        return ::mach_absolute_time();
    }
   

}    // namespace tkf

mach_absolute_time() returns the number of ticks since the device has been turned on and will be in a resolution native to the device.  The values returned by mach_timebase_info() provide the numerator and denominator necessary to convert the system ticks into nanoseconds.  Note that while we are using a 64-bit floating-point value for the conversion from system ticks to microseconds, we are not using it for any accumulation purposes, and as such it does not contribute to drift.  Because it is used in multiplication later it has been divided by 1,000.0 so that it converts to microseconds rather than nanoseconds.

The next step is to add accumulation methods.  This will be split into 2 functions: One that allows the number of system ticks by which to update and one that calls the former after actually determining how many ticks have passed since the last update.  By splitting the update into these 2 functions we can keep other timers as slaves to another so that as the main timer updates, the amount by which it updates can be cascaded down to other timers so that they all update by the same amount.  This will be important later.

Listing 2.5  TKFTime.cpp

    /** Calculates how many system ticks have passed

     *    since the last update and calls UpdateBy()
     *    with that value. */
    void CTime::Update( bool _bUpdateVirtuals ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
        m_u64LastRealTime = u64TimeNow;
       
        UpdateBy( u64Delta, _bUpdateVirtuals );
    }
   
    /** Updates by the given number of system ticks. */
    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;

    }

Accumulating time in system resolution is simple.  Note that inside of Update() the delta was calculated with a simple subtraction without any special-case handling for the wrap-around of the system tick counter.  Due to how machines handle integer math, this is correct, as the wrap-around case will still result in the correct delta time.

Our timer will need to return the current microseconds at any given time so it is best to calculate that value up-front.  Doing so is simple as it is just a matter of a single multiplication with the timer resolution.  The CTime class will receive a new member called m_u64CurMicros and UpdateBy() will be modified.

Listing 2.6  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);

    }

Next, we need microsecond values for the current time and for how much time has passed.  Handling this in a way that avoids drift is trickier.  Let’s consider only the case of determining the number of microseconds since the last frame, as a u64 type.  Inside of UpdateBy() we could simply convert _u64Ticks to microseconds, since that represents the amount of time that has passed since the last update.  However this always truncates and we never get back any of those truncates microseconds, which is exactly what causes drift.  Instead, microseconds since the last update must be calculated based off the raw ticks of the last update subtracted from the raw current ticks (after the update).  This will add a member to CTime called m_u64DeltaMicros, and with it UpdateBy() must be modified.

Listing 2.7  TKFTime.cpp

    /** Updates by the given number of system ticks. */

    void CTime::UpdateBy( u64 _u64Ticks, bool _bUpdateVirtuals ) {
        m_u64LastTime = m_u64CurTime;
        m_u64CurTime += _u64Ticks;
       
        u64 u64LastMicros = m_u64CurMicros;
        m_u64CurMicros = static_cast<u64>(m_u64CurTime * m_f64Resolution);
        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;

    }

m_u64CurMicros and m_u64DeltaMicros can get returned by inlined methods GetCurMicros() and GetDeltaMicros(), not shown here for brevity.  Objects that want to accumulate time should accumulate with GetDeltaMicros().  Another time-related attribute that is commonly needed is the amount of time that has passed in seconds, often in 32-bit floating-point format since it is generally a small value.  This value will also be updated once inside UpdateBy() and obtained by an inlined accessor method called GetDeltaTime().

Listing 2.8  TKFTime.cpp

        …

        m_u64DeltaMicros = m_u64CurMicros - u64LastMicros;
        m_f32DeltaTime = m_u64DeltaMicros *

            static_cast<f32>(1.0 / 1000000.0);

Implementation: Pause

The time class updates in such a way as to avoid drift and overflow, and buffers common time values for fast access via inlined accessors.  The next feature to add is pausing.  This is very simple and largely a repeat of previous updating code.  Pausing is implemented via a second set of accumulators called “virtual” accumulators.  Virtual ticks will be optionally accumulated on each update, and the rest (virtual current microseconds, virtual delta microseconds, and virtual delta time) will be updated based off that in the same way the normal deltas and time values are updated.  A new set of “Virt” members are added to CTime and updated inside of UpdateBy().

Listing 2.9  TKFTime.cpp

        …

        if ( _bUpdateVirtuals ) {
            m_u64VirtCurTime += _u64Ticks;
            u64 u64VirtLastMicros = m_u64VirtCurMicros;
            m_u64VirtCurMicros = static_cast<u64>(m_u64VirtCurTime
                * m_f64Resolution);
            m_u64VirtDeltaMicros = m_u64VirtCurMicros - u64VirtLastMicros;
            m_f32VirtDeltaTime = m_u64VirtDeltaMicros *
                static_cast<f32>(1.0 / 1000000.0);

        }

Additionally, inlined accessors are added to access these virtual timers (not shown here for brevity).  When objects can be paused, they should always exclusively use the virtual set of time values.  The standard time values are incremented every frame and can be used to animate things that never pause such as menus.  Meanwhile, the game world will update based on the virtual set of time values and all game objects will stop moving when the game is paused.

Implementation: Fixed Time-Stepping

Fixed time-stepping is itself sometimes a difficult concept to grasp, and proper implementations are often difficult to get right.  Fixed time-stepping refers to decoupling the logical updates from the rendering (this form of decoupling is unrelated to multi-threaded rendering), executing logical updates only after a certain fixed amount of time has passed while rendering as often as possible, regardless of how much time has passed.  There are several important reasons why this is done.  Firstly, logical updates are where physics, AI, scripts, etc., are run.  By spacing these updates out over a few frames rather than every frame CPU usage is reduced and the overall framerate can increase.  Secondly, and most importantly, physics simulations require a constant update time each time they are run in order to avoid exploding scenes and other buggy behavior.  Finally, fixed time steps are essential for keeping synchronization over network play as close as possible.  While it is still possible for clients to lose sync and there does need to be a mechanism to re-sync clients anyway, things are greatly simplified when non-interactive parts of the scene are run by fixed time steps, which all but ensures they will remain in sync for all clients.

Conceptually it can be viewed as shown in Figure 2-7.  Logical updates, in a perfect world, would happen at perfectly even intervals.  Renders happen as fast as possible, on every game loop or game cycle, which means there may be longer delays between some renders and short delays between others.

Figure 2-7

Unfortunately the logical updates and renders are executed on the same thread, and since renders happen every loop it is impossible to actually place a logical update anywhere except on the same intervals as the renders.  That is, you cannot have a render every loop and somehow insert a logical update half-way into the loop.  It turns out, however, that this is nothing but a conceptual problem.  Inside of the game, actual universal time doesn’t matter.  Imagine scenario 1 in which a render is delayed for 3 seconds and logical updates occur every second.  In a perfect world, we would wait 1 second, perform 1 logical update, wait another second and update logic, wait 1 more second and update logic, and then render.  But to the player who is looking at the screen, this process yields exactly the same result as if we waited 3 seconds, then updated the logic 3 times quickly, each update by 1 second, and then rendered.  The simulation has, in either case, moved forward by 3 seconds before the render, and the render itself will be identical in both scenarios.  In other words, the logical updates don’t actually need to occur at the correct times in real time—the only thing that matters is if the same number of logical updates have been executed before the render.  In practice, it looks like Figure 2-8.

Figure 2-8

In Figure 2-8, the logical updates occur at the same time as the renders because they are on the same thread and can only execute inside of a single game loop.  The original spacing of the logical updates is shown in grey.  Instead of executing the logical updates at arbitrary times within the game loop, we simply change the number of time the logical updates occur on each game loop.  Notice that the second logical update was pushed back a bit due to some lag, but in total 2 logical updates took place before the second render, which means the game simulation had advanced by, let’s say 2 seconds (borrowing from our previous example), which means the render still depicts the game state the same way it would have had we been able to execute the logical update at literal 1-second intervals.

Notice also that if the game loop and render execute too quickly, sometimes too little time passes to justify another logical update.  In this case 0 logical updates were issued on that game loop and the loop goes straight to rendering.  This saves on CPU usage.  Although not shown here, it can be extrapolated that 0 and 1 are not the only number of times that might be necessary to run the logical update in a single game loop.  If there is a strong lag and the delay between frames increases enough, it may be necessary to run 2, 3, or more logical updates in a single loop.  Our CTime class is going to determine for us how many times to update the logic on each game loop.  Actually performing the updates will be covered in the next chapter.  Additionally, an astute reader may have realized that in these simple examples it doesn’t make sense to render unless a logical update has taken place because you would be rendering the exact same scene with all the objects in their same locations etc.  While this is true for the simple example provided here, there is also a solution to this involving interpolation.  Again, this is handled at a higher level in the system and will be explained in detail in the next chapter, but it is worth mentioning now because in order to perform that interpolation we will need the CTime class to give us an extra value back when it calculates how many logical updates to perform.

The main question we want the CTime class to answer is how many times we need to update the logical loop each tick.  For this, a new method is added to CTime called GetFixedStepUpdateCountFromTicks().

Listing 2.10  TKFTime.cpp

    /** Gets the the number logical updates necessary for a fixed time

     *    step of the given number of system ticks as well as the fraction
     *    between logical updates where the simulation will be after
     *    updating the returned number of times. */
    u32 CTime::GetFixedStepUpdateCountFromTicks( u64 _u64Ticks,
        f32 &_f32Ratio, u64 &_u64RemainderTicks ) {
        u64 u64TimeNow = GetRealTime();
        u64 u64Delta = u64TimeNow - m_u64LastRealTime;
      
        u32 u32Count = static_cast<u32>(u64Delta / _u64Ticks);
        u64 u64AddMe = u32Count * _u64Ticks;
        m_u64LastRealTime += u64AddMe;
        _u64RemainderTicks = u64Delta - u64AddMe;
       
        _f32Ratio = static_cast<f32>(static_cast<f64>(u64AddMe) /
            static_cast<f64>(_u64Ticks));
        return u32Count;

    }

Notice that since GetRealTime() is called directly this should not be used in conjunction with Update().  This utility function is meant to be used with UpdateBy().  Notice that after getting the real time it doesn’t directly copy that into m_u64LastRealTime.  If it did, then the next time this is called on the next frame the delta would not include the previous frame’s time.  If the deltas don’t accumulate across frames, the proper number of logical updates per frame can’t be calculated—remember that it may take several frames before a logical update is needed.  Next, notice that m_u64LastRealTime is modified by adding the count multiplied by the ticks.  The CTime class will expect you to call UpdateBy() with the same number of ticks, u32Count times.  Again, this is to remove drift.  While we will lose a few ticks to rounded off fractions now, they will be regained on later frames.  Finally, when the logical update has executed u32Count number of times, each time adding _u64Ticks to its current simulation time, the logical update’s time will be a tick that is a multiple of _u64Ticks but the real game time will be somewhere between that time and the next logical update (the logical update’s time + _u64Ticks).  _f32Ratio is calculated to represent the fraction of the real time between logical updates.  This will be useful in the next chapter.  The actual number of ticks between logical ticks is stored in the return-by-reference parameter _u64RemainderTicks, which will later be needed to update the render time for each cycle.

 

 

L. Spiro


PARTNERS