# Algorithm Fixed timestep glitch.

## Recommended Posts

After reading Mr. @L Spiro's excellent article on fixed timestep, I was convinced that my own implementation was incorrect, suffering from very occasional frame skip.  After looking closely at the numbers, I found one source of frame skip.  Every 40 seconds or so, I get an extra Draw(), at the cost of an Update().  It occurs when the interpolation factor approaches 1.  It's not always visually discernible.

I'm drawing at 144Hz (not ideal, but the only refresh rate supported by this display)  and my update rate is set to half that.

Adding a dozen or so ticks to the accumulated time each loop iteration fixes the issue, but that's not a fix.. it's a hack.


FrameTime = Timer.ElapsedQPCTicks;
Accumulation += FrameTime;

//
// Update
//
while (Accumulation > UpdateTicks) // @72hz UpdateTicks = 138888
{
Update(UpdateTicks);
Accumulation -= UpdateTicks;
}

//
// Draw
//
Draw(Accumulation / (double)UpdateTicks);
Swapchain.TryPresent(DXGI.PresentFlags.None, 0, null);

Values shown are Int64/Long

-- ROGRat

##### Share on other sites
1 hour ago, ROGRat said:

while﻿ ﻿(Accumulation >= ﻿UpdateTicks﻿﻿﻿)﻿﻿﻿﻿﻿﻿﻿﻿

That is one issue.  Draw() should never be passed 1.0; that case should always be treated as 0.0 (the start of a new frame), so Update() should be called when “Accumulation” is greater than or equal to “UpdateTicks”.

Any jittering beyond this is likely due to some other code related to interpolating between frames (interpolating matrices etc.)

L. Spiro

##### Share on other sites

I agree with L Spiro that logically you should do the update when accumulation >= updateticks, however whether this is the cause of your visual glitch I don't know, because using the stale tick with fraction set to 1.0 should be the same visual result as the next tick with fraction set to 0.0 (I think!). However the lack of an update when expected could be causing something jarring in some other part of your code?

If you can you should make some logs of the update / frame updates and the times and fractions, to try and pinpoint where there is a problem, if indeed this is the source of the problem.

There are also a number of other very significant causes of jitter / glitches aside from the ticking code and the interpolation code, especially that the time reported by the OS is not usually the render time, but the submit time for the frame. There is a little discussion about this in the final part of my post here, the references and the comments:

##### Share on other sites

Hey guys, thanks very much for taking the time to have a look at this, I appreciate it.

@L Spiro -- I'm glad you mentioned the >= case because I put it on the backburner a while ago, thinking it was contributing to the frame skip but at the same time, saw that a potential Update() was being missed.  I wasn't aware that passing in 1 was a problem and have the necessary adjustments, thanks for that.

@lawnjelly I did as you suggested and added logging, something I really should have done earlier.  Aside from revealing why I'm losing an Update every so often (in addition to L. Spiro's point above), it highlighted the timing issue you touched on.  Up until now I had been displaying the Frametime onscreen at runtime, but it didn't show the large variations in that time which are directly responsible for frame loss.

I kept tabs on the highest, lowest and average frame time over the course of a 10 minute run.  For the sake of getting this timestep issue resolved, I've just got a couple of sprites moving back and forth, some debug text  and have cut interpolation back to just a translate matrix.

Highest was 510561, Lowest 8430 and Average 69426.

I don't know whether the out-of-band values are the result of QPC misbehaving (it appears that the more frequently you call QPC, the larger the margin of error), or whether it's due to my thread being hoisted by the scheduler but I'm not familiar with people capping or shaping timer values beyond ensuring they're not zero or negative, as QPC does on some systems.

Is there an established method for dealing with those values?  The few remedies I did try (like substituting high and low values with the average frame time) just didn't feel right.

Here's an excerpt from my log which shows why I'm missing updates when the interpolation factor is near 0.


FrameT: 69191	Accumulate: 66888	Alpha: 0.4815967	Draws: 7329	Updates: 3663
FrameT: 68145	Accumulate: 135033	Alpha: 0.9722438	Draws: 7330	Updates: 3663

FrameT: 75063	Accumulate: 71208	Alpha: 0.5127009	Draws: 7331	Updates: 3664

