Following a set of points?

Question

Lets assume that i have a set of path that an entity should follow :

const int Paths = 2
Vector2D<float> Path[Paths] = { Vector2D(100,0),Vector2D(100,50)   };

Now i define my entity's position in a 2D vector as follows :

Vector2D<float> FollowerPosition(0,0);

And now i would like to move the "follower" to the path at index 1 :

int PathPosition = 0; //Start with path 1

Currently i do this :

Vector2D<float>& Target = Path[PathPosition];
bool Changed = false;

if (FollowerPosition.X < Target.X) FollowerPosition.X += Vel,Changed = true;
if (FollowerPosition.X > Target.X) FollowerPosition.X -= Vel,Changed = true;
if (FollowerPosition.Y < Target.Y) FollowerPosition.Y += Vel;,Changed = true;
if (FollowerPosition.Y > Target.Y) FollowerPosition.Y -= Vel,Changed = true;

if (!Changed)
{
    PathPosition = PathPosition + 1;
    if (PathPosition > Paths) PathPosition = 0;
}

Which works except for one little detail : The movement is not smooth!! ...So i would like to ask if anyone sees anything wrong with my code.

Thanks and sorry for my english.

Answer 1

If you want fancy looking curves then you might want to use Bezier curves to interpolate between your set of points like below (picture taken from an article mentioned below, it only shows the result of the interpolation though, it doesn't show any "control points" which are discussed later below):

I hope you have some basic linear algebra knowledge.

In short, Bezier curves are mathematical functions allow you to construct a smooth path that passes from a starting point to an ending point while using a set of "control points" to control where and how the path should curve.

P0 is a starting point, P2 is an ending point. P1 is an arbitrary control point that curves the path towards it. The number of control points determine the mathematical order of the Bezier curve. Shown above is a quadratic Bezier curve with the following equation:

You would sample discrete positions along the curve that your object should be at by plugging in values of t ranging from 0 to 1 into the equation.

You can piece together a smooth path from a set of points by combining together a number of Bezier curves and calculate their control points by iterating through a few points at time from the set. Please refer to the following article series for more details:

Bezier Curve Basics

Using Bezier Curve to find a Path from N points

Answer 2

What you're looking for is something called Spline Interpolation or Approximation. There are several ways to achieve this, including Bezier curves, B-Splines, and some naive methods. I'll give a brief overview.

There are two options when it comes to creating curves: Interpolation and Approximation. Interpolation means that the curve will pass directly through the points you specify, while approximation means that the curve will just be influenced by the points you specify. Bezier curves and B-splines are both approximation curves. Both interpolation and approximation have their pros and cons, which are usually related to how the curve actually looks when it's generated (sharp turns, loops, etc).

Another method which I've actually used in an implementation before is called Catmull-Rom spline interpolation. For more information I'll direct you to this question posted on StackOverflow some time ago.

Finally, I'll leave you with a simple method of generating an approximation curve, which you may want to start with before getting into more detailed algorithms. It's called De Casteljau's Algorithm for generating Bezier curves. Given four input points or so, you could generate a longer list of points, perhaps 50, that represent points on the curve at 50 incrementally larger values of t (see the Geometric Interpretation section of that page on de Casteljau's algorithm). Then you can use your current path following algorithm on this new list of points.

EDIT: Alternatively you could have an algorithm which weights the influence of a point in the path by its distance from the object following it. In other words, as an object approaches point A, he is also getting closer to point B, the next point in the path, so some of his velocity will be towards A, and some will also be towards B. Summing these will give a total velocity which falls somewhere between the two. Since weights change with distance, this would theoretically result in a smooth curve as the object follows the path. Note that a lot of tweaking would have to be done to calculate weights to get the desired behavior.

This method is favorable to the spline interpolation I originally posted because it generates much smoother motion, whereas the spline method will suffer from the same problem you are having now, in that motion will not be perfectly smooth, but it will just be less noticeable because the objects moves on a higher resolution path.

Answer 3

If you want to move on lines (not curves), your implementation is almost good enough.

I would edit your code this way:

if (FollowerPosition.X < Target.X) FollowerPosition.X += Vel;
if (FollowerPosition.X >= Target.X) PathPosition = (PathPosition + 1) % (Paths + 1);
if (FollowerPosition.Y < Target.Y) FollowerPosition.Y += Vel;
if (FollowerPosition.Y >= Target.Y) PathPosition = (PathPosition + 1) % (Paths + 1);

This should be almost working except one thing:

Your character will move on line until he's not behind target position, so he doesn't have to stop exactly on line's ending point, but behind it. And then he will turn on other line segment.