[Platformer] [Top-Down] Verlet integration for position calculus

[D8H]

Position calculus from speed and acceleration

The Platformer and Top-Down Movement are using the Euler method.

• https://en.wikipedia.org/wiki/Euler_method

We're doing something like this (maybe not in that order).

position += velocity * timeDelta;
velocity += acceleration * timeDelta;

The Verlet method is more precise, resilient to fps changes and doesn't cost much more (2 additional multiplications)

• https://en.wikipedia.org/wiki/Verlet_integration

Considering that the acceleration is constant we could do this instead.

position += velocity * timeDelta + acceleration * timeDelta * timeDelta / 2;
velocity += acceleration * timeDelta;

FPS independent

The Verlet method will ensure that a platform character jump the same height no matter the FPS.
Moreover, I think that the feeling of fluidity even with frame drops (who said GC?) should make it up for the 2 additional multiplications.

I wrote a test to make a comparison.

• [Platformer] Add 2 tests on jump at 30 fps and 120 fps. #3408

The difference is sensible.

• at 30 fps the max height delta is 165 pixels
• at 60 fps the max height delta is 150 pixels
• at 120 fps the max height delta is 142.5 pixels

Easier jump properties

For the Platformer behavior, it could allow to setup the jump with easier to understand parameters like height and width distance (and jump sustain time, gravity changes...). It could be done with an event-based extension.
It could be interesting to have some sort of calculator in the Platformer configuration directly. It could update properties according to other with lock buttons but it would need to implement these lock buttons. It's probably not worth the effort.

Backward compatibility

The Platformer will need a property to choose the legacy mode, but the top-down movement could use the new method directly as the impact will only be a slight change in the acceleration which is not very important.

Source

• https://youtu.be/hG9SzQxaCm8?t=1168

[4ian]

Ah very interesting! It's true that we're missing this quadratic term.

Moreover, I think that the feeling of fluidity even with frame drops (who said GC?) should make it up for the 2 additional multiplications.

That would be very interesting to see. This would really help improving the fluidity of games.

Totally up to apply this to all behaviors involving movement :) This being said we have to be careful when the speed is capped to consider that the acceleration is then 0 (and not the acceleration set).

[D8H]

I started to write helper functions around the platformer jump. It will be useful for:

• configurate a platformer character
• design levels (how far can a platform be reached...)
• help with platformer AI (eg: find where to jump to go to a platform)

This is an example to test a behavior that find the right initial jump speed for a given jump height.
https://games.gdevelop-app.com/game-257821b3-e763-49f3-84ee-772ffc97546d/index.html

[D8H]

I wrote a mathematical model of the jump with SageMath. I think it might help to write test or add new features to the jump extension.
A solver allows to express one variable as a function of others given some conditions. It could be used to plot too.
Do you think it could be interesting to have it in the technical documentation of the platformer extension?

# peakTime < jumpSustainTime && peakTime < maxFallingSpeedReachTime #

currentFallingSpeed(t, gravity) = gravity * t
sustainSpeed(t, gravity, jumpSpeed) = -jumpSpeed + currentFallingSpeed(t, gravity)
sustainHeight(t, gravity, jumpSpeed) = integral(sustainSpeed(t, gravity, jumpSpeed), t)
sustainPeakTime(gravity, jumpSpeed, jumpSustainTime) = solve([sustainSpeed(t, gravity, jumpSpeed)==0], t)[0].rhs()
sustainPeakHeight(gravity, jumpSpeed, jumpSustainTime) = sustainHeight(sustainPeakTime(gravity, jumpSpeed, jumpSustainTime), gravity, jumpSpeed, jumpSustainTime)


# peakTime > jumpSustainTime && peakTime < maxFallingSpeedReachTime #

currentJumpSpeed(t, gravity, jumpSpeed, jumpSustainTime) = -jumpSpeed + gravity * (t - jumpSustainTime)
speed(t, gravity, jumpSpeed, jumpSustainTime) = currentJumpSpeed(t, gravity, jumpSpeed, jumpSustainTime) + currentFallingSpeed(t, gravity)
peakTime(gravity, jumpSpeed, jumpSustainTime) = solve([speed(t, gravity, jumpSpeed, jumpSustainTime)==0], t)[0].rhs()
height(t, gravity, jumpSpeed, jumpSustainTime) = sustainHeight(jumpSustainTime, gravity, jumpSpeed) + integral(speed(t, gravity, jumpSpeed, jumpSustainTime), t, jumpSustainTime, t)
peakHeight(gravity, jumpSpeed, jumpSustainTime) = height(peakTime(gravity, jumpSpeed, jumpSustainTime), gravity, jumpSpeed, jumpSustainTime)


# peakTime > jumpSustainTime && peakTime > maxFallingSpeedReachTime #

