0
\$\begingroup\$

I have a formula which returns a Lerp Vector3 value in integers but the problem is it never reaches the desired target value. It's converting to pixel values first by multiplying by PPM which is float 32f.

private Vector3 lerp(final Vector3 source, final Vector3 target, float alpha) {
    Vector3 sourcePPM = new Vector3(source.x * PPM, source.y * PPM, 0);
    Vector3 targetPPM = new Vector3(target.x * PPM, target.y * PPM, 0);
    sourcePPM.x += Math.round(alpha * (targetPPM.x - sourcePPM.x));
    sourcePPM.y += Math.round(alpha * (targetPPM.y - sourcePPM.y));
    source.x = sourcePPM.x / PPM;
    source.y = sourcePPM.y / PPM;
    source.z = 0;
    return source;
}

I initialize my vector variable source to new Vector3(0.0, 0.0, 0.0). Then, each frame I update it like this:

source = lerp(source, new Vector3(26.0, 29.0, 0.0), 0.06f);

But instead of eventually reaching the target, the value plateaus at a certain point:

Target destination: (26.0,29.0,0.0)
Actual final destination: (25.75,28.75,0.0)

Falling short of the target destination. If I don't round the values then it gets there fine but I need it to be in whole pixels.

The final line of intermediate values (too many to add all of them):

(25.0,27.90625,0.0)
(25.0625,27.96875,0.0)
(25.125,28.03125,0.0)
(25.1875,28.09375,0.0)
(25.25,28.15625,0.0)
(25.28125,28.21875,0.0)
(25.3125,28.28125,0.0)
(25.34375,28.3125,0.0)
(25.375,28.34375,0.0)
(25.40625,28.375,0.0)
(25.4375,28.40625,0.0)
(25.46875,28.4375,0.0)
(25.5,28.46875,0.0)
(25.53125,28.5,0.0)
(25.5625,28.53125,0.0)
(25.59375,28.5625,0.0)
(25.625,28.59375,0.0)
(25.65625,28.625,0.0)
(25.6875,28.65625,0.0)
(25.71875,28.6875,0.0)
(25.75,28.71875,0.0)
(25.75,28.75,0.0)
\$\endgroup\$
  • \$\begingroup\$ Somewhat tangentially, I think "Debugging with the scientific method" is an absolutely excellent talk. You may enjoy and benefit from watching it. It's at youtube.com/watch?v=FihU5JxmnBg \$\endgroup\$ – Jonas Kölker Jun 12 at 10:58
  • \$\begingroup\$ Here's a hypothesis: when source and target are sufficiently close to each other, Math.round(alpha * (targetPPM.x - sourcePPM.x)) is zero, leading source to not be modified. \$\endgroup\$ – Jonas Kölker Jun 12 at 12:47
4
\$\begingroup\$

The Greek philosopher Zeno proposed a paradox: an arrow can never strike its target. In order to do so, it would have to:

  • First, cross half the distance to its target.

  • Then, cross half the remaining distance (one quarter of the original distance)

  • Then, cross half that remaining distance (one eighth of the original)

  • Then, cross half of that remaining distance (one sixteenth of the original)

  • Then...

Because we can continue taking halves forever, this means there's an infinite number of steps the arrow has to take to reach the target. How could we ever perform infinite actions in finite time?

The solution to Zeno's paradox is the (apparently) continuous nature of time and space. Because each of these steps takes less and less time, while still making tiny increments of progress, we can show with calculus that the sum of all these infinite steps really does take only a finite amount of time, and summing all those infinite infinitesimals really does bring us all the way to our target.

Why does this matter? Because when you use this pattern for lerp:

current (variable) = lerp(current (variable), target (fixed), alpha (fixed));

Instead of this one:

current (variable) = lerp(start (fixed), end (fixed), progress (variable));

You're saying "I want my object to move like Zeno's arrow" - what we call an "exponential ease-out" motion, or "exponential moving average" if the target can change mid-flight.

The amount your current variable changes each frame is proportional to how far it still has to go:

  • In your first call, when current is a long way from target, that difference is large, and alpha times that distance is proportionately large, so your current variable changes a lot.

  • But as current gets closer and closer to target, the difference gets less and less, so alpha times that distance is proportionately smaller, and your current variable starts moving more slowly.

Now, because space isn't very continuous in your game - it's rounded to discrete pixels - there comes a point where the difference between current and target is so small that after multiplying by alpha, it rounds to zero. The arrow never reaches its target, and Zeno is right! (For a different reason than he had in mind though).

