Coordinate based travel through multi-line path over elapsed time

Question

I have implemented A* Path finding to decide the course of a sprite through multiple waypoints. I have done this for point A to point B locations but am having trouble with multiple waypoints, because on slower devices when the FPS slows and the sprite travels PAST a waypoint I am lost as to the math to switch directions at the proper place.

EDIT: To clarify my path finding code is separate in a game thread, this onUpdate method lives in a sprite like class which happens in the UI thread for sprite updating. To be even more clear the path is only updated when objects block the map, at any given point the current path could change but that should not affect the design of the algorithm if I am not mistaken. I do believe all components involved are well designed and accurate, aside from this piece :- )

Here is the scenario:

public void onUpdate(float pSecondsElapsed)
{
    // this could be 4x speed, so on slow devices the travel moved between
    // frames could be very large. What happens with my original algorithm
    // is it will start actually doing circles around the next waypoint..
    pSecondsElapsed *= SomeSpeedModificationValue;

    final int spriteCurrentX = this.getX();
    final int spriteCurrentY = this.getY();

    // getCoords contains a large array of the coordinates to each waypoint.
    // A waypoint is a destination on the map, defined by tile column/row. The
    // path finder converts these waypoints to X,Y coords.
    //
    // I.E:
    // Given a set of waypoints of 0,0 to 12,23 to 23, 0 on a 23x23 tile map, each tile
    // being 32x32 pixels. This would translate in the path finder to this:
    //    -> 0,0 to 12,23
    //        Coord : x=16 y=16
    //        Coord : x=16 y=48
    //        Coord : x=16 y=80
    //          ...
    //        Coord : x=336 y=688
    //        Coord : x=336 y=720
    //        Coord : x=368 y=720
    //
    //    -> 12,23 to 23,0 -NOTE This direction change gives me trouble specifically
    //        Coord : x=400 y=752
    //        Coord : x=400 y=720
    //        Coord : x=400 y=688
    //          ...
    //        Coord : x=688 y=16
    //        Coord : x=688 y=0
    //        Coord : x=720 y=0
    //
    // The current update index, the index specifies the coordinate that you see above
    // I.E. final int[] coords = getCoords( 2 ); -> x=16 y=80
    final int[] coords = getCoords( ... );

    // now I have the coords, how do I detect where to set the position? The tricky part
    // for me is when a direction changes, how do I calculate based on the elapsed time
    // how far to go up the new direction... I just can't wrap my head around this.

    this.setPosition(newX, newY);
}

Answer 1

When using a variable time-step, the game becomes non deterministic, as you can see it can break the flow of gameplay on a slower device.

The easiest way to fix this error would be to implement a fixed timestep with interpolation. If implemented correctly the logic of the game will always update at the same rate, and becomes deterministic, meaning a simulation will always play out the same(if there are no random numbers, or if there are random numbers the random numbers are seeded the same way).

Here is an answer with resources on how to implement a fixed timestep.
Semi-fixed or Fully-fixed timestep?

Here is an answer that explains how to implement interpolation for movement and transformations.
How to Interpolate between two game states?