FrameT: 68592	Accumulate: 912		Alpha: 0.006566442	Draws: 7332	Updates: 3665
FrameT: 65353	Accumulate: 66265	Alpha: 0.477111		Draws: 7333	Updates: 3665
FrameT: 72306	Accumulate: 138571	Alpha: 0.9977176	Draws: 7334	Updates: 3665

FrameT: 71837	Accumulate: 71520	Alpha: 0.5149473	Draws: 7335	Updates: 3666
FrameT: 66574	Accumulate: 138094	Alpha: 0.9942831	Draws: 7336	Updates: 3666

FrameT: 72569	Accumulate: 71775	Alpha: 0.5167833	Draws: 7337	Updates: 3667
FrameT: 63456	Accumulate: 135231	Alpha: 0.9736694	Draws: 7338	Updates: 3667

FrameT: 69301	Accumulate: 65644	Alpha: 0.4726398	Draws: 7339	Updates: 3668

FrameT: 74165	Accumulate: 921		Alpha: 0.006631243	Draws: 7340	Updates: 3669
FrameT: 66417	Accumulate: 67338	Alpha: 0.4848367	Draws: 7341	Updates: 3669

FrameT: 72052	Accumulate: 502		Alpha: 0.003614423	Draws: 7342	Updates: 3670
FrameT: 64242	Accumulate: 64744	Alpha: 0.4661598	Draws: 7343	Updates: 3670
FrameT: 69928	Accumulate: 134672	Alpha: 0.9696446	Draws: 7344	Updates: 3670

FrameT: 69455	Accumulate: 65239	Alpha: 0.4697238	Draws: 7345	Updates: 3671

FrameT: 74134	Accumulate: 485		Alpha: 0.003492022	Draws: 7346	Updates: 3672
FrameT: 67106	Accumulate: 67591	Alpha: 0.4866583	Draws: 7347	Updates: 3672
FrameT: 69110	Accumulate: 136701	Alpha: 0.9842535	Draws: 7348	Updates: 3672

FrameT: 73498	Accumulate: 71311	Alpha: 0.5134425	Draws: 7349	Updates: 3673

FrameT: 68647	Accumulate: 1070	Alpha: 0.007704049	Draws: 7350	Updates: 3674
FrameT: 67602	Accumulate: 68672	Alpha: 0.4944416	Draws: 7351	Updates: 3674
FrameT: 68210	Accumulate: 136882	Alpha: 0.9855567	Draws: 7352	Updates: 3674

FrameT: 73221	Accumulate: 71215	Alpha: 0.5127513	Draws: 7353	Updates: 3675
FrameT: 65159	Accumulate: 136374	Alpha: 0.9818991	Draws: 7354	Updates: 3675

FrameT: 74278	Accumulate: 71764	Alpha: 0.5167041	Draws: 7355	Updates: 3676
FrameT: 64930	Accumulate: 136694	Alpha: 0.9842031	Draws: 7356	Updates: 3676

FrameT: 67312	Accumulate: 65118	Alpha: 0.4688526	Draws: 7357	Updates: 3677

FrameT: 74949	Accumulate: 1179	Alpha: 0.008488854	Draws: 7358	Updates: 3678
FrameT: 67914	Accumulate: 69093	Alpha: 0.4974728	Draws: 7359	Updates: 3678
FrameT: 67283	Accumulate: 136376	Alpha: 0.9819135	Draws: 7360	Updates: 3678

FrameT: 75550	Accumulate: 73038	Alpha: 0.5258769	Draws: 7361	Updates: 3679
FrameT: 62028	Accumulate: 135066	Alpha: 0.9724814	Draws: 7362	Updates: 3679

FrameT: 72305	Accumulate: 68483	Alpha: 0.4930808	Draws: 7363	Updates: 3680
FrameT: 64991	Accumulate: 133474	Alpha: 0.961019		Draws: 7364	Updates: 3680

FrameT: 75387	Accumulate: 69973	Alpha: 0.5038088	Draws: 7365	Updates: 3681

FrameT: 69627	Accumulate: 712		Alpha: 0.005126433	Draws: 7366	Updates: 3682
FrameT: 64625	Accumulate: 65337	Alpha: 0.4704294	Draws: 7367	Updates: 3682
FrameT: 70444	Accumulate: 135781	Alpha: 0.9776295	Draws: 7368	Updates: 3682

FrameT: 74890	Accumulate: 71783	Alpha: 0.5168409	Draws: 7369	Updates: 3683
FrameT: 62398	Accumulate: 134181	Alpha: 0.9661094	Draws: 7370	Updates: 3683