maxFallingSpeedReachedTime(gravity, maxFallingSpeed) = solve([currentFallingSpeed(t, gravity)==maxFallingSpeed],t)[0].rhs()
maxFallingSpeedReachedSpeed(t, gravity, jumpSpeed, jumpSustainTime, maxFallingSpeed) = currentJumpSpeed(t, gravity, jumpSpeed, jumpSustainTime) + maxFallingSpeed
maxFallingSpeedReachedPeakTime(gravity, jumpSpeed, jumpSustainTime, maxFallingSpeed) = solve([maxFallingSpeedReachedSpeed(t, gravity, jumpSpeed, jumpSustainTime, maxFallingSpeed)==0], t)[0].rhs()
maxFallingSpeedReachedHeight(t, gravity, jumpSpeed, jumpSustainTime, maxFallingSpeed) = height(maxFallingSpeedReachedTime(gravity, maxFallingSpeed), gravity, jumpSpeed, jumpSustainTime) + integral(maxFallingSpeedReachedSpeed(t, gravity, jumpSpeed, jumpSustainTime, maxFallingSpeed), t, maxFallingSpeedReachedTime(gravity, maxFallingSpeed), t)
maxFallingSpeedReachedPeakHeight(gravity, jumpSpeed, jumpSustainTime, maxFallingSpeed) = maxFallingSpeedReachedHeight(maxFallingSpeedReachedPeakTime(gravity, jumpSpeed, jumpSustainTime, maxFallingSpeed), gravity, jumpSpeed, jumpSustainTime, maxFallingSpeed)


# peakTime < jumpSustainTime && peakTime > maxFallingSpeedReachTime #
# in this case the speed is constant (-jumpSpeed + maxFallingSpeed) there is no strict maximum. #

affineCaseSpeed(t, jumpSpeed, maxFallingSpeed) = -jumpSpeed + maxFallingSpeed
affineCaseHeight(t, jumpSpeed, maxFallingSpeed) = sustainHeight(maxFallingSpeedReachedTime(gravity, maxFallingSpeed), gravity, jumpSpeed) + integral(affineCaseSpeed(t, jumpSpeed, maxFallingSpeed), t, maxFallingSpeedReachedTime(gravity, maxFallingSpeed), t)

For instance, this is the resulting code to solve the initial speed from a given jump height. It has some branches because of the piecewise nature of the y function.

const maxFallingSpeedReachedTime = maxFallingSpeed / gravity;

let jumpSpeed = -gravity * jumpSustainTime + Math.sqrt(2 * gravity * gravity * jumpSustainTime * jumpSustainTime - 4 * jumpHeight * gravity);
let peakTime = (gravity * jumpSustainTime + jumpSpeed) / (2 * gravity);

// If the peakTime is outside of the piecwise part,
// use the formula for this part.
if (peakTime > maxFallingSpeedReachedTime) {
    jumpSpeed = -gravity * jumpSustainTime + maxFallingSpeed
        + Math.sqrt(gravity * gravity * jumpSustainTime * jumpSustainTime - 2 * jumpHeight * gravity - maxFallingSpeed * maxFallingSpeed);
    peakTime = (gravity * jumpSustainTime + jumpSpeed - maxFallingSpeed) / gravity;
    // Same here, use the formula of the other side.
    if (peakTime < jumpSustainTime) {
        jumpSpeed = Math.sqrt(-jumpHeight * gravity * 2);
    }
}
else if (peakTime < jumpSustainTime) {
    jumpSpeed = Math.sqrt(-jumpHeight * gravity * 2);
    peakTime = jumpSpeed / gravity;
    // Same here, use the formula of the other side.
    if (peakTime > maxFallingSpeedReachedTime) {
        jumpSpeed = -gravity * jumpSustainTime + maxFallingSpeed
            + Math.sqrt(gravity * gravity * jumpSustainTime * jumpSustainTime - 2 * jumpHeight * gravity - maxFallingSpeed * maxFallingSpeed);
        peakTime = (gravity * jumpSustainTime + jumpSpeed - maxFallingSpeed) / gravity;
    }
}
if (jumpSpeed >= 0) {
    character.setJumpSpeed(jumpSpeed);
}

[4ian]

Nice!

Do you think it could be interesting to have it in the technical documentation of the platformer extension?

Totally! We can have it in the platformer behavior README :)

For instance, this is the resulting code to solve the initial speed from a given jump height. It has some branches because of the piecewise nature of the y function

Do you see it useful as an example, like the one you did?
We could also add links to this example on the wiki.

[D8H]

The PR:

• [Platformer] Add a frame rate independent movement mode. #3417

The documentation:

• https://github.com/4ian/GDevelop/blob/master/Extensions/PlatformBehavior/README.md#jump-trajectory

The extension PR:

• [PlatformerTrajectory] Add a behavior to evaluate jump trajectories. GDevelopApp/GDevelop-extensions#334