# C++ Figuring out where we are on a curvy path

## Recommended Posts

So, I'm kinda confused about how I should create, store (in structs at runtime), and interpolate along potentially curvy paths.

Suppose I have a path of, say, ten points. And I want to move an entity 200 units along that path. Those ten points aren't an equal distance from each other, even linearly.

How do I know where 200 units into the path is?
If I have a vector of ten points, how do I know 200 units of movement along that path lies between point 6 and 7?

I could store the distances between each point *also*, and do:

float segmentDistance = totalDistanceThrough;
size_t i = 0;
while(segmentDistance > pathSegmentLength[i])
{
segmentDistance -= pathSegmentLength[i];
++i;
}

We are between: pathPoint[i] and pathPoint[i+1],

...but the iterating over every path segment length subtracting from the distance seems dumb.

I'm pretty bad at math, but there has to be a more elegant way.

What's a better more-common way to store paths and move along them? For example, what information do you store alongside your path control points?

##### Share on other sites
6 hours ago, Servant of the Lord said:

...but the iterating over every path segment length subtracting from the distance seems dumb.

But is also not too bad for just 10 points and a densely packed array of distances (i.e. cache friendly accesses).

There may be some improvements If the path consists of notably more points:

a) You may store not the distance from one point to the next but from the very beginning to the particular point, i.e. an array of ever increasing distance values. This would simply allow for binary search.

b) If the point of interest does not wildly jump back and forth on the path but "wanders" in some orderly manner (and "moving an entity along" seems me to be such a thing), then the previously found position (i.e. its index) can be stored and be used as the starting point of a linear search in the next iteration. Usually only one or just a few search steps will be necessary. You may further know the direction of search (up or down the path) in front of the search.

Edited by haegarr

##### Share on other sites

Thank you, that definitely helped get me going in the right direction.

##### Share on other sites

If you can represent your segments as splines instead of line segments, you can trivially compute the length of each spline section and sum them up. I have some C# code somewhere that demonstrates how to do spline interpolation for path segments, if that'd be useful.

 Not to say you can't accomplish this with plain segments - but you can get much more graceful curves with splines.

## Create an account

Register a new account

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5
JoeJ
12

• 12
• 21
• 9
• 31
• 16
• ### Forum Statistics

• Total Topics
632618
• Total Posts
3007466
• ### Who's Online (See full list)

There are no registered users currently online

×