FrameT: 73042	Accumulate: 68335	Alpha: 0.4920152	Draws: 7371	Updates: 3684
FrameT: 65401	Accumulate: 133736	Alpha: 0.9629053	Draws: 7372	Updates: 3684

FrameT: 72797	Accumulate: 67645	Alpha: 0.4870471	Draws: 7373	Updates: 3685
FrameT: 69771	Accumulate: 137416	Alpha: 0.9894015	Draws: 7374	Updates: 3685

FrameT: 65935	Accumulate: 64463	Alpha: 0.4641366	Draws: 7375	Updates: 3686
FrameT: 72778	Accumulate: 137241	Alpha: 0.9881415	Draws: 7376	Updates: 3686

FrameT: 72291	Accumulate: 70644	Alpha: 0.5086401	Draws: 7377	Updates: 3687
FrameT: 64307	Accumulate: 134951	Alpha: 0.9716534	Draws: 7378	Updates: 3687

FrameT: 74957	Accumulate: 71020	Alpha: 0.5113473	Draws: 7379	Updates: 3688

FrameT: 68318	Accumulate: 450		Alpha: 0.003240021	Draws: 7380	Updates: 3689
FrameT: 60889	Accumulate: 61339	Alpha: 0.4416436	Draws: 7381	Updates: 3689

FrameT: 79307	Accumulate: 1758	Alpha: 0.01265768	Draws: 7382	Updates: 3690
FrameT: 68708	Accumulate: 70466	Alpha: 0.5073584	Draws: 7383	Updates: 3690
FrameT: 62191	Accumulate: 132657	Alpha: 0.9551365	Draws: 7384	Updates: 3690

FrameT: 76123	Accumulate: 69892	Alpha: 0.5032256	Draws: 7385	Updates: 3691

FrameT: 69184	Accumulate: 188		Alpha: 0.001353609	Draws: 7386	Updates: 3692
FrameT: 66033	Accumulate: 66221	Alpha: 0.4767942	Draws: 7387	Updates: 3692
FrameT: 66812	Accumulate: 133033	Alpha: 0.9578437	Draws: 7388	Updates: 3692

FrameT: 70594	Accumulate: 64739	Alpha: 0.4661238	Draws: 7389	Updates: 3693
FrameT: 68693	Accumulate: 133432	Alpha: 0.9607165	Draws: 7390	Updates: 3693

FrameT: 70182	Accumulate: 64726	Alpha: 0.4660302	Draws: 7391	Updates: 3694
FrameT: 74161	Accumulate: 138887	Alpha: 0.9999928	Draws: 7392	Updates: 3694

FrameT: 67348	Accumulate: 67347	Alpha: 0.4849015	Draws: 7393	Updates: 3695
FrameT: 70203	Accumulate: 137550	Alpha: 0.9903663	Draws: 7394	Updates: 3695

FrameT: 71742	Accumulate: 70404	Alpha: 0.5069121	Draws: 7395	Updates: 3696
FrameT: 64437	Accumulate: 134841	Alpha: 0.9708614	Draws: 7396	Updates: 3696

FrameT: 74511	Accumulate: 70464	Alpha: 0.5073441	Draws: 7397	Updates: 3697
FrameT: 62325	Accumulate: 132789	Alpha: 0.9560869	Draws: 7398	Updates: 3697

FrameT: 77072	Accumulate: 70973	Alpha: 0.5110089	Draws: 7399	Updates: 3698
FrameT: 65231	Accumulate: 136204	Alpha: 0.9806751	Draws: 7400	Updates: 3698

FrameT: 73219	Accumulate: 70535	Alpha: 0.5078552	Draws: 7401	Updates: 3699
FrameT: 68335	Accumulate: 138870	Alpha: 0.9998704	Draws: 7402	Updates: 3699

FrameT: 66736	Accumulate: 66718	Alpha: 0.4803727	Draws: 7403	Updates: 3700
FrameT: 65417	Accumulate: 132135	Alpha: 0.9513781	Draws: 7404	Updates: 3700

FrameT: 76962	Accumulate: 70209	Alpha: 0.505508		Draws: 7405	Updates: 3701
FrameT: 68379	Accumulate: 138588	Alpha: 0.99784		Draws: 7406	Updates: 3701

