Jump to content
  • Advertisement
Sign in to follow this  
srsmania

Moving a sprite along a curved path

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm new to the forum.
I'd like to ask a question about programming in XNA.
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 tongue.png)

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

Share this post


Link to post
Share on other sites
Advertisement
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). smile.png
    Cheers!

Share this post


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

Share this post


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

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

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


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


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


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. smile.png
Cheers!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!