Overshooting when traversing between two points with a set velocity

Question

I'm creating a prototype for something I may make into a game and I've run into difficulty in creating a method to move a ship along a line between two points. While it reaches the end point, it either over/undershoots the end point on either the x or y. Applying a floor or ceiling arbitrarily won't work for all circumstances depending on what direction I'm travelling either.

I'm certain there must be a better way.

I've got the logic of creating a line between them using ArcTan2 but I'm finding that I will always get an over shot of the destination. I think I've been toying with it too long to arrive at a sensible solution that's not a kludge fixed with several conditional statements. I'm using C# but only while I'm at this stage.

A few definitions:

Name	Type	Initial Value	Meaning
xpos	float	4	The current horizontal position of the ship
ypos	float	12	The current vertical position of the ship
xhead	float	14	The horizontal position of the destination
yhead	float	7	The vertical position of the destination
speed	float	2	The ship's speed, measured in position units per step
dist	float	11.18034	The current distance between the ship and its destination
deltaX	float	10	The signed offset from the ship to the destination, horizontally
deltaY	float	-5	The signed offset from the ship to the destination, vertically
angle	float)	-0.4636476	The angle the ship needs to travel, measured in radians counter-clockwise from the positive x axis

Using the standard Euclidian distance between xpos,ypos and xhead,yhead I obtain the distance and then by using Atan2 and the deltas I get the angle above.

here is my current code (ToPoint is an ext method turning xpos and ypos into a PointF as is Distance. headToPoint is xhead,yhead to a PointF):

        trail = new List<PointF>();
        steps = new List<PointF>();
        stepsIX = 0;
        float origDistance = (float)Math.Sqrt(Math.Pow(xhead - xpos, 2) + Math.Pow(yhead - ypos, 2));
        float segSize = origDistance / speed;
        float distance = origDistance;
        float lastdistance = distance;

        float deltaX = xhead - xpos;
        float deltaY = yhead - ypos;
        float angle = (float)Math.Atan2(deltaY, deltaX);

        steps.Add(this.ToPoint());

        while (distance >= 0)
        {
          PointF last = steps[steps.Count() - 1];
          lastdistance = (float)Math.Sqrt(Math.Pow(xhead - last.X, 2) + Math.Pow(yhead - last.Y, 2));
          float nx = last.X + (float)(speed * Math.Cos(angle));
          float ny = last.Y + (float)(speed * Math.Sin(angle));
          PointF np = new PointF(nx, ny);
          distance = np.Distance(headToPoint());


          if (distance > lastdistance)
          {
            break;
          }


          steps.Add(np);
        }

Output of steps:

START: {X=4, Y=12}
TARGET: {X=14, Y=7} 
--Steps--
{X=4, Y=12}
{X=5.788855, Y=11.10557}
{X=7.577709, Y=10.21115}
{X=9.366564, Y=9.316718}
{X=11.15542, Y=8.422291}
{X=12.94427, Y=7.527864}
{X=14.73313, Y=6.633436}

Many thanks to anyone who reads this or has any ideas!

Answer 1

This can be done much more simply. We don't need trigonometry and angles where simple vector normalization and arithmetic suffices.

bool StepToward(
        ref float currentX, ref float currentY,
        float destinationX, float destinationY,
        float maxStepDistance
) {
    // Compute the offset from our current position to the destination.
    float dX = destinationX - currentX;
    float dY = destinationY - currentY;

    // Get our distance away (we could defer this square root, but the
    // majority of the time we have to do it anyway, so let's bite the bullet.
    float distance = (float)Math.Sqrt(dX * dX + dY * dY);

    // If we're within one step of our destination, reach it exactly,
    // and report back that we have arrived (true).
    if (distance <= maxStepDistance) {
        currentX = destinationX;
        currentY = destinationY;
        return true;
    }

    // Otherwise, get an offset vector in the direction of our destination,
    // clamped to the length of our maximum allowable step.
    // Use it to advance one step distance toward the destination.
    float scale = maxStepDistance / distance;
    currentX += dX * scale;
    currentY += dY * scale;

    // Report back that we still have farther to go.
    return false;
}

Your loop can then be something like:

// Log starting point.
steps.Add(ToPoint());

// Step until we reach the destination.
while (!StepToward(ref xpos, ref ypos, headX, headY, speed)) {
   // Recording each intermediate step we take.
   steps.Add(steps.Add(ToPoint());
}

// Log our arrival at the destination.
steps.Add(ToPoint());

---

You could also do this in one big batch:

// Compute the offset and distance from our start position to the destination.
float deltaX = headX - posx;
float deltaY = headY - posy;
float distance = (float)Math.Sqrt(deltaX * deltaX + deltaY * deltaY);

// Compute how many steps it will take to reach it at this speed.
float stepCount = distance / speed;
int wholeStepCount = (int)stepCount;

// Compute an incremental movement to apply with each step.
float scale = speed / distance;
float stepX = deltaX * scale;
float stepY = deltaY * scale;

// Add whole steps 0...n to our list.
for (int i = 0; i <= stepCount; i++) {
    steps.Add(new PointF(posx + i * stepX, posy + i * stepY));
}

// If there's any remainder, add our fractional step to arrive exactly.
if (wholeStepCount < stepCount) {
    steps.Add(new PointF(headX, headY));
}