FrameT: 63899	Accumulate: 63599	Alpha: 0.4579157	Draws: 7407	Updates: 3702
FrameT: 74913	Accumulate: 138512	Alpha: 0.9972928	Draws: 7408	Updates: 3702

FrameT: 67676	Accumulate: 67300	Alpha: 0.4845631	Draws: 7409	Updates: 3703
FrameT: 64634	Accumulate: 131934	Alpha: 0.9499309	Draws: 7410	Updates: 3703

The accumulation variable eventually arrives at a point where it's so low that it takes 3 iterations to bring it back up to the >= required for an update.  If the timer is especially erratic at this time, interpolation jumps back and forth from close to 0 to close to 1 and movement jitters significantly.

By trimming slightly less than 138888 from the accumulator after update, it can be made to occur less often but it's just another magic number hack that is only delaying the inevitable.

Interestingly, I've been using an Intel adaptor in this system because I wanted the lower end as a yardstick.  Switching briefly to the nVidia adaptor, with G-Sync enabled, the above issue doesn't occur at all.  Now that I've got logging, I'm keen to work out how it does it.

Any further thoughts on this would be gratefully received.  🙂  Thanks again for your input.

--ROGRat

##### Share on other sites

A key point is to realise that erratic timing values / thread timing issues are nothing to do with fixed ticking scheme. You should test / debug each individually.

### Fixed timestep

For your tests on fixed ticking I personally would just go with a round number for the tick frequency based on your QPC, say 100,000. This makes it a lot easier to see what is going on at a glance.

Some variation in the number of ticks / frame is expected, due to aliasing between the timings. Given that your frame time is often about half your tick time, I don't think the variation between 1 and 3 ticks on a frame is hugely unexpected, or something to worry about. Usually the variation would be more like 2, 3, 3, 2, 2, 3, 3, 2, 3 ticks etc. More than this probably represents the erratic nature of the frame timings, rather than an error in the ticking scheme.

To test your fixed timestep you don't even need to rely on timings from the OS, you could make your own timing generator, and draw a graph of position of some constantly moving object against the input time. If the graph is smooth, your code is correct.

Given that your fixed ticking is probably working, I would take that out of the equation to examine frame timings and just use conventional 'move by deltatime * speed' to examine the frame timings on your system, and see if you still get jitter. If you can reduce jitter in the simpler system, it will also improve it in the fixed timestep version.

### Frame timings

Things to consider about frame timings:

• Make sure your logging isn't affecting it (log to a buffer rather than OutputDebugString or similar)
• Frame timings tend to be much better in fullscreen
• Frame timings are much more regular on some platforms than others

