Find position on a path

Question

I am building a 2D game, I got a path of $N$ coordinates where $N$ is a small integer. I calculated the path total length to be $L$, and I decided that I would like to complete the path within some fixed time, so during each frame, I am calculating where my location on the path should be.

Assuming that my location is $fL$ where $f$ is a number between $0$ to $1$, how can I calculate the coordinates of my location?

Answer 1

The standard technique here is surprisingly boring. In pseudocode, you write something like this:

preprocessing: 
input: pts, an array of N points indicating a piecewise
            linear path.

distances[0] = 0.0; 
for i = 1 to N-1
   distances[i] = distances[i-1] + dist(pts[i], pts[i-1]); 

L = lengths[N-1]; // total length of the path. 

main program:
input:
input: pts, an array of N points indicating a piecewise
            linear path.
       f, a fraction between 0 and 1. 
       L, the total length of the path
       distances, an array of distances along the path. 

output: q, a point along the path that's f of the way from 
       pts[0] to pts[N-1]. 

target = f * L; // the distance we want to go. 
i = 0; 
while (lengths[i] < target) i = i + 1; 

// Now lengths[i-1] < target <= lengths[i]
u = pts[i-1]; 
v = pts[i];
h = lengths[i] - lengths[i-1]; // distance between the pts
r = target - lengths[i-1]; // distance still to be covered. 
t = r/h; // fraction of the distance from u to v we have to go. 
q = (1-t) * u + t * v; 

The idea is that if you have 3 points, at distances 0, 3, and 5.5, for a total length of 5.5, and you want to go 70% of the way (f = 0.7), then you compute $0.7 \cdot 5.5 = 3.85$. So you want to get to the point that's at distance 3.85 from the start. You walk the first edge, and use up distance $3,$ and now need to got $0.85$ more. The length of the second edge of your path is $5.5 - 3 = 2.5$, so you need to go $0.85$ of the total distance of $2.5$. That's a fraction $t = 0.85/2.5 = 0.34$ of the distance. To get that, you call the second and third points $u$ and $v$, and compute the point $(1-0.34)u + 0.34 v$, and that's your result.

N.B.

1. This works in any dimension, not just 2.

2. I've made the simplest possible assumption about your path, namely, that it's a sequence of straight line segments. The only simpler assumption --- that you "teleport" from one point to the next, resting at each location in sequence, has the problem that there may be no solution to the problem posed. For instance, if you start at $(0,0)$ and then teleport to $(3, 0)$, what answer should I give for $f = 0.5$? The obvious answer is $(1.5, 0)$, but you were never at that point. In fancier terms, I've assumed a $C^1$ interpolant for your data, because the $C^0$ interpolant doesn't work. If you want a smoother output, you'll need to choose a higher-order interpolant, and spline technology is probably what you're looking for...until you realize what a mess it is. If you go that route, I strongly suggest you consider the Catmull-Rom spline.

3. I've tried to answer the question I thought you were asking, but there's a real skill in learning to ask the question you really need answered so that you get what you want, and don't waste others' time. If you look back at your question, you might want to think about "How could I have asked this more usefully?" You might, for instance, have included an example. You might have said "from the input points, I'm assuming a "connect-the-dots" kind of path." Or you might have said "Is there something better than a connect-the-dots path for which this computation is still easy?"