Jump to content
  • Advertisement
Sign in to follow this  
Servant of the Lord

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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.

 

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!