Avoiding fixed timestep death spiral?

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Avoiding fixed timestep death spiral?

Post by airstruck » Sun Mar 05, 2017 6:23 pm

Capping dt to a maximum value seems like the usual recommendation for avoiding the "death spiral" when using a fixed timestep (accumulator approach). I'm looking at an alternative for this that will drop frames instead of slowing the game down on slow devices.

Code: Select all

local accumulator = 0
local timestep = 69 / 4096

function love.update (dt)
    accumulator = accumulator + dt
    dt = timestep
    if accumulator >= dt then
        while accumulator >= dt * 2 do dt = dt * 2 end
        accumulator = accumulator - dt
        -- do stuff here with dt
    end
end
Just off the top of my head, not really tested but you get the idea.

The timestep value has an exact binary representation and is just under 60 fps. When the accumulator is more than twice the timestep, the timestep is doubled (as many times as needed, but probably usually just once). So it usually has a fixed timestep of ~60 fps, but it will drop to ~30 fps to get out of a death spiral. Not exactly a fixed timestep, I guess, but carefully managed.

Other than problems with tunneling (can be fixed with CCD or not having super-fast things) and jitter (maybe can be fixed by extrapolation or interpolation in draw routine), are there problems with this approach I'm not thinking of? Is this a common approach? How will box2d feel about this? Are there any other good alternatives?

User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: Avoiding fixed timestep death spiral?

Post by raidho36 » Sun Mar 05, 2017 6:29 pm

The common approach is to let it spiral into oblivion. The #1 issue with dropping frames is that input will also be dropped and will not activate until next frame. When FPS tanks as badly as you need to skip frames, skipping input really ruins character handling and you quickly find yourself in a game over screen. People can get over game slowing down to a crawl as long as it still handles the same way, but not when it stops responding to input.

User avatar
ivan
Party member
Posts: 1703
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Avoiding fixed timestep death spiral?

Post by ivan » Sun Mar 05, 2017 6:37 pm

I like to use a max_frameskip constant. A simple technique is to count the number of substeps in each update until you reach the max_frameskip. This way the game will slow down in the rare event something terrible happens but it won't hog the cpu completely.

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: Avoiding fixed timestep death spiral?

Post by airstruck » Sun Mar 05, 2017 6:38 pm

I don't really consider letting it spiral into oblivion to be an option. If it regularly takes even a few milliseonds longer to do its thing than the fixed timestep allows, some kind of safeguard here means the difference between the game running almost perfectly or spiraling out of control immediately. It seems like there would be no real difference with input handling with this frame-dropping approach as compared to the capped-dt approach?

@Ivan: interesting, but I'm specifically looking for alternatives to max frameskip (capped dt) that won't slow down the game.

User avatar
ivan
Party member
Posts: 1703
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Avoiding fixed timestep death spiral?

Post by ivan » Sun Mar 05, 2017 6:42 pm

I dont think there is much you could do with fixed time steps except to slow down the game altogether.

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: Avoiding fixed timestep death spiral?

Post by airstruck » Sun Mar 05, 2017 6:55 pm

Right, that's why I'm looking at "carefully managed" timesteps that are at least multiples of a fixed timestep. It seems to work pretty well from some simple stress tests, but I'm not sure how things like box2d that sort of expect a fixed timestep will react.

User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: Avoiding fixed timestep death spiral?

Post by raidho36 » Sun Mar 05, 2017 6:59 pm

The key factor to consider is importance of input timing. If it's important, then the game must always run at the same pace as well as not skip any frames. Both sudden speed changes and dropping input frames ruins timing and if it was important, ruins the gameplay experience. Secondary factor is input precision. It actually improves as the game runs slower, but skipping frames ruins is just as well as it does with timing.

If neither are important, then you can go about it any way you want - it's not relevant. If precision matters, such as when avoiding projectiles, then input is not to be skipped. If timing matters, such as in platforming, then game must also not change pace, in addition to not skipping input. Generally, dropping one or two frames should not damage precision too badly - still unacceptable in competitive games though, where even small timing difference decides the game.

Having that said, you should optimize the game to run at good framerate on all target systems. Don't expect variable framerate handling system to bail you out of that problem. And of course if it does runs fine on all systems, none of this is an issue to start with. As for Box2D, we all already know it doesn't likes non-fixed timestep and objects' interaction becomes unstable, so that's your answer.

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: Avoiding fixed timestep death spiral?

Post by airstruck » Mon Mar 06, 2017 6:14 pm

What's most important to me in this case is that the game clock always runs at same speed, this is why capping dt is no good. In general I expect the game to be able to do its thing within the fixed timestep, but I want a safety net in case there's a hiccup. Maybe system update manager cranks up and prevents game from working fast enough for a moment, I want it to be able to recover from that, without slowing down game time or starting a death spiral.

For box2d, maybe it can just be updated twice when a frame is dropped. Updating everything else on a double timestep should be enough.

Let me try asking this question in a different way. Has anyone here done a fixed timestep where death spiral was avoided in some other way besides capping dt (slowing down game time)? Did you do it by temporarily using a multiple of the regular timestep, or some other way? I'm mostly just trying to figure out if the technique I outlined for dropping frames is a common one, or if it's done in some other way (or not done at all for some reason). I can't find much about it on the internet.

User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: Avoiding fixed timestep death spiral?

Post by raidho36 » Mon Mar 06, 2017 6:42 pm

You didn't find anything because there's no simple and universal answer. What you should and shouldn't do depends on the way your particular game plays. Also I just noticed, you seem to imply that without some sort of frame skipping the framerate will get continually worse until the game freezes completely. This isn't what really happens (unless you design update function extremely poorly). If it takes 10 ms to update the frame but only 8 ms of CPU time is actually available per 10 ms of real time, then it'll simply take 10 * 10/8 = 12.5 ms of real time to update, and it'll run at 80 fps instead of 100. The extra time doesn't carry over to the next frame to catch up for, once calculations are finished it's gone.

Electric motor power and load would be a good analogy - the faster it spins the less there is torque available. If you apply to a bigger load than it could pull at full speed, it'll slow down until it produces enough power to pull it, but it won't halt completely just because at full speed it didn't produce enough torque.

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: Avoiding fixed timestep death spiral?

Post by airstruck » Mon Mar 06, 2017 8:03 pm

I'm not looking for a simple universal answer, I'm looking for any example of anyone using an approach like this for any purpose.

I think maybe we're discussing two different approaches. In the approach I've usually seen, extra time does remain in the accumulator. When the accumulator becomes greater than a fixed timestep, a "tick" happens and the timestep is subtracted from the accumulator, leaving the accumulator greater than 0 unless it happened to reach exactly the value of the timestep. If it takes longer to process a tick than the fixed timestep allows, the value in the accumulator will keep growing, and "game time" will fall behind where it's supposed to be relative to real time. This is what I'm worried about, I didn't mean to suggest that the game would slow down and eventually stop (although it could if you tried to mitigate this by simply applying two ticks in a row, for example). The solution I'm looking at is to temporarily double the timestep if the accumulator grows to twice the value of the regular timestep.

In other words, the extra time does carry over in the approach I have in mind, which as far as I can tell is the usual way of handling the accumulator. Are you saying you prefer resetting the accumulator to zero after each frame instead of subtracting the timestep and leaving the difference in the accumulator, or am I misunderstanding your point?

Post Reply

Who is online

Users browsing this forum: No registered users and 44 guests