# Moving a sprite along a curved path

This topic is 2784 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I'm new to the forum.
I'm trying to create a 2D game in C# (XNA 3.1) where you can operate a tram; the game has a bird's-eye view.
So far I've managed to make it work in straight lines: I'm actually moving the background, and it works just fine.

My problem is: how do I make a curve? I'm having problems monitoring position and rotation of the sprite (I'm moving the tram in this case, as opposed to the background), as I can't seem to find a way to exactly determine where and when it should rotate and how much.

Is there some way to re-create a smooth curve with accurate positioning of the sprite? (by the way, the tram is also articulated so it's even worse )

I understand that I probably need some math, but I have no idea where to begin.

##### Share on other sites
Hi!

I assume the tram is following some pre-determined path, so along some tracks, right?
In this case, you could describe the path (as some sort of list of way points) with the help of a spline, for instance a Cubic Hermite Spline.
As you probably know, a spline is a sequence of curves. Cubic means the segments are cubic polynomials.

Cubic Hermite Spline segments are defined by a:

• start point [formula]p_0[/formula],
• start direction [formula]m_0[/formula],
• end point [formula]p_1[/formula],
• end direction [formula]m_1[/formula].

For each segment the parametric curve describing the position is (cf.wiki)
[formula]\mathbf{p}(t) = (2t^3-3t^2+1)\mathbf{p_0}[/formula][formula] + (t^3-t^2+t)\mathbf{m_0} + (-2t^3+3t^2)\mathbf{p_1} + (t^3-t^2)\mathbf{m_1}[/formula]
XNA implements this in Vector3.Hermite(..).

The derivation gives us the tangent:
[Formula]\mathbf{\dot{p}}(t) = (6t^2-6t)\mathbf{p_0} [/Formula][Formula] + (3t^2-2t+1)\mathbf{m_0} + (-6t^2+6t)\mathbf{p_1} + (3t^2-2t)\mathbf{m_1}[/Formula]

The angle of the sprite would be
[Formula]alpha(t) = atan2( \mathbf{\dot{p}}(t).y, \mathbf{\dot{p}}(t).x) [/Formula]
.
If you have trouble choosing the directions [formula]m_0[/formula], [formula]m_1[/formula], etc… you could simply use Catmull Rom Splines. They are a special case of Hermite Splines, where you set as direction vector the difference between the next and previous way point.
As an example for a sequence of three sequent points [formula]p_0[/formula], [formula]p_1[/formula], [formula]p_2[/formula] we would set
[formula]m_0=p_1-p_0[/formula] (boundary condition)
[formula]m_1=p_2-p_0[/formula] (next – previous)
[formula]m_2=p_2-p_1[/formula] (boundary condition)
(Normalizing those is probably a good idea.)

I hope this helps you a little to get on the right track (pun intended).
Cheers!

##### Share on other sites
OK, first of all thanks a lot for answering so quickly!
I hope I understood correctly what you wrote, unfortunately I didn't yet have a chance to study this particular math subject (I just finished the equivalent of Single Variable Calculus).

If I'm right, basically I should create a series of vectors that represent the various points and directions of my path.
I can easily calculate the rotation of the sprite with the formula.

What I didn't get is how exactly does the "Hermite" function gives me my position. It returns a vector, but what does it represent? I was thinking, "the tangent at that point", but shouldn't that be p'(t)? Maybe it just gives the coordinates as the components of the vector?
Also, why should I use Vector3.Hermite instead of Vector2.Hermite?

I hope I'm not being too annoying with all these questions, I'm usually pretty good at maths but this is all new for me

##### Share on other sites
Hi!

If I'm right, basically I should create a series of vectors that represent the various points and directions of my path.
I can easily calculate the rotation of the sprite with the formula.

Jep, that‘s right.

What I didn't get is how exactly does the "Hermite" function gives me my position. It returns a vector, but what does it represent? I was thinking, "the tangent at that point", but shouldn't that be p'(t)? Maybe it just gives the coordinates as the components of the vector?

You probably know the linear interpolation:
[formula]f(p_0, p_1 ,t) = p_0(1-t) + p_1t[/formula]
Pretty much like the linear interpolation the Hermite function interpolates between two points, but with Hermite functions you can specify at [formula]p_0[/formula] and [formula]p_1[/formula] a direction. (In contrast to that linear interpolations just use the direction of the shortest connection.) So, instead of interpolating along a line, we use a cubic polynomial.
Similar to linear interpolations, Hermite interpolations also have end point interpolation, which means:
[formula]Hermite(p_0, m_0, p_1, m_1, 0) = p_0[/formula]
[formula]Hermite(p_0, m_0, p_1, m_1, 1) = p_1[/formula]
As you can see, you interpolate between two points over the domain [0,1]. 0 is the start point, 1 is the end point. (Very much like with linear interpolations.)
So, yes, the vector the Hermite function returns is exactly the position you are looking for.
Unfortunately, XNA brings no helper for the derivative (=tangent) of the polynomial that’s behind the Hermite interpolation, so I wrote that down for you.

Also, why should I use Vector3.Hermite instead of Vector2.Hermite?

Sorry, my bad, I usually use it in 3D. You can of course use Vector2.Hermite.

I hope I'm not being too annoying with all these questions, I'm usually pretty good at maths but this is all new for me

Don’t mind, you’re welcome to ask.

At first this might look like some magic going on here, but actually Hermite interpolations are just a special case of a Bezier curve, with the four control points: [formula]p_0[/formula], [formula]p_0+m_0/3[/formula], [formula]p_1-m_1/3[/formula] and [formula]p_1[/formula]. Do you know Bezier curves?

Cheers!

##### Share on other sites
Thanks a lot for the help, it's actually working pretty well now!
(BTW, I used Catmull-Rom splines in the end)

Do you mind if I ask you one more question? (I hope it's the last one :-P)
Since i'm trying to obiouvsly keep my speed equal to the one that I had on a straight line,
I'd like to have evenly-distributed points. However, currently my tram accelerates on some parts
and dramatically decelerates on others. I'm pretty sure it's due to the fact that sometimes I'm
given closer points than other times, because the increment on t is constant.

Is there any way to force it to give me points with a constant distance?

##### Share on other sites

Thanks a lot for the help, it's actually working pretty well now!
(BTW, I used Catmull-Rom splines in the end)

Very good.

Since i'm trying to obiouvsly keep my speed equal to the one that I had on a straight line,
I'd like to have evenly-distributed points. However, currently my tram accelerates on some parts
and dramatically decelerates on others. I'm pretty sure it's due to the fact that sometimes I'm
given closer points than other times, because the increment on t is constant.

Is there any way to force it to give me points with a constant distance?

Instead of introducing further points one would rather reparameterize the curve.

To have uniform velocity one would try to construct a so called arc length parameterization. Finding those exactly is a little tricky. You'd have to compute the length of the curve segments, by integrating the polynomials used in the curve.
But you can also approximate it discretely with a chordal parameterization.
Currently you have:
[Formula]\Delta t_i = \left |t_i-t_{i-1} \right |=1=const[/Formula]
For a chordal parameterization you would use:
[Formula]\Delta t_i = \left\| p_i-p_{i-1} \right \| [/Formula]

So what you basically do is:
Iterate over your path and build a list of the accumulated distances between adjacent points. Let's say the distances are 1,2,3,2. What you store is the sum of the previous distances: 0,1,1+2,1+2+3,1+2+3+2 = 0,1,3,6,8.
So the first curve segment goes from 0 to 1. The second segment from 1 to 3, the third segment from 3 to 6 and so on.
To move along the path you increment your interpolation value s and look into the list at which position you are. Let's say s=4. This would be between 3 and 6, so the third curve segment. The value for the Catmull-Rom interpolation would be:
[Formula]t = (s-min)/(max-min) = (4-3)(6-3) = 1/3[/Formula]
As I said, it is not a real arc length parameterization, but it should be close enough.

Hope that helps.
Cheers!

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 9
• 11
• 15
• 21
• 26