In my experience running in a window tends to give much more erratic frame timings than fullscreen. The window manager / compositor might be doing all kinds of jiggery pokery in windowed mode which cause this .. post processing, more than 1 application sharing the GPU etc. I also suspect that in fullscreen mode the OS might be more likely to give your thread 'first go' at the wait for vsync (but I can't confirm this, I know next to nothing about scheduling lol). Essentially if your thread gets some random opportunity to run within a frame (depending on what all the other processes are doing), your timings are going to be way off.

In addition any time you get from the OS may only be very roughly and indirectly related to the time at which frames will actually be displayed (submitting a frame, and that frame actually getting displayed are different things). You might for example be getting erratic timings each frame from the OS, but the actual frames may be being displayed correctly with a constant gap.

These are some relevant reading links from my blog post to digest:

Aside from all this there are some very obvious things which you should eliminate from your code in my opinion:

• Do not call OS / GPU memory allocate / deallocate routines during typical frames, do this at e.g. game start, level start. Make use of your own pools, allocate more than is necessary.
• Same with file access
• In general you should aim to have all your code run in as constant time as possible. If there are CPU intensive spikes, try to spread these over several frames / ticks.

The point about calling some of these external funcs (memory and file are obvious ones) is that they hide the fact that they can take an undefined amount of time, which can give large variation in how long your game loop takes to complete, which has knock on effects on the smoothness of everything else.

##### Share on other sites
Posted (edited)

Hey @lawnjelly, thanks very much for your comprehensive reply.  With your input, and @L Spiro's, I've been able to eliminate all frame skip (at this point) in addition to having learned a number of things along the way.

Quote

Some variation in the number of ticks / frame is expected, due to aliasing between the timings. Given that your frame time is often about half your tick time, I don't think the variation between 1 and 3 ticks on a frame is hugely unexpected, or something to worry about. Usually the variation would be more like 2, 3, 3, 2, 2, 3, 3, 2, 3 ticks etc. More than this probably represents the erratic nature of the frame timings, rather than an error in the ticking scheme.

The source of the issue I was having with an apparent -Update/+Draw is situated between the chair I'm sitting on and the keyboard in front of me.  I was expecting 2 draws for e very 1 update, completely forgetting the fact that the display-- just like every other -- isn't refreshing at exactly the value given in the DXGI. ModeDescription.  I really wanted that 2:1 ratio though, so I wrote a routine that detects the exact refresh rate (144.028 in this case), and then adjusts the Update ticks accordingly (72.014). Pretty pointless and a bit OCD, but no magic number hack 🙂

Quote

To test your fixed timestep you don't even need to rely on timings from the OS, you could make your own timing generator, and draw a graph of position of some constantly moving object against the input time. If the graph is smooth, your code is correct.

I did this by passing in the calculated monitor refresh time instead of QPC elapsed ticks and added the "dozen or so ticks" I mentioned in my OP, arriving at the refresh value reported by DirectX.  That's when I realized it was just drift I was experiencing.   Aside from being really smooth, it reinforced what L. Spiro said about not passing 1 to the Interpolator:

FrameT: 69431	Accumulate: 0	     Alpha: 0       Draws: 2     Updates: 2
FrameT: 69431	Accumulate: 69444    Alpha: 0.5     Draws: 3     Updates: 2
FrameT: 69431	Accumulate: 0	     Alpha: 0       Draws: 4     Updates: 3
FrameT: 69431	Accumulate: 69444    Alpha: 0.5     Draws: 5     Updates: 3
FrameT: 69431	Accumulate: 0	     Alpha: 0       Draws: 6     Updates: 4
FrameT: 69431	Accumulate: 69444    Alpha: 0.5     Draws: 7     Updates: 4

• Quote

• Make sure your logging isn't affecting it (log to a buffer rather than OutputDebugString or similar)
• Frame timings tend to be much better in fullscreen
• Frame timings are much more regular on some platforms than others

Yes, yes and yes.  My first attempt at logging destroyed my framerate straight up, so I switched to StreamWriter and it was fine.  I've been running in a fullscreen window for the sake of being able to access breakpoints in the debugger.  I tried connecting my desktop display to my laptop so I could see the debugger in fullscreen,  but the DVI port only does 50Hz and my monitor doesn't.

On the nVidia side, it's a lot smoother and sort of hides the problem at times..

Quote

In my experience running in a window tends to give much more erratic frame timings than fullscreen. The window manager / compositor might be doing all kinds of jiggery pokery in windowed mode which cause this .. post processing, more than 1 application sharing the GPU etc. I also suspect that in fullscreen mode the OS might be more likely to give your thread 'first go' at the wait for vsync (but I can't confirm this, I know next to nothing about scheduling lol). Essentially if your thread gets some random opportunity to run within a frame (depending on what all the other processes are doing), your timings are going to be way off.

Fullscreen mode is definitely smoother, but the two main causes behind large frame times were garbage collection and "cold start" costs imposed by JIT'ism.  Because of the immutable nature of many DirectX objects, I'm having to create, use and dispose of these objects at runtime.  Until I replace them with mutable/poolable alternatives I'm managing garbage collection manually to prevent the runtime from performing a full blocking/compacting collection.

Thanks for the links, I will check them out later.

Quote

Aside from all this there are some very obvious things which you should eliminate from your code in my opinion:

• Do not call OS / GPU memory allocate / deallocate routines during typical frames, do this at e.g. game start, level start. Make use of your own pools, allocate more than is necessary.
• Same with file access
• In general you should aim to have all your code run in as constant time as possible. If there are CPU intensive spikes, try to spread these over several frames / ticks.

I was calling GetRawInputBuffer() from Update() and the cost was showing up in the log. It's only 40 bytes/packet but it shows, and also has cold-start penalty.   I tried pre-allocating a buffer and pinning it with a GCHandle but it didn't work, so I moved it onto another thread until I sort that out.

My most allocated and longest lived type was System.String, from all the debug text I was displaying onscreen.   The main problem is the DirectX objects being New'd and Disppsed at frame rate.    Don't do that 😉

Edited by ROGRat

## Create an account

Register a new account

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 9
• 56
• 17
• 28