Improve the behaviour of move_and_slide() when on moving platforms

[e344fde6bf]

Describe the project you are working on

3D platform

Describe the problem or limitation you are having in your project

The current implementation of move_and_slide() in KinematicBody handles moving platforms poorly if they are moving at a non-constant velocity (#36483, #961) or rotating (#35365, #16450).

Issue with platform moving at a non-constant velocity:

Issue with rotating platform:

Describe the feature / enhancement and how it helps to overcome the problem or limitation

This proposal is to improve move_and_slide() by using numerical analysis to predict the platform's velocity (i.e. the value returned by get_floor_velocity()).

Using this proposal on a platform moving at a non-constant velocity:

Using this proposal on a rotating platform

Demo project implementation

Controls:

• WASD + mouse to move
• Space to jump
• press Q to switch between the original and improved velocity estimates
• press E to toggle motion smoothing

demo: demo repo
godot version: v3.2.3.stable

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Improving estimate of velocity due to rotation

The way move_and_slide() current works is it calculates the instantaneous velocity v that the KinematicBody experiences at point p and assumes it remains constant for the given timestep. However to rotate around the origin at a fixed distance, the average velocity that the KinematicBody experiences over the whole timestep should be used. One way to calculate this is to take the start point p1 and use the angular velocity to rotate around the origin to point p2. Then the average velocity is simply the difference between the two. This diagram shows the difference between the two approaches:

Estimating linear velocity

The current approach to estimate linear velocity is to take the two most recent position values and use the difference between them to compute an estimate for the linear velocity. If more data points are used, then a better approximation can be found.

So given a series of position x[i] values, we define a series of v[i] velocity values as v[i] = x[i+1] - x[i], a series of acceleration values a[i] = v[i+1] - v[i], a series of jerk values j[i] etc. This process can be performed repeatedly for higher-order approximates. Then we assume that after we repeat this process enough, we'll find a series of values that is constant e.g. j[i] = j[i+1].

Then to find x[i+1], then we simply substitute:

x[i+1] = x[i] + v[i]
x[i+1] = x[i] + v[i-1] + a[i-1]
x[i+1] = x[i] + v[i-1] + a[i-2] + j[i-3]
// but if j[i-3] = j[i-2], then our estimate is
x[i+1] = x[i] + v[i-1] + a[i-2] + j[i-2]

It might be easier to understand if we visualise it as a table:

x0, x1, x2, x3
  v0, v1, v2
    a0, a1
      j0
// Then to find x4, we compute
x4 = x3 + v2 + a1 + j0

This process is essentially using a Newton polynomial to estimate the next value in the sequence. From Newton polynomials we know that if we take n repeated differences of an nth degree polynomial, we will reach a constant value. For our example above, we assumed that the third series of differences j[i] are constant, so we have effectively used a third degree polynomial to estimate x4.

This implementation will still have noticeable issues when the platform does not move smoothly (discontinuities in position, velocity, etc.), however the current implementation also suffers from these same issues anyway.

Smoothing out discontinuities

While the above method works well and will keep the KinetmaticBody at a fixed point on the platform, discontinuities in the platforms velocity will result in overshoot and ringing as the algorithm rapidly tries to correct itself. To combat this we can look for large jumps in the derivatives and perform the error correction over several frames.

When we detect a discontinuity, we should:

• discard our previously recorded velocity values because they are no longer useful for making predictions
• because of the discontinuity, our prediction made in the last frame will have been wrong. We can compute the error in our position as error = (v[t] - v[t-1]) * h
• add back a portion of this error each frame until we have reached the target position

Demo implementation notes/issues

The current implementation of move_and_slide() uses an out of date value for get_floor_velocity() (probably a bug). When we call move_and_slide() at time t, if it collides with a floor, then it creates a KinematicCollision and stores in it the floor velocity calculated between frames t-h and t-2h. Then in the next frame t+h, calls to get_floor_velocity() will use that velocity value stored in the KinematicCollision even though we should now have access to the velocity of the floor moving between frames t-h and t. So we fix this in our demo by requesting the most up to date value of the floor from the PhysicsServer.

To calculate the rotational velocity, we need to know the position of KinematicBody relative to the centre of the platform. However, the KinematicCollision object created by move_and_slide doesn't provide enough information to calculate this value. To compute this in GDScript, we need to know the position that the platform has at the start of the frame, but I'm not sure how to compute this easily in a way that is independent from the KinematicBody's location in the scene tree. To hack around this in the demo, I placed the player at the top of the scene tree.

If this enhancement will not be used often, can it be worked around with a few lines of script?

Any project that uses move_and_slide() for character motion will benefit from this approach. There are other ways to solve this problem, for example:

• re-parenting the node to the platform
• organising the scene tree such that platforms are processed before characters so we know how to move the character
• "Sync to Physics" option

However from a users perspective, I think this approach is simpler, more beginner friendly and has basically no downsides compared to the current implementation of move_and_slide().

Is there a reason why this should be core and not an add-on in the asset library?

This proposal improves move_and_slide() so it should be in core.

Edit: added vertical moving platforms to the demo for testing purposes
Edit2: added motion smoothing when we detect discontinuities

[e344fde6bf]

I added some vertical moving platforms to the demo for testing: move_and_slide-improvement-0.2.zip. These aren't working for either approach.

From what it looks like this happens because move_and_slide() is performing collisions tests with the platform based on where it currently is, but it should be performing collision tests based on where it expects the platform to be next frame. For example if the platform is moving straight up, move_and_slide() will add the platforms velocity to the player placing them somewhere in the air above the platform. Then it performs the collision test and decides they are in the air so they start falling as the platform hasn't yet moved under the player.

[e344fde6bf]

Since we are tracking the objects derivatives it's easy to tell when a discontinuity occurs, so we can take some steps to smooth out the motion:

• discard our previously recorded velocity values because they are no longer useful for making predictions
• because of the discontinuity, our prediction made in the last frame will have been wrong. We can compute the error in our position as error = (v[t] - v[t-1]) * h
• add back a portion of this error each frame until we have reached the target position

I've updated the demo to include these techniques: demo. Press E to toggle them.

[Calinou]

cc @pouleyKetchoupp

[pouleyKetchoupp]

Thanks for this proposal, it's an interesting take on solving moving platforms.

I think porting Sync to Physics option to 3D would be an easier first step at the moment though. I would rather start with that and see what remaining issues need to be solved from there.

[e344fde6bf]

If the issue with reported positions and velocities being out of sync is fixed, we probably wouldn't need Sync to Physics in most cases. Because I could just put all the platforms at the top of my node tree and all the player characters at the bottom. Then move_and_slide() would know the exact distance to move the character on the platform. However, this would only work if the platforms are kinematic bodies and not rigid bodies (their velocity is from start of frame).

Does Sync to Physics handle this better? I'm not sure how it works exactly, but I'm guessing it causes the KinematicBody to be moved after all the other rigid and non-synced kinematic bodies have calculated there new position/velocities. If I use a rigid body as a see-saw platform, can I use a KinematicBody for the player controller then? How would this be implemented? It still seems like you'd need Sync to Physics for this use case.

[pouleyKetchoupp]

Sync to Physics works only for kinematic bodies and fixes cases where the platform is one frame ahead of other physics objects, by setting the platform's transformation only after physics is processed.

Even if there's a change in the API to have access to updated velocities from the KinematicBody as we're discussing in #2332, move_and_slide would still use the previous velocity internally for things to work correctly. Because as you pointed out, otherwise the order of your objects in the tree would affect the way they interact. Having a specific flag on platforms like Sync to Physics seems much less confusing.

[e344fde6bf]

Just to clear something up, is move_and_slide() supposed to work when used with Sync to Physics? I read in the documentation of KinematicBody2D that they should not be used together.

move_and_slide would still use the previous velocity internally for things to work correctly

So if we can't use it with Sync to Physics whats the use case of move_and_slide(), if we use the previous velocity internally won't we have the same sliding issues when on moving platforms? If I'm understanding things correctly, this would mean move_and_slide() only works when all the other bodies aren't moving. So to handle non-trival cases we either need to predict the velocity (like mention in this issue), or use the up-to date velocities (#2332) with a specific order of the node tree.

[pouleyKetchoupp]

You can't use move_and_slide for moving the platform if it has Sync to Physics, but you can still use move_and_slide on the character body itself.

[e344fde6bf]

Ah okay, I think understand how the sync_to_physics property is used now. Still I think there's some use cases were you might want to use the specific node ordering approach with move_and_slide. For example, if the game had moving platforms as well as "platform head" enemies which the player can ride on, then you could order the node tree

1. Moving platforms
2. Enemies
3. Player character

This way I could use move_and_slide() to control the enemies, and they'd be able to ride the moving platforms. The player would also use move_and_slide() which would allow them to ride on top of an enemy that's also riding on top of a moving platform.

I think move_and_slide() should be able to support both use cases easily since it can just use the sync_to_physics property to decide how the velocity is computed (sync_to_physics = false -> gets the "intra-frame" velocity, sync_to_physics = true -> use the previous velocity). This can handle all the use cases that I want, so I think I'll close this issue in favour of #2332.

There's still some bugs with move_and_slide, do you want to open an issue for any of them?

• On a rotating platform move_and_slide() uses the instantaneous velocity instead of the average velocity over the timestep
• The floor velocity used by move_and_slide() is take from the start of the previous frame instead of the start of the current frame.

Thanks for taking the time to answer all my questions.

[e344fde6bf]

In case anyone stumbles upon this, I made another version of the demo that uses the node ordering approach here: https://github.com/e344fde6bf/godot-move-and-slide-fix/tree/node-order

This approach doesn't suffer issues for non-smooth motion since it gets the exact distance/velocity that the platforms move each frame.

[pouleyKetchoupp]

Thanks for the practical use cases, I see what we're trying to solve more clearly now, and the different test scenes are very useful too.

Concerning the two issues, yes some tickets on github would be great if you can isolate a test case in a minimal project (or with a simple reproduction case in the project you already made).