So, some potential solutions:

  1. Let your underlying vector in the feedback loop stay unrounded, but then save its rounded value to another variable you use for your simulation/display:
   unroundedPosition = unroundedLerp(unroundedPosition, target, alpha);
   roundedPosition = Round(unroundedPosition * PPM)/PPM;

   // Use `roundedPosition` for anything that reads this object's position.
  1. Detect the case where you round to zero, and fudge it to avoid getting stuck:
    private Vector3 roundedLerp(final Vector3 source, final Vector3 target, float alpha) {
        Vector3 sourcePPM = new Vector3(source.x * PPM, source.y * PPM, 0);
        Vector3 targetPPM = new Vector3(target.x * PPM, target.y * PPM, 0);

        float deltaX = (targetPPM.x - sourcePPM.x);
        // If we can make a whole pixel of progress with alpha, proceed as normal.
        if(Math.abs(alpha * deltaX) > 0.5) {
            sourcePPM.x += Math.round(alpha * deltaX);            
        // Otherwise, if we're more than half a pixel from our target, advance one pixel.
        } else if(Mathf.abs(deltaX) > 0.5) {
            sourcePPM.x += Math.signum(deltaX);
        } 

        float deltaY = (targetPPM.y - sourcePPM.y);
        if(Math.abs(alpha * deltaY) > 0.5) {
            sourcePPM.y += Math.round(alpha * deltaY);            
        } else if(Mathf.abs(deltaY) > 0.5) {
            sourcePPM.y += Math.signum(deltaY);
        } 

        source.x = sourcePPM.x / PPM;
        source.y = sourcePPM.y / PPM;
        source.z = 0;
        return source;
    }
  1. Use the non-exponential form of lerp, and add any easing you want yourself:
    // Store a progress variable that goes from zero to 1 over your desired movement.
    progress = Math.Min(progress + deltaTime/transitionDuration, 1);

    // This gives you a quadratic ease-out: fast at the start, slow at the finish.
    float easeOut = 1 - (1 - progress) * (1 - progress);

    currentPosition = roundedLerp(startPosition, endPosition, easeOut);
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You came back after all, that's great. Looks like we probably have the solution here. Your fudge formula does work although it's rather a big jump to get to the final destination at the end. It goes from (25.75,28.71875,0.0) to (26.0,28.75,0.0). In PPM terms that's quite a big jump. \$\endgroup\$ – Hasen Jun 12 at 14:37
  • \$\begingroup\$ For a lesser fudge, you can try the edited version, which advances one pixel at a time once it's so close that rounding the multiple of alpha drops to zero. \$\endgroup\$ – DMGregory Jun 12 at 15:28
  • \$\begingroup\$ ♦ Ok I'll take a look at it. In any case in the meantime I was using the first solution which works fine too. \$\endgroup\$ – Hasen Jun 14 at 5:25
  • \$\begingroup\$ The first solution is definitely a better option. \$\endgroup\$ – DMGregory Jun 14 at 9:30
0
\$\begingroup\$

Here's what I would do and think about in your shoes:

  • Print all the intermediate values. That might show you where the problem lies. If any value is not as expected, change your mental model (this may require research) such that your new model agrees with what you observed.
  • My first guess about how to do this is to convert your given data to floats, calculate the lerp with floats, then convert the final result back to integers by rounding to nearest.
  • Does Math.round round down, up, towards zero, to nearest integer? Make sure it does what you expect.

I can perhaps give a better answer if you print all the intermediate values and expand your question around the first value that surprises you. Note: You haven't showed us the Vector3 constructor nor the type and precise value of PPM (is it 32.0? Float or double?). Those might be helpful too.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think this would be better suited as a comment since they are suggestions. I already tried it with floats and then rounding to integers, it has the same result. PPM if float 32f. I'll update my answer with that. I added some intermediate values, but not all since there are way too many. \$\endgroup\$ – Hasen Jun 12 at 11:23
  • \$\begingroup\$ I see that I was unclear: by intermediate I didn't mean "various different values of alpha", which is what I think you did. What I meant was printing the values of all the subexpressions. For example, printing sourcePPM.x before and after you've mutated it (with the highest value of alpha you give your function), and sourcePPM.y, and printing the value of the Math.round(...) expression, and printing source.x after you've set it, and so on. \$\endgroup\$ – Jonas Kölker Jun 12 at 11:54
  • \$\begingroup\$ Interestingly, with Math.ceil it finds it's destination, as long as x and y target values are positive values...if not it's even further off than Math.round. Math.floor would no doubt have the opposite effect. \$\endgroup\$ – Hasen Jun 12 at 11:58
  • \$\begingroup\$ Are you saying you need all those values in my question or that I look at those values myself? I've already been looking at every possible value, before and after, I have a million print line commands for every different value which I comment and uncomment. The only progress I've made though was about the rounding after your suggestion, as I detailed in the comment above. \$\endgroup\$ – Hasen Jun 12 at 12:10
  • \$\begingroup\$ I recommend you look at all the printed values, for a single call to lerp, and explain more clearly which of the values you're surprised by. But actually I think @DMGregory is closer to helping you find the problem. \$\endgroup\$ – Jonas Kölker Jun 12 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.