The past few days I have been playing with Godot engine with a view to using it for some Gamedev challenges. Last time for Tower Defence I used Unity, but updating it has broken my version so I am going to try a different 'rapid development' engine.
So far I've been very impressed by Godot, it installs down to a small size, isn't bloated and slow with a million files, and is very easy to change versions of the engine (I compiled it from source to have latest version as an option).
Unfortunately, after working through a couple of small tutorials I get the impression that Godot suffers from the same frame judder problem I had to deal with in Unity.
Let me explain: (tipping a hat to Glenn Fiedler's article)
Some of the first games ran on fixed hardware so they didn't have a big deal about timing, each 'tick' of the game was a frame that was rendered to the screen. If the screen rendered at 30fps, the game ran at 30fps for everyone.
This was used on PCs for a bit, but the problem was that some hardware was faster than others, and there were some games that ran too fast or too slow depending on the PC.
Clearly something had to be done to enable the games to deal with different speed CPUs and refresh rates.
Delta Time?
The obvious answer was to sample a timer at the beginning of each frame, and use the difference (delta) in time between the current frame and the previous to decide how far to step the simulation.
This is great except that things like physics can produce different results when you give it shorter and longer timesteps, for instance a long pause while jumping due to a hard disk whirring could give enough time for your player to jump into orbit. Physics (and other logic) tends to work best and be simpler when given fixed regular intervals. Fixed intervals also makes it far easier to get deterministic behaviour, which can be critical in some scenarios (lockstep multiplayer games, recorded gameplay etc).
Fixed Timestep
If you know you want your gameplay to have a 'tick' every 100 milliseconds, you can calculate how many ticks you want to have complete at the start of any frame.
// some globals
iCurrentTick = 0
void Update()
{
// Assuming our timer starts at 0 on level load:
// (ideally you would use a higher resolution than milliseconds, and watch for overflow)
iMS = gettime();
// ticks required since start of game
iTicksRequired = iMS / 100;
// number of ticks that are needed this frame
iTicksRequired -= iCurrentTick;
// do each gameplay / physics tick
for (int n=0; n<iTicksRequired; n++)
{
TickUpdate();
iCurrentTick++;
}
// finally, the frame update
FrameUpdate();
}Brilliant! Now we have a constant tick rate, and it deals with different frame rates. Providing the tick rate is high enough (say 60fps), the positions when rendered look kind of smooth. This, ladies and gentlemen, is about as far as Unity and Godot typically get.
The Problem
However, there is a problem. The problem can be illustrated by taking the tick rate down to something that could be considered 'ridiculous', like 10 or less ticks per second. The problem is, that frames don't coincide exactly with ticks. At a low tick rate, several frames will be rendered with dynamic objects in the same position before they 'jump' to the next tick position.
The same thing happens at high tick rates. If the tick does not exactly match the frame rate, you will get some frames that have 1 tick, some with 0 ticks, some with 2. This appears as a 'jitter' effect. You know something is wrong, but you can't put your finger on it.
Semi-Fixed Timestep
Some games attempt to fix this by running as many fixed timesteps as possible within a frame, then a smaller timestep to make up the difference to the delta time. However this brings with it many of the same problems we were trying to avoid by using fixed timestep (lack of deterministic behaviour especially).
Interpolation
The established solution that is commonly used to deal with both these extremes is to interpolate, usually between the current and previous values for position, rotation etc. Here is some pseudocode:
// some globals
int iCurrentTick = 0
// player
Vector3 m_Pos_previous = (0, 0, 0);
Vector3 m_Pos_current = (0, 0, 0);
Vector3 m_Pos_render = (0, 0, 0);
// called each frame by engine
void Update()
{
// Assuming our timer starts at 0 on level load:
// (ideally you would use a higher resolution than milliseconds, and watch for overflow)
int iMS = gettime();
// ticks required since start of game
int iTicksRequired = iMS / 100;
// remainder
int iMSLeftOver = iMS % 100;
// number of ticks that are needed this frame
iTicksRequired -= iCurrentTick;
// do each gameplay / physics tick
for (int n=0; n<iTicksRequired; n++)
{
TickUpdate();
iCurrentTick++;
}
// finally, the frame update
float fInterpolationFraction = iMSLeftOver / 100.0f;
FrameUpdate(fInterpolationFraction);
}
// just an example
void TickUpdate()
{
m_Pos_previous = m_Pos_current;
m_Pos_current.x += 10.0f;
}
// very pseudocodey, just an example for translate for one object
void FrameUpdate(float fInterpolationFraction)
{
// where pos is Vector3 translate
m_Pos_render = m_Pos_previous + ((m_Pos_current - m_Pos_previous) * fInterpolationFraction);
}The more astute among you will notice that if we interpolate between the previous and current positions, we are actually interpolating *back in time*. We are in fact going back by exactly 1 tick. This results in a smooth movement between positions, at a cost of a 1 tick delay.
This delay is unacceptable! You may be thinking. However the chances are that many of the games you have played have had this delay, and you have not noticed.
In practice, fast twitch games can set their tick rate higher to be more responsive. Games where this isn't so important (e.g. RTS games) can reduce processing by dropping tick rate. My Tower Defence game runs at 10 ticks per second, for instance, and many networked multiplayer games will have low update rates and rely on interpolation and extrapolation.
I should also mention that some games attempt to deal with the 'fraction' by extrapolating into the future rather than interpolation back a frame. However, this can bring in new sets of problems, such as lerping into colliding situations, and snapping.
Multiple Tick Rates
Something which doesn't get mentioned much is that you can extend this concept, and have different tick rates for different systems. You could for example, run your physics at 30tps (ticks per second), and your AI at 10tps (an exact multiple for simplicity). Or use tps to scale down processing for far away objects.
How do I retrofit frame interpolation to an engine that does not support it fully?
With care is the answer unfortunately. There appears to be some support for interpolation in Unity for rigid bodies (Rigidbody.interpolation) so this is definitely worth investigating if you can get it to work, I ended up having to support it manually (ref 7) (if you are not using internal physics, the internal mechanism may not be an option). Many people have had issues with dealing with jitter in Godot and I am as yet not aware of support for interpolation in 3.0 / 3.1, although there is some hope of allowing interpolation from Bullet physics engine in the future.
One option for engine devs is to leave interpolation to the physics engine. This would seem to make a lot of sense (avoiding duplication of data, global mechanism), however there are many circumstances where you may not wish to use physics, but still use interpolation (short of making everything a kinematic body). It would be nice to have internal support of some kind, but if this is not available, to support this correctly, you should explicitly separate the following:
- transform CURRENT (tick)
- transform PREVIOUS (tick)
- transform RENDER (where to render this frame)
The transform depends on the engine and object but it will be typically be things like translate, rotate and scale which would need interpolation.
All these should be accessible from the game code, as they all may be required, particularly 1 and 3. 1 would be used for most gameplay code, and 3 is useful for frame operations like following a player with a camera.
The problem that exists today in some engines is that in some situations you may wish to manually move a node (for interpolation) and this in turn throws the physics off etc, so you have to be very careful shoehorning these techniques in.
Delta smoothing
One final point to totally throw you. Consider that typically we have been relying on a delta (difference) in time that is measured from the start of one frame (as seen by the app) and the start of the next frame (as seen by the app). However, in modern systems, the frame is not actually rendered between these two points. The commands are typically issued to a graphics API but may not be actually rendered until some time later (consider the case of triple buffering). As such the delta we measure is not actually the time difference between the 2 rendered frames, it is the delta between the 2 submitted frames.
A dropped frame may for instance have very little difference in the delta for the submitted frames, but have double the delta between the rendered frames. This is somewhat a 'chicken and the egg' problem. We need to know how long the frame will take to render in order to decide what to render, where, but in order to know how long the frame will take to render, we need to decide what to render, and where!!
On top of this, a dropped frame 2 frames ago could cause an artificially high delta in later submitted frames if they are capped to vsync!
Luckily in most cases the solution is to stay well within performance bounds and keep a steady frame rate at the vsync cap. But in any situation where we are on the border between getting dropped frames (perhaps a high refresh monitor?) it becomes a potential problem.
There are various strategies for trying to deal with this, for instance by smoothing delta times, or working with multiples of the vsync interval, and I would encourage further reading on this subject (ref 3, 8, 9).
Addendum
Note that the code examples given are pseudocode, and may be best modified for a particular engine. There is often some support for fixed tick rates within engines, for instance in Unity you may be able to use the following simplified scheme:
// unity calls update once per frame
void Update()
{
// interpolate fraction
float fFraction = (Time.time - Time.fixedTime) / Time.fixedDeltaTime;
// my frame update for interpolation
FrameUpdate(fFraction); // same as earlier examples
}
// unity calls once per tick
void FixedUpdate()
{
TickUpdate(); // same as earlier examples
}I would also suggest implementing interpolation without engine physics first, because using with engine physics can incorporate subtle bugs as you may be moving a physics representation inadvertently. I will address this in a future article, however in short one solution is to create completely separate renderable objects and physics objects in the game (different branches of the scene graph), store a reference on the render object to the physics object, and interpolate the render object transform based on the physics object. In Godot you can also visualize the physics colliders in the Debug Menu, which is very helpful.
References
1 https://gafferongames.com/post/fix_your_timestep/
2 http://www.kinematicsoup.com/news/2016/8/9/rrypp5tkubynjwxhxjzd42s3o034o8
3 http://frankforce.com/?p=2636
4 http://fabiensanglard.net/timer_and_framerate/index.php
5 http://lspiroengine.com/?p=378
6 http://www.koonsolo.com/news/dewitters-gameloop/
7 https://forum.unity.com/threads/case-974438-rigidbody-interpolation-is-broken-in-2017-2.507002/
8 https://medium.com/@alen.ladavac/the-elusive-frame-timing-168f899aec92
9 http://bitsquid.blogspot.com/2010/10/time-step-smoothing.html
I had a similar issue with retrofitting Urho3D to use a fixed timestep. I'm not doing that now, but when I was doing it my solution was to implement a special component to store last and current transforms and work through that. It worked well enough, but my games tend to not use physics, and as you mentioned, physics is where the madness lurks. Something built into the native Node would be better, I think, but would require modifying the library.