[HN Gopher] Fixed Timestep Without Interpolation
___________________________________________________________________
Fixed Timestep Without Interpolation
Author : ibobev
Score : 60 points
Date : 2024-10-18 11:00 UTC (12 hours ago)
(HTM) web link (jakubtomsu.github.io)
(TXT) w3m dump (jakubtomsu.github.io)
| eru wrote:
| It's somewhat amusing, that someone smart working in a language
| like Go would come to the same conclusion that Haskell
| practically forces on you (unless you work to avoid it): by
| default, your state should be copy-on-write.
|
| > For this reason we duplicate the entire game state into a new,
| temporary render-only game state, and simulate the tick on this
| one. That way the fixed timestep game state stays untouched.
|
| Of course, because it's Go, they have to duplicate everything
| explicitly. A poor-man's copy-on-write.
|
| > Tangent: determinism and replay
|
| > You need to make sure entities are always updated in the same
| order. This means deterministic O(1) datastructures like pools
| are your friend.
|
| That's not actually required. But I guess Go makes this the least
| painful avenue forward?
| pixelpoet wrote:
| Pretty sure that's Odin, not Go.
| eru wrote:
| Oh, I used my browser's `inspect` on the source code snipped
| posted, and they were using Go syntax highlighting, so I
| assumed the code is written in Go.
|
| Thanks for pointing this out.
|
| Well, I guess my original point applies to Odin instead of Go
| then.
| meheleventyone wrote:
| > > Tangent: determinism and replay
|
| > > You need to make sure entities are always updated in the
| same order. This means deterministic O(1) datastructures like
| pools are your friend.
|
| > That's not actually required. But I guess Go makes this the
| least painful avenue forward?
|
| The formulation isn't complete but they're correct for what
| they're getting at. It should be:
|
| "You need to make sure entities are always updated in the same
| order iff the order matters to the end result."
|
| For example if you move entity A before entity B and collision
| check on move to make sure it's valid if A and B would
| intersect after moving without collision checking you will end
| up with different positions of A and B depending on which goes
| first.
|
| Your choices then are to make sure entity update order is
| deterministic or rework the problem so it doesn't have the
| ordering dependency. The latter can be quite hard to do and the
| conditions where there is an ordering dependency can be subtle
| and unintuitive making it hard to cover all cases.
| diggan wrote:
| Maybe I misunderstand your comment, but seems like you're
| misunderstanding the contents of the article/the point?
|
| They're doing a duplicate of the state not because it's
| required in the language or whatever, but because they want to
| predict something without affecting the actual state. The only
| way of doing that is running the actual code against a new
| state duplicate from the existing, actual state.
|
| Not sure what the language has to do with it, you'd have to do
| the same in any language, explicitly or implicitly.
| thegeomaster wrote:
| One important approach is missing: extrapolation.
|
| Usually, your entities all have velocities, which you can use to
| extrapolate from the last simulated state to the current one
| (after <dt time has passed). For things like visual effects,
| you'd have to have a custom extrapolate implementation, which is
| not really different than a custom interpolate implementation
| that you need for interpolation.
|
| This eliminates the lag issue, and at anywhere close to 60FPS,
| looks perfectly fine. It will look strange at very low
| framerates, but at that point, you can just automatically switch
| it off.
|
| You do need a way to extrapolate game state, which is slightly
| painful, but the author's proposed solution has big drawbacks
| (which he hints at). Since it touches all game state each frame
| (even though it's "just" a memcpy), it completely changes the
| performance characteristics of your main loop.
|
| Without this, the complexity of your game step is linear in the
| number of updated or rendered entities, so you can add large
| amounts of additional state at any time, as long as only a small
| part of it will be visible/relevant to update each frame.
|
| With the author's approach, your step complexity is linear in the
| state size. You basically have an additional write for all state,
| which gives you a very restrictive upper limit. It's not just AAA
| games - as soon as you add a particle system, you've created a
| great many entities which you now need to memcpy every frame.
|
| The scalable solution to this complication is copy-on-write,
| which is more complexity... or, bite the bullet, write that
| extrapolation function, and enjoy your freedom to introduce crazy
| particles, physics, MMO world state, or whatever you want! At
| real-world framerates, it will look no different.
| jakubtomsu wrote:
| Extrapolation has some very serious drawbacks in action games
| which make it unusable though. You cannot just move entities
| forward in time by velocity*delta, because that ignores all
| collisions with the world. So you end up with a lot of weird
| jitter and ugly effects like that. And once you start adding
| support for things like collision while extrapolating, why not
| just tick the entire game;)
| jakubtomsu wrote:
| (collisions are by far not the only issue here, it's just the
| first one you run into)
| jayd16 wrote:
| > why not just tick the entire game
|
| In a multiplayer scenario, you might not have enough
| information to tick the entire game. You'll probably want to
| extrapolate input from other users, at least.
| meheleventyone wrote:
| On the contrary in multiplayer extrapolation is the last
| thing you want to do because the time to correction is long
| and the prediction is really coarse. It essentially results
| in a lot of corrections, applied late which looks and feels
| awful.
| dyarosla wrote:
| Extrapolation is one of those ideas that's not actually used in
| practice- at least I've yet to see it used in any games in any
| meaningful capacity.
|
| It's just far too complicated and requires custom logic while
| resulting in worse results than more straightforward options.
| Even for multiplayer games the "extrapolation" is often done by
| repeating input states and running the regular game loop.
|
| I also wouldn't equivocate the interpolation approach with
| extrapolation. With interpolation you interpolate between two
| valid states. With extrapolation you produce a potentially
| invalid state (ie a character that's inside of a wall). The
| only work around for the latter issue is to perform a full game
| tick - at which point you're no longer doing extrapolation.
| jayd16 wrote:
| > Extrapolation is one of those ideas that's not actually
| used in practice
|
| This is how VR frame doubling works, no?
| "Timewarp"/"Spacewarm"
|
| Also I would think that a lot of netcode would be considered
| extrapolation. You'd extrapolate a peer's input or velocity
| (and perhaps clean it up with further local simulation) and
| then deal with mis-prediction when changes are replicated.
| dyarosla wrote:
| For the former, Timewarp is used at an OS level to perturb
| the visibly rendered quad to match the display time
| orientation. There's no extrapolation: the rendered frame
| is simply adjusted to account for the change in headset
| orientation.
|
| For the latter, as I mentioned, the extrapolation is not on
| velocity: you still compute regular game ticks but by
| holding the input constant. This is quite different from
| extrapolating velocities.
| jayd16 wrote:
| Spacewarp takes the motion vectors and depth buffer and
| generates new frames from the extrapolated motion. Its
| detailed here.
| https://developers.meta.com/horizon/blog/introducing-
| applica...
|
| > For the latter, as I mentioned, the extrapolation is
| not on velocity: you still compute regular game ticks but
| by holding the input constant. This is quite different
| from extrapolating velocities.
|
| Replicating velocity is fairly common. Unreal's character
| movement replicates velocity and not inputs. I would
| personally argue that even doing a full game tick with
| replicated velocities is extrapolation. I'm not sure what
| the distinction would be or what counts as a full tick
| with error correction vs local extrapolation per tick
| with error correction.
| dyarosla wrote:
| I agree- what's the difference between error correction
| and a full tick? At what point do you draw the line on
| error correction?
|
| Extrapolation is often used to mean extrapolating values
| _without_ error correction, at which point the results
| are less than stellar.
|
| Spacewarp is, like Timewarp, a way to match the render
| frame time on a headset but by creating a warp of the
| output image; ill concede that this is technically
| extrapolation but is far away from whats generally
| referred to in describing updating entity values in game
| loops.
| meheleventyone wrote:
| There's a third way here so rather than:
|
| * Interpolate between the previous state and the new state by the
| remaining time which leaves the action delayed in the past.
|
| * Simulate an extra variable delta tick with the extra issues you
| can get from going off cadence.
|
| You can simulate a temporary tick a full fixed tick ahead and
| then interpolate between the current tick and the future tick.
| Typically the cost of ticking a new frame doesn't depend hugely
| on the length of time it's simulating so the cost is largely the
| same as the method presented. This has some advantages in terms
| of keeping the time delta consistent, meaning you don't need to
| worry about it throughout the simulation code.
| jakubtomsu wrote:
| that's a cool idea! However it does mean I would still have to
| write the interpolation code which is not fun. But it's a good
| way to solve the latency issue for sure. Thanks for the idea,
| I'll add a note to mention it somewhere in the post.
| meheleventyone wrote:
| Thanks, like most engineering things it's all about picking
| the set of tradeoffs that you can live with. :D
| modeless wrote:
| This runs the risk of showing events that don't occur, as
| you're rewinding and replaying part of a time step every frame.
| For example, the player might die in the temporary time step
| and you'd show the first frame of death animation but then a
| jump input comes in later that frame and when you redo the time
| step for real the player doesn't die.
| jayd16 wrote:
| Yes but rollback and replay still looks good in practice and
| is considered state of the art in latency dependent games
| (like fighting games).
| modeless wrote:
| For multiplayer, sure. The latency is large and variable,
| so you have to make compromises. But local inputs are low
| and fixed latency and ideally you don't need the same
| compromises.
|
| The ideal solution from a latency perspective is non-fixed
| time steps, but there are a lot of downsides of course. The
| rewind/replay solution could be improved with some tweaks.
| You could set a flag in the temporary time step to disable
| all irreversible state changes like dying, so you would
| never see/hear a flicker of death.
| meheleventyone wrote:
| Yes if there was a change in input that would mean there was
| a significant difference but it'd both be fleeting and rare
| at most game framerates. If one frame you predicted death and
| the next it corrected it's unlikely much of anything will
| have started happening. In a rollback networking situation
| you can often go back several frames of incorrect prediction
| without it being particularly noticeable, so one frame is
| basically immaterial.
| davexunit wrote:
| It's an interesting approach because the one frame of lag
| introduced by the typical interpolation strategy is not ideal,
| but I don't think many games can make use of it. As the article
| states, game state needs to be in a relatively small contiguous
| chunk of memory with no pointers to chase. That's a very serious
| constraint.
| dyarosla wrote:
| The main reason to prefer interpolation is that your fixed time
| step function does not need to operate on variable time ever-
| removing a complicated dependency.
|
| For instance, modifying character accelerations based on a fixed
| time step constant is far more straightforward than the methods
| required to work with variable time deltas (due to floating point
| accumulated error). This is why any action-based deterministic
| game (think platformers, shooters, physics based games) will opt
| for this.
|
| IMO it is _much_ more straightforward to have a render method
| that pre-allocates some extra memory, interpolates a handful of
| values and renders them vs the nondeterminism introduced in a
| game logic method that has to take into account variable time
| (especially if also networking multiplayer state). And for this
| you trade off a frame of visual-only latency - a choice I'd take
| any day.
| rkangel wrote:
| > modifying character accelerations based on a fixed frame
| constant is far more straightforward than the methods required
| to work with variable time deltas
|
| For those who don't know - the reason this is hard is because
| of the different amounts of maths error that can accumulate
| between the two approaches (usually FP precision error). Doing
| some maths in 10 increments a tenth of the size will likely end
| up with a slightly different value than doing it once in a full
| size increment.
|
| This is _particularly_ important in multiplayer games where
| multiple players need to be able to do the same calculations
| and get the identical result. It is not good if the world
| begins to diverge just because you 've got different frame
| rates!
| Mathnerd314 wrote:
| For reference, SuperTux's code:
| https://github.com/SuperTux/supertux/blob/8d79ac7ce4db5e4225...
| (disclosure: not code I wrote, but I've tweaked it here and
| there)
|
| The idea is similarly to just simulate one logical step at a
| time, with the fixed timestep (this is important because SuperTux
| uses simple Euler integration which is timestep-sensitive). But
| there is tracking code that sleeps / adds extra logical steps
| between frames so the rate of logical frames ends up
| corresponding closely to the rate of rendered frames. And as with
| the final solution here there's no interpolation in rendering,
| you just display the latest game state without storing the
| previous.
| brid wrote:
| "Note: This method probably won't work very well in cases when
| game_tick can take a very significant amount of time, or the game
| state is gigantic, e.g. in a big AAA game which needs to run the
| physics engine and whatnot."
| akira2501 wrote:
| // Bitwise OR the bit flags tick_input.actions[action] +=
| flags
|
| Why?
___________________________________________________________________
(page generated 2024-10-18 23:00 UTC)