getting an object to follow a bezier curve

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 5331 Views - Last Post: 30 May 2013 - 04:24 AM

#1 Geogaddy  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 66
  • Joined: 27-March 11

getting an object to follow a bezier curve

Posted 25 September 2012 - 04:50 AM

Last thing I need to figure out before I can start making my shmup is how to get sprite objects to follow a bezier curve. If I'm totally honest, I'm completely out of my depth here.

A lot of shmups have enemies that appear to be following a curve when they appear on-screen. I know how to move a sprite object using waypoints, but I'm less sure when it comes to bezier curves, since the control points aren't actually the curve itself. Here's my formula, which totally isn't my own work:

private Vector2 GetPoint(float t, Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3)
        {
            float cx = 3 * (p1.X - p0.X);
            float cy = 3 * (p1.Y - p0.Y);

            float bx = 3 * (p2.X - p1.X) - cx;
            float by = 3 * (p2.Y - p1.Y) - cy;

            float ax = p3.X - p0.X - cx - bx;
            float ay = p3.Y - p0.Y - cy - by;

            float Cube = t * t * t;
            float Square = t * t;

            float resX = (ax * Cube) + (bx * Square) + (cx * t) + p0.X;
            float resY = (ay * Cube) + (by * Square) + (cy * t) + p0.Y;

            return new Vector2(resX, resY);
        }



And here's the code I'm using to render the curve:

spriteBatch.Begin();
            Vector2 PlotPoint;
            for (float t = 0; t <= 1.0f; t += 0.01f)
            {
                PlotPoint = GetPoint(t, controlPoint0, controlPoint1, controlPoint2, controlPoint3);
                spriteBatch.Draw(blank, PlotPoint, Color.Gray);
            }
            spriteBatch.End();



The curve renders fine, but I can't for the life of my figure out how to make my sprite object follow the curve. I've tried a couple of things and failed, but I feel like I'm missing some basic comprehension here. Any assistance will, as always, be greatly appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: getting an object to follow a bezier curve

#2 BBeck  Icon User is offline

  • Here to help.
  • member icon


Reputation: 580
  • View blog
  • Posts: 1,287
  • Joined: 24-April 12

Re: getting an object to follow a bezier curve

Posted 25 September 2012 - 07:26 AM

I haven't worked with Bezier curves like you are describing, but I have come across some talk of it in my studies.

I think what you want is Catmull-Rom Interpolation.

Or in 2D:
http://msdn.microsof...catmullrom.aspx

I believe the vectors define the points of the curve and the amount is a percentage defined as a float (1.0 = 100%, 0.53 = 53%) of the amount between the two end points (so an amount of 0.53 would be 53% of the distance between the end points). It looks like it returns a vector to tell you what position that would be. So with even velocity along the curve the percentage becomes the percentage of the curve traveled during that time slice. If it were more than 100% move on to the next curve.

MathHelper even has a 1D version of Catmull-Rom:
http://msdn.microsof...catmullrom.aspx

You also may want to look at this paper, especially if you know Calculus:
http://www.geometric...cifiedSpeed.pdf

It's a bit ugly for those of us who don't know Calculus and I'm sure there's a far more simple explanation of how to get the job done.

Also, check out this blog post on the XNA Curve class.

There are also hermite splines in XNA.

And check out this blog post:
http://glasnost.itca...s/catmulrom.htm

This post has been edited by BBeck: 25 September 2012 - 08:00 AM

Was This Post Helpful? 1
  • +
  • -

#3 Geogaddy  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 66
  • Joined: 27-March 11

Re: getting an object to follow a bezier curve

Posted 25 September 2012 - 08:45 AM

It's tricky. Not only am I not sure which approach shmups typically take in this situation, I don't even know enough about beziers and catmull-roms to make an informed decision. All I know is that I've seen bezier in action in the context of a shmup, and it looked most like what I was after.

Also, my (incredibly limited) understanding of things is that catmull-rom doesn't do circles, which might be a problem.

I'm working on my basic understanding of bezier curves thanks to thispage, which does a pretty good job of explaining it to the layman.

Keeping the code I posted previously in mind, this is the constructor for the object I intend to make follow the curve:

 public Object(Texture2D texture, Rectangle BoundingBox, Vector2 worldLocation, Vector2 velocity, float Speed)
        {
            Texture = texture;
            boundingBox = BoundingBox;
            this.WorldLocation = worldLocation;
            Velocity = velocity;
            speed = Speed;
        }



Now if I were going to try and implement this without a basic understanding of curves, I can't for the life of me figure out how to implement it using these parameters. Regular enemy movement is fine, no problem - but maybe the fact I have no idea what I'm doing with bezier curves is confusing the issue here.

Thanks for the advice. :)
Was This Post Helpful? 0
  • +
  • -

#4 BBeck  Icon User is offline

  • Here to help.
  • member icon


Reputation: 580
  • View blog
  • Posts: 1,287
  • Joined: 24-April 12

Re: getting an object to follow a bezier curve

Posted 25 September 2012 - 09:17 AM

Now you've got me curious about this. I've been trying to find an answer and it seems to be a suprisingly tough question.

The one example I've found (in Sean James's XNA 4.0 book) appears to cheat and draw the race track using Catmull-Rom but then proceeds to define the track as just a set of point and uses linear interpolation in order to move between them. So distance between two points becomes a straight line. It's just a series of straight lines that imitate a curve.

I can't believe someone has not already addressed this. This seems like an extremely common problem. On the other hand, the best answers I've seen so far involve Calculus.
Was This Post Helpful? 0
  • +
  • -

#5 Geogaddy  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 66
  • Joined: 27-March 11

Re: getting an object to follow a bezier curve

Posted 25 September 2012 - 10:09 AM

Googling turns up a lot of high-level stuff relating to XNA and Beziers, but almost all of it goes over my head - there definitely isn't much for the layman to work with.

This forum post goes into detail regarding a solution that, having seen it with my own eyes, seems like exactly what I want. But I suspect that I wouldn't understand most of what he's talking about even with a basic understanding of bezier curves.
Was This Post Helpful? 0
  • +
  • -

#6 BBeck  Icon User is offline

  • Here to help.
  • member icon


Reputation: 580
  • View blog
  • Posts: 1,287
  • Joined: 24-April 12

Re: getting an object to follow a bezier curve

Posted 25 September 2012 - 04:31 PM

Man this problem just gets uglier as you dig into it.

First of all, there's actually 4 parts to the question.

1) In a given amount of time (one frame), how far will an object travel along a bezier curve?
2) What percentage of the curve does that distance represent?
3) What position does that translate to along the curve?
4) What direction will you be facing if you keep aligned with the curve?

You can't really determine the percentage distance unless you know the length of the curve. However, if the curve is bent to any shape other than a straight line, it's length increases. So you have to calculate the length based on the shape of the curve because it may be different for every curve. 50% on one curve may only be 20% on another curve for the exact same distance along the curve with the exact same start and end points.

You also need to get the tangent of the curve at that point in order to calculate facing.

I started to build a program to have a ship travel the path of the curve, so that I could figure it out. But then I realized I didn't understand the shape of the curve generated by the 4 points. So, I changed the program to draw the curve and let you move the handles to see how that changes the shape.

What it ultimately reveals is that the curve is 3D in 2D space. What I mean is that you can even have two straight lines with this Catmull-Rom curve that have different lengths because they are actually in 3 dimensions. The for loop draws a dot (that's a white dot sprite that I made myself, and you'll have to make your own) to show about every 2.5% of the curve. All the dots should be evenly spaced on a straight line. But for these curves the dots can bunch up at the ends or at the center, so you have an infinate number of distances for an infinate number of perfectly straight lines. In short, it's 3D even though it exists in 2D space.

Anyway, here's my code thusfar if you want to mess around with the shape of the curve.

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;

namespace BezierTest
{
    public class Spline
    {
        private Texture2D DotSprite;    //Picture/sprite of a white dot.
        private Vector2 DotSpriteCenter;    //Center of the sprite.
        private Vector2 HandleOne;
        private Vector2 Start;
        private Vector2 End;
        private Vector2 HandleTwo;

        public Vector2 HandleA 
        {
            get 
            {
                return HandleOne;
            }
            set
            { HandleOne = value; } 
        }

        public Vector2 Foot { get { return Start; } set { Start = value; } }
        public Vector2 Head { get { return End; } set { End = value; } }
        public Vector2 HandleB { get {return HandleTwo;} set {HandleTwo = value;} }


        public Spline(Vector2 HandleA, Vector2 Foot, Vector2 Head, Vector2 HandleB, ContentManager Content)
        {
            HandleOne = HandleA;
            Start = Foot;
            End = Head;
            HandleTwo = HandleB;

            DotSprite = Content.Load<Texture2D>("Dot");
            DotSpriteCenter = new Vector2(DotSprite.Width / 2, DotSprite.Height / 2);
        }


        public Vector2 PositionAt(float Percent)
        {
            Vector2 Position = Vector2.CatmullRom(HandleOne, Foot, Head, HandleB, Percent);
            return Position;
        }


        public void DrawPath(SpriteBatch spriteBatch)
        {
            spriteBatch.Draw(DotSprite, HandleOne, null, Color.Red, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);
            spriteBatch.Draw(DotSprite, Start, null, Color.Yellow, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);
            spriteBatch.Draw(DotSprite, End, null, Color.Yellow, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);
            spriteBatch.Draw(DotSprite, HandleTwo, null, Color.Blue, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);

            for (float i = 0.025f; i < 1; i = i + 0.025f)
            {
                spriteBatch.Draw(DotSprite, PositionAt(i), null, Color.White, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);
            }
        }

        public void Draw(SpriteBatch spriteBatch)
        {
            spriteBatch.Draw(DotSprite, HandleOne, null, Color.Red, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);
            spriteBatch.Draw(DotSprite, Start, null, Color.Yellow, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);
            spriteBatch.Draw(DotSprite, End, null, Color.Yellow, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);
            spriteBatch.Draw(DotSprite, HandleTwo, null, Color.Blue, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1);
        }
    }


    public class Game1 : Microsoft.Xna.Framework.Game
    {
        private GraphicsDeviceManager graphics;
        private SpriteBatch spriteBatch;
        //private Texture2D ShipSprite;   //Picture/sprite for the ship. (Contains Alpha transparency.)
        
        //private float ShipOrientation;  //Angle the the ship will face, where 0 degrees will be towards the top of the screen measured in radians (not degrees).
        //private Vector2 ShipSpriteCenter;   //Center of the sprite because we want to orient about the center and not the upper right corner.
        //private Vector2 ShipPosition;   //Ship's position on the screen represented as a vector even though it's not (it's a position, but we may need to do vector math on it later anyway).

        private Spline Path;


        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            graphics.PreferredBackBufferWidth = 1280;    //Screen width horizontal. Change this to fit your screen.
            graphics.PreferredBackBufferHeight = 720;    //Screen width vertical. Change this to fit your screen.
            graphics.IsFullScreen = false;  //Feel free to set this to true once your code works. 

            Content.RootDirectory = "Content";
        }

        protected override void Initialize()
        {
            Path = new Spline(new Vector2(450f, 200f), new Vector2(250f, 300f), new Vector2(850f, 300f), new Vector2(650f, 400f), Content);

            base.Initialize();
        }


        protected override void LoadContent()
        {
            spriteBatch = new SpriteBatch(GraphicsDevice);
            //ShipSprite = Content.Load<Texture2D>("V");
            //ShipPosition = Path.PositionAt(0.01f);
            //ShipSpriteCenter = new Vector2(ShipSprite.Width/2, ShipSprite.Height/2);
        }

        
        protected override void UnloadContent()
        {
        }


        protected override void Update(GameTime gameTime)
        {
            KeyboardState KBState;
            KBState = Keyboard.GetState();
            if (KBState.IsKeyDown(Keys.Escape)) this.Exit();

            if (KBState.IsKeyDown(Keys.W)) Path.HandleA += new Vector2(0f, -0.5f);
            if (KBState.IsKeyDown(Keys.S)) Path.HandleA += new Vector2(0f, 0.5f);
            if (KBState.IsKeyDown(Keys.A)) Path.HandleA += new Vector2(-0.5f, 0f);
            if (KBState.IsKeyDown(Keys.D)) Path.HandleA += new Vector2(0.5f, 0f);

            if (KBState.IsKeyDown(Keys.Up)) Path.HandleB += new Vector2(0f, -0.5f);
            if (KBState.IsKeyDown(Keys.Down)) Path.HandleB += new Vector2(0f, 0.5f);
            if (KBState.IsKeyDown(Keys.Left)) Path.HandleB += new Vector2(-0.5f, 0f);
            if (KBState.IsKeyDown(Keys.Right)) Path.HandleB += new Vector2(0.5f, 0f);


            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
                this.Exit();

            //ShipOrientation += 0.01f;

            base.Update(gameTime);
        }


        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.Black);

            spriteBatch.Begin();
            {
                //spriteBatch.Draw(ShipSprite, ShipPosition, null, Color.White, ShipOrientation, ShipSpriteCenter, 0.15f, SpriteEffects.None, 0);
                Path.DrawPath(spriteBatch);
            }
            spriteBatch.End();

            base.Draw(gameTime);
        }
    }
}



This post has been edited by BBeck: 25 September 2012 - 04:34 PM

Was This Post Helpful? 1
  • +
  • -

#7 BBeck  Icon User is offline

  • Here to help.
  • member icon


Reputation: 580
  • View blog
  • Posts: 1,287
  • Joined: 24-April 12

Re: getting an object to follow a bezier curve

Posted 25 September 2012 - 07:59 PM

So, I modified the above code to use the Hermite curve instead of Catmull-Rom. It's defined differently, but the end result is the same: a very uneven curve depending on how the user defines it. This leads me to believe the best solution that I am likely to come up with is to use the spline to define points on the curve, but to understand that they are not evenly distributed. So they become way points, but with the understanding that they have no standard distance between one another. Then you can just move through them in straight lines. The more points you define on the curve, the more those straight lines will follow the curve. The fewer points you define on the curve, the more the movement will look like straight lines rather than a curve.

If you need to stop at a point that is in between two way points on the curve you can then just use LERP (interpolation) to calculate a point in between.

That would explain why Sean James' solution is basically to do that.

Perhaps LordOfDuct can weigh in on the matter. He is our resident mathematician.
Was This Post Helpful? 0
  • +
  • -

#8 Geogaddy  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 66
  • Joined: 27-March 11

Re: getting an object to follow a bezier curve

Posted 26 September 2012 - 01:20 AM

This link to the app hub forums doesn't specifically deal with bezier, but from a layman's perspective, it looks to be a comprehensive discussion on the matter, at the very least - hopefully it'll be of some use.

I got your code working no bother, by the way (although the endpoint doesn't appear yellow, for some reason).
Was This Post Helpful? 0
  • +
  • -

#9 BBeck  Icon User is offline

  • Here to help.
  • member icon


Reputation: 580
  • View blog
  • Posts: 1,287
  • Joined: 24-April 12

Re: getting an object to follow a bezier curve

Posted 26 September 2012 - 05:48 AM

I'm not sure why the dot sprite would not turn yellow unless it wasn't white in the first place. I take advantage of the fact that it's white to assign it colors. If the sprite has any color in it other than white, it won't color correctly. My sprite was just a white dot on an empty alpha field. I think the picture was 64X64.

I modded my code last night to do Hermite splines. They're different. I don't think they are right for this solution though.

Interesting post. What's really amazing is that they got Shawn Hargreaves to weigh in on it. What's even more amazing is that Shawn was stumped by the problem. Shawn is kind of an XNA legend. I think he was Microsoft's representative for the XNA team to the development community. His blog is really good at explaining extremely complicated XNA stuff that you may have difficulty finding info on elsewhere.

Even more interesting is that I think everyone is trying to over complicate the problem. Although, I think Byron Nelson was on to the solution I would take.

I went through Sean James's chapter on this in his book. The approach he takes is to define a series of path control points to allow you to lay out the track. Those are 100% user defined positions. Then he uses Catmull-Rom to add additional path points. Of course, they are not at all evenly distributed because of the way Catmull-Rom works. But that's irrelevant (which is the point I think everyone is missing - and I missed too for the first half a day of looking at the problem or so).

They are waypoints. The distance between waypoints should not affect the speed that you travel between them. If you have two waypoints 10 meters apart and two waypoints 20 meters apart your velocity should still be 1 meter per second.

So what I would do is travel in a straight line between waypoints. It may require some knowledge of the continuum of space and the concept of precision to be comfortable with this. But, often times you have to accept a certain level of precision, or rather a certain level of lack of precision. If there are enough waypoints defined, no one on earth will be able to tell that the waypoints are discrete, or that you are traveling in a straight line, or that you are pointing towards the next waypoint rather than aligning with the curve.

So, you just have to decide how many waypoints along the spline to define to get the level of precision that you want.

Once you get all the waypoints defined, you just move between them in straight lines. So, let's say you want to move at 2 meters per second constant velocity. You have your current position on the first waypoint. You calculate that the distance to the next waypoint is 0.5 meters. So, you subtract that and need to move 1.5 meters. The next waypoint is 0.8 meters distance from the previous. So, you subtract that and need to move 0.7 meters. The next waypoint is 3 meters from the previous point. That's greater than 0.7 meters that you have left to move in the one second frame. So, the distance is 3 meters, but you only move the remainder distance of 0.7 between the last two waypoints.

Notice that your final position is actually in between waypoints here.

You place the vehicle at that new calculated position. Then you turn it to face the next waypoint, if you want to make it look like it's always facing down the track. It's not. It's not facing along the spline at all; it's facing towards the next waypoint. You will be able to see this clearly if you have far too few waypoints defined. But with a respectable number of waypoints defined, noone is likely to notice. In other-words, if the distance between waypoints is only 10 pixels, and the vehicle is placed on a straight line between them. When it's facing the next waypoint, you're not likely to notice that it's not staying aligned with the spline.

Anyway, I may try and do an example program of it today. I've got it figured out theoretically but it would be good to test it.

It was also ingenious Ngn thought about putting time itself through Catmull-Rom if it actually works. I might test that as well. It might give more accurate results and might further simplify things, although my solution above is pretty simple and straight forward.

This post has been edited by BBeck: 26 September 2012 - 06:04 AM

Was This Post Helpful? 0
  • +
  • -

#10 Geogaddy  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 66
  • Joined: 27-March 11

Re: getting an object to follow a bezier curve

Posted 26 September 2012 - 09:35 AM

A waypoint system is fairly straightforward; Kurt Jaeger's XNA 4.0 book uses a waypoint system for enemies in a vertically "scrolling" shooter. I get that by using enough of them you could probably affect a smooth, curved path, but it's not the sort of thing I'd want to be doing without some sort of spline editor.
Was This Post Helpful? 0
  • +
  • -

#11 BBeck  Icon User is offline

  • Here to help.
  • member icon


Reputation: 580
  • View blog
  • Posts: 1,287
  • Joined: 24-April 12

Re: getting an object to follow a bezier curve

Posted 26 September 2012 - 03:08 PM

Well, I'm inclined to see if they'll let me publish this here in the forum as a tutorial.

It's working. Here's the code. Unfortunately, there's no good way to include the sprite for the dots or the sprite for the ship. You could make your own and include them in the project's contents with the same names. I made both of them in Paint.Net as simple shapes with an alpha transparent background.

Dot is just a white dot. 64X64

V is the ship icon, which I made a black triangle with a yellow outline. 256X256

Here's the code:

Game1.cs
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using PathNamespace;


namespace PathFinder
{
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        private GraphicsDeviceManager graphics;
        private SpriteBatch BatchOSprites;
        private Texture2D ShipSprite;   //Picture/sprite for the ship. (Contains Alpha transparency.) 256x256
        private Vector2 ShipOrientation;  //Angle the the ship will face, where 0 degrees will be towards the top of the screen measured in radians (not degrees).
        private Vector2 ShipSpriteCenter;   //Center of the sprite because we want to orient about the center and not the upper right corner.
        private Vector2 ShipPosition;   //Ship's position on the screen represented as a vector even though it's not (it's a position, but we may need to do vector math on it later anyway).
        private float ShipVelocity;     //Speed of the ship in pixels per frame.
        private List<Vector2> PathControlPoints;    //Define this to define the path of the track.
        private Path Track;
        private bool ShipMovingForward; //True=forward, False=back.
        private int NextTrackPoint; //Next waypoint the ship will move to.

        private const float MillisecondsPerSecond = 1000f;  //Float to keep from having to constantly convert for the final value.


        //=======================================================================================================================
        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            graphics.PreferredBackBufferWidth = 1280;    //Screen width horizontal. Change this to fit your screen.
            graphics.PreferredBackBufferHeight = 720;    //Screen width vertical. Change this to fit your screen.
            graphics.IsFullScreen = false;  //Feel free to set this to true once your code works. 

            Content.RootDirectory = "Content";
        }
        //=======================================================================================================================


        protected override void Initialize()
        //=======================================================================================================================
        //  Initialize()
        //  Parameters: None
        //  Returns: None
        //
        //  Purpose: Initial setup of anything that is not game content.
        //
        //  Explanation:
        //      Setup the "track", or path, that the ship will follow. This is done by defining "control points". Each point
        //  will be a point on the track. All points between these points will be automatically interpolated and generated. Each
        //  control point is a postion represented as a Vector2 even though the positions are not vectors. 
        //
        //      The PathControlPoints is a list of the control points that you can add or remove points from.
        //
        //      The Track is an object that manages the entire track, or path, that the ship will follow.
        //  
        //      The NextTrackPoint is the number of Track points to count forward from 0 to determine which track point the ship
        //  is headed to next. This is generated points and not control points!
        //
        //=======================================================================================================================
        {
            PathControlPoints = new List<Vector2>();
            PathControlPoints.Add(new Vector2(100f, 400f));
            PathControlPoints.Add(new Vector2(600f, 100f));
            PathControlPoints.Add(new Vector2(1100f, 400f));

            PathControlPoints.Add(new Vector2(550f, 420f));
            PathControlPoints.Add(new Vector2(650f, 380f));

            PathControlPoints.Add(new Vector2(600f, 700f));
            Track = new Path(PathControlPoints, Content);
            NextTrackPoint = 0;

            base.Initialize();  //Code generated by Visual Studio and may not be necessary since we don't use components.
        }


        protected override void LoadContent()
        //=======================================================================================================================
        //  LoadContent()
        //  Parameters: None
        //  Returns: None
        //
        //  Purpose: Initial setup of game content (artwork).
        //
        //  Explanation:
        //      The standard spriteBatch has been renamed. Since there is no seperate class for a ship in this program, the ship
        //  sprite is loaded here and it's values are initialized.
        //
        //=======================================================================================================================
        {
            BatchOSprites = new SpriteBatch(GraphicsDevice);
            ShipSprite = Content.Load<Texture2D>("V");  //Load the sprite representing the ship.
            ShipPosition = Track.StartingSpot();    //Start the ship on the very first node(point) of the track.
            ShipSpriteCenter = new Vector2(ShipSprite.Width / 2, ShipSprite.Height / 2);
            ShipOrientation = -Vector2.UnitY;   //Vector pointing towards top of the screen.
            ShipVelocity = 80f; //Ship's velocity in pixels per second.
            ShipMovingForward = true;
        }
        //=======================================================================================================================


        protected override void UnloadContent()
        //=======================================================================================================================
        //  UnloadContent()
        //  Parameters: None
        //  Returns: None
        //
        //  Purpose: Destruction of game content.
        //
        //  Explanation:
        //       I've never seen anyone use this method. Although, I suspect they put it in here for a reason, and we just haven't
        //  figured out exactly what that reason is.
        //
        //=======================================================================================================================
        {
        }
        //=======================================================================================================================


        protected override void Update(GameTime gameTime)
        //=======================================================================================================================
        //  Update()
        //  Parameters: gameTime - object that tracks time elapsed since the previous frame.
        //  Returns: None
        //
        //  Purpose: Change things every frame.
        //
        //  Explanation:
        //       In order to keep movement even, I'm using time elapsed since the previous Update measured in milliseconds. I
        //  am then converting it into seconds by multiplying the milliseconds value times 1,000 milliseconds per second. Number
        //  of seconds elapsed will be fractional, since it's actually milliseconds. The ship's velocity in pixels per second is
        //  multiplied times the number of seconds (milliseconds) since the previous time the Update ran giving Velocity per frame.
        //
        //      The path(track)'s MoveToPosition is called to move the ship from it's previous location to the new location for this
        //  frame. ShipPosition, NextTrackPoint, and ShipOrientation are all passed by reference so that the call actually modifies
        //  their values. This allows the call to update the Ship's position and heading.
        //
        //=======================================================================================================================
        {
            KeyboardState KBState;
            float MillisecondsSinceLastFrame = 0f;
            float SecondsSinceLastFrame = 0f;
            float ShipsDistanceSincePreviousFrame = 0f;


            KBState = Keyboard.GetState();
            if (KBState.IsKeyDown(Keys.Escape)) this.Exit();

            if (KBState.IsKeyDown(Keys.Up)) ShipMovingForward = true;
            if (KBState.IsKeyDown(Keys.Down)) ShipMovingForward = false;

            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
                this.Exit();

            MillisecondsSinceLastFrame = (float)gameTime.ElapsedGameTime.Milliseconds;
            SecondsSinceLastFrame = (float)MillisecondsSinceLastFrame / MillisecondsPerSecond;
            ShipsDistanceSincePreviousFrame = ShipVelocity * SecondsSinceLastFrame;
            
            Track.MoveToPositionOnPath(ref ShipPosition, ref NextTrackPoint, ref ShipOrientation, ShipsDistanceSincePreviousFrame, ShipMovingForward);

            base.Update(gameTime);
        }
        //=======================================================================================================================


        private float VectorsAngle(Vector2 InputVector)
        //=======================================================================================================================
        //  VectorsAngle
        //  Parameters: InputVector - Any 2D vector to convert to an angle.
        //  Returns: AngleInRadians - Angle that the vector faces.
        //
        //  Purpose: Returns an angle that represents the compass heading of the 2D vector in radians.
        //
        //  Explanation:
        //       0 radians faces towards the top of the screen. Pi radians faces down. Pi/2 faces right. Convert to degrees if it
        //  makes you feel better.
        //
        //=======================================================================================================================
        {
            float AngleInRadians;

            AngleInRadians = (float)Math.Atan2(InputVector.Y, InputVector.X);   //Convert 2D vector's direction to an angle.
            AngleInRadians += MathHelper.PiOver2;   //Add 90 degrees to make 0 degrees pointing to top of the screen.
            return AngleInRadians;
        }
        //=======================================================================================================================


        protected override void Draw(GameTime gameTime)
        //=======================================================================================================================
        //  Draw()
        //  Parameters: gameTime - Time elapsed since the last call to Draw().
        //  Returns: None.
        //
        //  Purpose: Draw everything that shows up on the screen or otherwise gets drawn.
        //
        //  Explanation:
        //       Clears the screen in black and then draws all the sprites for the track and the ship. You can comment out the lines
        //  for the track to turn them invisible or uncomment to make them visible. The sprites have alpha backgrounds and so 
        //  BlendState.AlphaBlend has to be specified. They are purposely drawn in backwards order to show that their draw layer is
        //  what's drawing them in the correct order.
        //
        //=======================================================================================================================
        {
            float ShipSpriteOrientation = 0f;

            GraphicsDevice.Clear(Color.Black);

            ShipSpriteOrientation = VectorsAngle(ShipOrientation);
            BatchOSprites.Begin(SpriteSortMode.BackToFront, BlendState.AlphaBlend);
            {
                BatchOSprites.Draw(ShipSprite, ShipPosition, null, Color.White, ShipSpriteOrientation, ShipSpriteCenter, 0.15f, SpriteEffects.None, 0f);
                Track.DrawControlPoints(BatchOSprites);
                //Track.DrawPath(BatchOSprites);
            }
            BatchOSprites.End();

            base.Draw(gameTime);
        }
        //=======================================================================================================================
    }
}





Path.cs
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;


namespace PathNamespace
{
    public class Path
    {
        private Texture2D DotSprite;    //Picture/sprite of a white dot. 64X64
        private Vector2 DotSpriteCenter;    //Center of the sprite.
        private List<Vector2> ControlPoints;    //User defined.
        private List<Vector2> PathPoints;   //Generated points between user defined points.
        private const int SplinePoints = 34; //Resolution of the spline.


        public Path(List<Vector2> PathControlPoints, ContentManager Content)
        //=======================================================================================================================
        //  Constructor()
        //  Parameters: 
        //      PathControlPoints - a list of screen points that define the path.
        //      Content - The external content manager is needed to load the sprite texture for the path dots.
        //
        //  Returns: None.
        //
        //  Purpose: Initialize the object according to programmer defined control points.
        //
        //  Explanation:
        //       The programmer that initializes this object has to create a list of 2D Vector screen positions which define the 
        //  path. The path will follow the order of these positions in the order they are defined from first to last. This allows 
        //  the programmer to create loops and other shapes as well as layout the entire shape of the path. More control points
        //  will more accurately define the path.
        //
        //      The DefinePath method is called, after the white dot sprite is loaded, for the computer to generate a certain number 
        //  of path points between the control points. The number of path points between control points is set by SplinePoints. The
        //  more control points the better the definition of the track, but the slower everything will run. Likewise, the more 
        //  SplinePoints between control points the more accurate, but the slower everything will run.
        //
        //      The path points generated between control points use Catmull-Rom interpolation to smooth out the curve, rather then
        //  turning at exceedingly sharp angles in the turns.
        //
        //=======================================================================================================================
        {
            ControlPoints = PathControlPoints;
            DotSprite = Content.Load<Texture2D>("Dot");
            DotSpriteCenter = new Vector2(DotSprite.Width / 2, DotSprite.Height / 2);
            DefinePath();
        }
        //=======================================================================================================================


        public Vector2 StartingSpot()
        //=======================================================================================================================
        //  StartingSpot()
        //  Parameters: None.
        //  Returns: Vector2 - Screen position of the first Control Point defined.
        //
        //  Purpose: Returns a vector position of the place where the path/track begins.
        //
        //  Explanation:
        //       
        //
        //=======================================================================================================================
        {
            return ControlPoints[0];
        }
        //=======================================================================================================================


        public void DrawControlPoints(SpriteBatch Batch)
        //=======================================================================================================================
        //  DrawControlPoints()
        //  Parameters: Batch - SpriteBatch being used for this draw batch. Passed so that one batch can be used for all.
        //  Returns: None.
        //
        //  Purpose: Draws all the user defined control points that control the layout of the path/track.
        //
        //  Explanation:
        //       Draws all the user defined control points that control the layout of the path/track in yellow to make them
        //  easily visible even when the interpolated intermediate path points are drawn. The dot sprite was created white and
        //  will take on any color given because it's white.
        //
        //      This does NOT draw the points in between the control points, which represent the actual path.
        //
        //=======================================================================================================================
        {
            foreach (Vector2 ControlPoint in ControlPoints)
            {
                Batch.Draw(DotSprite, ControlPoint, null, Color.Yellow, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 0.9f);
            }
        }
        //=======================================================================================================================


        public void DrawPath(SpriteBatch Batch)
        //=======================================================================================================================
        //  DrawPath()
        //  Parameters: Batch - SpriteBatch being used for this draw batch. Passed so that one batch can be used for all.
        //  Returns: None.
        //
        //  Purpose: Draws all of the waypoints for the defined path including those computer generated.
        //
        //  Explanation:
        //       The sprite is white and will take on the green color given because it is white.
        //
        //=======================================================================================================================
        {
            foreach (Vector2 PathPoint in PathPoints)
            {
                Batch.Draw(DotSprite, PathPoint, null, Color.Green, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1f);
            }
        }
        //=======================================================================================================================


        public void MoveToPositionOnPath(ref Vector2 Position, ref int NextPathPoint, ref Vector2 Orientation, float Distance, bool Forward)
        //=======================================================================================================================
        //  MoveToPositionOnPath()
        //  Parameters: 
        //      Position - Screen position of the object represented as a 2D vector. Altered by this method.
        //      NextPathPoint - Points to the waypoint on the path that the object will be moving towards. Altered by this method. 
        //      Orientation - Normalized (we hope) vector that points in the direction the ship faces. Altered by this method.
        //      Distance - Distance the object will move this frame regardless of distance between waypoints.
        //      Forward - True if motion is clockwise, and false for counter-clockwise.
        //
        //  Returns: None.
        //
        //  Purpose: Moves the object defined by the Position towards the next waypoint that can be reached, by traveling through
        //      all intermediary waypoints, by the given distance.
        //
        //  Explanation:
        //       The object's current position is passed in. The method starts by looking at the waypoint specified by NextPathPoint.
        //  NextPathPoint is maintained by the external program. It starts out set to the first waypoint, and then this method
        //  updates the external value to let the external program know what the correct next waypoint will be. It should be noted
        //  that the next waypoint is not simply incremented, but that many waypoints may be passed in determining the next waypoint.
        //
        //      The method updates the position to move towards the next waypoint, and if the next waypoint can be reached without
        //  exceeding the specified distance, it will go on and do the same for the waypoint after that, and so on and so forth. Once
        //  it reaches a point inbetween waypoints where the distance runs out, it will set the final position of the object to that
        //  spot. It will output the number of the next waypoint (NextPathPoint). Then it will calculate a direction vector to point to 
        //  the direction to that next waypoint. 
        //
        //      The object following the path could be anything. This method just treats the object according to it's position, orientation,
        //  and it's next waypoint. The next waypoint is calculated here and sent to the external program to be maintained and then
        //  it will be passed in again the next time, updated, and returned again.
        //
        //=======================================================================================================================
        {
            if (Distance > 0f)  //Don't try and move the object if the distance to be moved is zero. It will destroy the vectors, if you do.
            {
                Vector2 PathToNextWaypoint;     //Used to track direction to and distance of the next waypoint.
                float DistanceToNextWayPoint = 0f;  //Info contained in PathToNextWaypoint but made redundant for clarity.
                int NumberOfPathPoints = PathPoints.Count();


                PathToNextWaypoint = PathPoints[NextPathPoint] - Position; //Vector subtraction gives a new vector of distance & direction to waypoint.
                DistanceToNextWayPoint = PathToNextWaypoint.Length();   //Length is the distance between next path point and current position.
                while (Distance > DistanceToNextWayPoint)   //Loop until distance left to travel is less than distance to next point.
                {
                    Distance -= DistanceToNextWayPoint;         //Subtract the distance to next waypoint before moving there.
                    Position = PathPoints[NextPathPoint];     //Move to the next path point.
                    if (Forward == true)
                    {
                        //Move clockwise.
                        NextPathPoint++;
                        if (NextPathPoint >= PathPoints.Count()) NextPathPoint = 0; //Wrap around to the beginning if you go off the end.
                    }
                    else
                    {
                        //Move counter-clockwise.
                        NextPathPoint--;
                        if (NextPathPoint < 0) NextPathPoint = PathPoints.Count() - 1; //Wrap around to the beginning if you go off the end.
                    }
                    PathToNextWaypoint = PathPoints[NextPathPoint] - Position;  //Vector subtraction gives a new vector of distance & direction to waypoint.
                    DistanceToNextWayPoint = PathToNextWaypoint.Length();   //Length is the distance between next path point and current position.
                }

                //Distance is now smaller than distance between waypoints here.
                PathToNextWaypoint.Normalize(); //Normalize vector to remove distance information and prepare for scalar multiplication to reset distance/length.
                Position += PathToNextWaypoint * Distance; //Vector to scalar multiplication changes length of vector PathToNextWaypoint to Distance. Addition changes position by amount & direction of PathToNextWaypoint.
                //PathToNextWaypoint.Normalize(); //Normalize again because we want to use this for the Orientation normal which stores only the ship's heading.
                Orientation = PathToNextWaypoint;
            }
        }
        //=======================================================================================================================


        private void DefinePath()
        //=======================================================================================================================
        //  DefinePath()
        //  Parameters: None.
        //  Returns: None.
        //
        //  Purpose: Generates a path, or track, that an object can follow.
        //
        //  Explanation:
        //       When the Path is initialized before this, the control points are defined. The control points allow the programmer
        //  to layout the track by specifiying points along the track. Each control point will be a path on the track. They go in
        //  the order they were defined. Path points are generated between control points at that point.
        //
        //      This method uses Catmull-Rom to define smooth curves between control points. It looks at the waypoint that came
        //  before for the first handle. And it looks at the waypoint two ahead to determine the position of the second handle. 
        //  Then using those handles it shapes the curve between the two center waypoints into a smooth curve that turns to face
        //  the previous waypoint and the waypoint after the spline.
        //
        //=======================================================================================================================
        {
            int NumberOfControlPoints = ControlPoints.Count;

            PathPoints = new List<Vector2>();
            for (int ControlPoint = 0; ControlPoint < NumberOfControlPoints; ControlPoint++)
            {
                PathPoints.Add(ControlPoints[ControlPoint]);    //Add the control point to the list of Path Points that define the path.

                //Don't reprocess the ControlPoints(ends of the spline).
                for (int SplinePoint = 1; SplinePoint < SplinePoints; SplinePoint++)
                {
                    float Percent = (float)SplinePoint / (float)SplinePoints;
                    Vector2 PreviousControlPoint = ControlPoints[WrapPoint(ControlPoint - 1, NumberOfControlPoints - 1)];
                    Vector2 CurrentControlPoint = ControlPoints[ControlPoint];
                    Vector2 NextControlPoint = ControlPoints[WrapPoint(ControlPoint + 1, NumberOfControlPoints - 1)];
                    Vector2 NextNextControlPoint = ControlPoints[WrapPoint(ControlPoint + 2, NumberOfControlPoints - 1)];
                    Vector2 Position = Vector2.CatmullRom(PreviousControlPoint, CurrentControlPoint, NextControlPoint, NextNextControlPoint, Percent);
                    PathPoints.Add(Position);
                }
            }
        }
        //=======================================================================================================================


        private int WrapPoint(int Point, int MaxPoint)
        //=======================================================================================================================
        //  WrapPoint()
        //  Parameters: 
        //      Point - the control point number.
        //      MaxPoint - the last control point number in the list of control points.
        //  Returns: int - the control point number wrapped if it falls off the ends.
        //
        //  Purpose: Changes the control point number if it is out of range.
        //
        //  Explanation:
        //       The control points can all be numbered zero through the number of control points minus one. When doing that
        //  it's easy to specify a control point number that's outside of the range of valid control point numbers. This method
        //  verifies that the control point number given is in the valid range. And if it's not, it updates it to wrap it around
        //  the other side by the amount that it would have gone out of range. This allows the ends of the path to meet each other
        //  and become a closed circuit.
        //
        //=======================================================================================================================
        {
            if (Point > MaxPoint)
            {
                Point -= MaxPoint + 1;  //Point is already across "the line" and we subtract 1 from the top to bring it back in.
            }
            else
            {
                if (Point < 0) Point += MaxPoint + 1;    //Point is already across "the line" and we subtract 1 from the top to bring it back in.
            }
            return Point;
        }
        //=======================================================================================================================
    }

}



This post has been edited by BBeck: 26 September 2012 - 03:36 PM

Was This Post Helpful? 1
  • +
  • -

#12 Geogaddy  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 66
  • Joined: 27-March 11

Re: getting an object to follow a bezier curve

Posted 27 September 2012 - 03:53 AM

This is excellent, and very well annotated. I'm still playing around with it so I might have more to say once I fully understand what's going on, but yeah - great stuff.

Oh, and this definitely SHOULD be a tutorial. Far too little out there on the net concerning this subject.
Was This Post Helpful? 0
  • +
  • -

#13 BBeck  Icon User is offline

  • Here to help.
  • member icon


Reputation: 580
  • View blog
  • Posts: 1,287
  • Joined: 24-April 12

Re: getting an object to follow a bezier curve

Posted 27 September 2012 - 04:29 AM

Thanks! I try to annotate my code really well for teaching. I went ahead and annotated it like that partially to make it clear, but mostly in anticipation that I might make it into a tutorial.

The idea of putting time through the Catmull-Rom curve still really intrigues me. I may try and give that a try. Doing it like I did here works pretty well, but there's a whole lot of calculating involved in determining the position every frame. I'm thinking there's got to be a better way. So, I may try and see if I can come up with an improvement on it if I get some time.
Was This Post Helpful? 0
  • +
  • -

#14 BBeck  Icon User is offline

  • Here to help.
  • member icon


Reputation: 580
  • View blog
  • Posts: 1,287
  • Joined: 24-April 12

Re: getting an object to follow a bezier curve

Posted 27 September 2012 - 10:10 AM

You know, I really thought I was going to be able to further optimize this. The MoveToPositionOnPath method is extremely "expensive", largely because it iterates between every waypoint between control points.

I looked a bit closer at the claim that you could put time through Catmull-Rom. After reviewing it, I think he was just wrong. The output of his equation is a 2D vector, yet he's using the X component and totally throwing away the y component. I suspect this might work if the spline is mostly horizontal, but not well at all when vertical because of the missing Y information. Also, he seems to be the only one on the internet who makes the claim that it will work. I think it probably just works under very specific circumstances.

Everyone I've found on the internet who seems to really be an expert on this topic seems to say the only way to truely solve it is with either differential or integral calculus. And apparently, the equation is not pretty and probably fairly processor intense. That makes sense since the calculus answer (I think) is basically going to do basically what my code does, which is divide the curve up into a certain number of subsegments and calculate a straight line value between them.

I freely admit that I barely even know what calculus is, but I think my solution is "essentially" roughly the same solution as using differential calculus (or is it integral... I think it's differential because I'm drawing lines between every segment on the curve and adding up the values of those lines).

So, it seems to me that even using calculus is likely to result in computations that are about equally as expensive and do basically the same thing.

When I wrote the code, I put DistanceToNextWayPoint into it's own variable even though it's the exact same things as PathToNextWayPoint.Length(). That might have been a savings, but the value gets used twice, which saves it from having to be recalculated (I'm not sure but I think the .Length() method calculates the answer instead of just storing the answer).

I also considered not using vectors to save processing time, but I think not using vectors would likely be just as expensive as using vectors and the vectors are more straight forward.

In short, by playing around with it quite a bit you "might" be able to optimize it a tiny bit. But I think it's about as good as it's going to get.
Was This Post Helpful? 1
  • +
  • -

#15 Tryk  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 27-May 13

Re: getting an object to follow a bezier curve

Posted 27 May 2013 - 05:34 AM

View PostBBeck, on 26 September 2012 - 03:08 PM, said:

Well, I'm inclined to see if they'll let me publish this here in the forum as a tutorial.

It's working. Here's the code. Unfortunately, there's no good way to include the sprite for the dots or the sprite for the ship. You could make your own and include them in the project's contents with the same names. I made both of them in Paint.Net as simple shapes with an alpha transparent background.

Dot is just a white dot. 64X64

V is the ship icon, which I made a black triangle with a yellow outline. 256X256

Here's the code:

Game1.cs
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;
using PathNamespace;


namespace PathFinder
{
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        private GraphicsDeviceManager graphics;
        private SpriteBatch BatchOSprites;
        private Texture2D ShipSprite;   //Picture/sprite for the ship. (Contains Alpha transparency.) 256x256
        private Vector2 ShipOrientation;  //Angle the the ship will face, where 0 degrees will be towards the top of the screen measured in radians (not degrees).
        private Vector2 ShipSpriteCenter;   //Center of the sprite because we want to orient about the center and not the upper right corner.
        private Vector2 ShipPosition;   //Ship's position on the screen represented as a vector even though it's not (it's a position, but we may need to do vector math on it later anyway).
        private float ShipVelocity;     //Speed of the ship in pixels per frame.
        private List<Vector2> PathControlPoints;    //Define this to define the path of the track.
        private Path Track;
        private bool ShipMovingForward; //True=forward, False=back.
        private int NextTrackPoint; //Next waypoint the ship will move to.

        private const float MillisecondsPerSecond = 1000f;  //Float to keep from having to constantly convert for the final value.


        //=======================================================================================================================
        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            graphics.PreferredBackBufferWidth = 1280;    //Screen width horizontal. Change this to fit your screen.
            graphics.PreferredBackBufferHeight = 720;    //Screen width vertical. Change this to fit your screen.
            graphics.IsFullScreen = false;  //Feel free to set this to true once your code works. 

            Content.RootDirectory = "Content";
        }
        //=======================================================================================================================


        protected override void Initialize()
        //=======================================================================================================================
        //  Initialize()
        //  Parameters: None
        //  Returns: None
        //
        //  Purpose: Initial setup of anything that is not game content.
        //
        //  Explanation:
        //      Setup the "track", or path, that the ship will follow. This is done by defining "control points". Each point
        //  will be a point on the track. All points between these points will be automatically interpolated and generated. Each
        //  control point is a postion represented as a Vector2 even though the positions are not vectors. 
        //
        //      The PathControlPoints is a list of the control points that you can add or remove points from.
        //
        //      The Track is an object that manages the entire track, or path, that the ship will follow.
        //  
        //      The NextTrackPoint is the number of Track points to count forward from 0 to determine which track point the ship
        //  is headed to next. This is generated points and not control points!
        //
        //=======================================================================================================================
        {
            PathControlPoints = new List<Vector2>();
            PathControlPoints.Add(new Vector2(100f, 400f));
            PathControlPoints.Add(new Vector2(600f, 100f));
            PathControlPoints.Add(new Vector2(1100f, 400f));

            PathControlPoints.Add(new Vector2(550f, 420f));
            PathControlPoints.Add(new Vector2(650f, 380f));

            PathControlPoints.Add(new Vector2(600f, 700f));
            Track = new Path(PathControlPoints, Content);
            NextTrackPoint = 0;

            base.Initialize();  //Code generated by Visual Studio and may not be necessary since we don't use components.
        }


        protected override void LoadContent()
        //=======================================================================================================================
        //  LoadContent()
        //  Parameters: None
        //  Returns: None
        //
        //  Purpose: Initial setup of game content (artwork).
        //
        //  Explanation:
        //      The standard spriteBatch has been renamed. Since there is no seperate class for a ship in this program, the ship
        //  sprite is loaded here and it's values are initialized.
        //
        //=======================================================================================================================
        {
            BatchOSprites = new SpriteBatch(GraphicsDevice);
            ShipSprite = Content.Load<Texture2D>("V");  //Load the sprite representing the ship.
            ShipPosition = Track.StartingSpot();    //Start the ship on the very first node(point) of the track.
            ShipSpriteCenter = new Vector2(ShipSprite.Width / 2, ShipSprite.Height / 2);
            ShipOrientation = -Vector2.UnitY;   //Vector pointing towards top of the screen.
            ShipVelocity = 80f; //Ship's velocity in pixels per second.
            ShipMovingForward = true;
        }
        //=======================================================================================================================


        protected override void UnloadContent()
        //=======================================================================================================================
        //  UnloadContent()
        //  Parameters: None
        //  Returns: None
        //
        //  Purpose: Destruction of game content.
        //
        //  Explanation:
        //       I've never seen anyone use this method. Although, I suspect they put it in here for a reason, and we just haven't
        //  figured out exactly what that reason is.
        //
        //=======================================================================================================================
        {
        }
        //=======================================================================================================================


        protected override void Update(GameTime gameTime)
        //=======================================================================================================================
        //  Update()
        //  Parameters: gameTime - object that tracks time elapsed since the previous frame.
        //  Returns: None
        //
        //  Purpose: Change things every frame.
        //
        //  Explanation:
        //       In order to keep movement even, I'm using time elapsed since the previous Update measured in milliseconds. I
        //  am then converting it into seconds by multiplying the milliseconds value times 1,000 milliseconds per second. Number
        //  of seconds elapsed will be fractional, since it's actually milliseconds. The ship's velocity in pixels per second is
        //  multiplied times the number of seconds (milliseconds) since the previous time the Update ran giving Velocity per frame.
        //
        //      The path(track)'s MoveToPosition is called to move the ship from it's previous location to the new location for this
        //  frame. ShipPosition, NextTrackPoint, and ShipOrientation are all passed by reference so that the call actually modifies
        //  their values. This allows the call to update the Ship's position and heading.
        //
        //=======================================================================================================================
        {
            KeyboardState KBState;
            float MillisecondsSinceLastFrame = 0f;
            float SecondsSinceLastFrame = 0f;
            float ShipsDistanceSincePreviousFrame = 0f;


            KBState = Keyboard.GetState();
            if (KBState.IsKeyDown(Keys.Escape)) this.Exit();

            if (KBState.IsKeyDown(Keys.Up)) ShipMovingForward = true;
            if (KBState.IsKeyDown(Keys.Down)) ShipMovingForward = false;

            if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
                this.Exit();

            MillisecondsSinceLastFrame = (float)gameTime.ElapsedGameTime.Milliseconds;
            SecondsSinceLastFrame = (float)MillisecondsSinceLastFrame / MillisecondsPerSecond;
            ShipsDistanceSincePreviousFrame = ShipVelocity * SecondsSinceLastFrame;
            
            Track.MoveToPositionOnPath(ref ShipPosition, ref NextTrackPoint, ref ShipOrientation, ShipsDistanceSincePreviousFrame, ShipMovingForward);

            base.Update(gameTime);
        }
        //=======================================================================================================================


        private float VectorsAngle(Vector2 InputVector)
        //=======================================================================================================================
        //  VectorsAngle
        //  Parameters: InputVector - Any 2D vector to convert to an angle.
        //  Returns: AngleInRadians - Angle that the vector faces.
        //
        //  Purpose: Returns an angle that represents the compass heading of the 2D vector in radians.
        //
        //  Explanation:
        //       0 radians faces towards the top of the screen. Pi radians faces down. Pi/2 faces right. Convert to degrees if it
        //  makes you feel better.
        //
        //=======================================================================================================================
        {
            float AngleInRadians;

            AngleInRadians = (float)Math.Atan2(InputVector.Y, InputVector.X);   //Convert 2D vector's direction to an angle.
            AngleInRadians += MathHelper.PiOver2;   //Add 90 degrees to make 0 degrees pointing to top of the screen.
            return AngleInRadians;
        }
        //=======================================================================================================================


        protected override void Draw(GameTime gameTime)
        //=======================================================================================================================
        //  Draw()
        //  Parameters: gameTime - Time elapsed since the last call to Draw().
        //  Returns: None.
        //
        //  Purpose: Draw everything that shows up on the screen or otherwise gets drawn.
        //
        //  Explanation:
        //       Clears the screen in black and then draws all the sprites for the track and the ship. You can comment out the lines
        //  for the track to turn them invisible or uncomment to make them visible. The sprites have alpha backgrounds and so 
        //  BlendState.AlphaBlend has to be specified. They are purposely drawn in backwards order to show that their draw layer is
        //  what's drawing them in the correct order.
        //
        //=======================================================================================================================
        {
            float ShipSpriteOrientation = 0f;

            GraphicsDevice.Clear(Color.Black);

            ShipSpriteOrientation = VectorsAngle(ShipOrientation);
            BatchOSprites.Begin(SpriteSortMode.BackToFront, BlendState.AlphaBlend);
            {
                BatchOSprites.Draw(ShipSprite, ShipPosition, null, Color.White, ShipSpriteOrientation, ShipSpriteCenter, 0.15f, SpriteEffects.None, 0f);
                Track.DrawControlPoints(BatchOSprites);
                //Track.DrawPath(BatchOSprites);
            }
            BatchOSprites.End();

            base.Draw(gameTime);
        }
        //=======================================================================================================================
    }
}





Path.cs
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;


namespace PathNamespace
{
    public class Path
    {
        private Texture2D DotSprite;    //Picture/sprite of a white dot. 64X64
        private Vector2 DotSpriteCenter;    //Center of the sprite.
        private List<Vector2> ControlPoints;    //User defined.
        private List<Vector2> PathPoints;   //Generated points between user defined points.
        private const int SplinePoints = 34; //Resolution of the spline.


        public Path(List<Vector2> PathControlPoints, ContentManager Content)
        //=======================================================================================================================
        //  Constructor()
        //  Parameters: 
        //      PathControlPoints - a list of screen points that define the path.
        //      Content - The external content manager is needed to load the sprite texture for the path dots.
        //
        //  Returns: None.
        //
        //  Purpose: Initialize the object according to programmer defined control points.
        //
        //  Explanation:
        //       The programmer that initializes this object has to create a list of 2D Vector screen positions which define the 
        //  path. The path will follow the order of these positions in the order they are defined from first to last. This allows 
        //  the programmer to create loops and other shapes as well as layout the entire shape of the path. More control points
        //  will more accurately define the path.
        //
        //      The DefinePath method is called, after the white dot sprite is loaded, for the computer to generate a certain number 
        //  of path points between the control points. The number of path points between control points is set by SplinePoints. The
        //  more control points the better the definition of the track, but the slower everything will run. Likewise, the more 
        //  SplinePoints between control points the more accurate, but the slower everything will run.
        //
        //      The path points generated between control points use Catmull-Rom interpolation to smooth out the curve, rather then
        //  turning at exceedingly sharp angles in the turns.
        //
        //=======================================================================================================================
        {
            ControlPoints = PathControlPoints;
            DotSprite = Content.Load<Texture2D>("Dot");
            DotSpriteCenter = new Vector2(DotSprite.Width / 2, DotSprite.Height / 2);
            DefinePath();
        }
        //=======================================================================================================================


        public Vector2 StartingSpot()
        //=======================================================================================================================
        //  StartingSpot()
        //  Parameters: None.
        //  Returns: Vector2 - Screen position of the first Control Point defined.
        //
        //  Purpose: Returns a vector position of the place where the path/track begins.
        //
        //  Explanation:
        //       
        //
        //=======================================================================================================================
        {
            return ControlPoints[0];
        }
        //=======================================================================================================================


        public void DrawControlPoints(SpriteBatch Batch)
        //=======================================================================================================================
        //  DrawControlPoints()
        //  Parameters: Batch - SpriteBatch being used for this draw batch. Passed so that one batch can be used for all.
        //  Returns: None.
        //
        //  Purpose: Draws all the user defined control points that control the layout of the path/track.
        //
        //  Explanation:
        //       Draws all the user defined control points that control the layout of the path/track in yellow to make them
        //  easily visible even when the interpolated intermediate path points are drawn. The dot sprite was created white and
        //  will take on any color given because it's white.
        //
        //      This does NOT draw the points in between the control points, which represent the actual path.
        //
        //=======================================================================================================================
        {
            foreach (Vector2 ControlPoint in ControlPoints)
            {
                Batch.Draw(DotSprite, ControlPoint, null, Color.Yellow, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 0.9f);
            }
        }
        //=======================================================================================================================


        public void DrawPath(SpriteBatch Batch)
        //=======================================================================================================================
        //  DrawPath()
        //  Parameters: Batch - SpriteBatch being used for this draw batch. Passed so that one batch can be used for all.
        //  Returns: None.
        //
        //  Purpose: Draws all of the waypoints for the defined path including those computer generated.
        //
        //  Explanation:
        //       The sprite is white and will take on the green color given because it is white.
        //
        //=======================================================================================================================
        {
            foreach (Vector2 PathPoint in PathPoints)
            {
                Batch.Draw(DotSprite, PathPoint, null, Color.Green, 0f, DotSpriteCenter, 0.1f, SpriteEffects.None, 1f);
            }
        }
        //=======================================================================================================================


        public void MoveToPositionOnPath(ref Vector2 Position, ref int NextPathPoint, ref Vector2 Orientation, float Distance, bool Forward)
        //=======================================================================================================================
        //  MoveToPositionOnPath()
        //  Parameters: 
        //      Position - Screen position of the object represented as a 2D vector. Altered by this method.
        //      NextPathPoint - Points to the waypoint on the path that the object will be moving towards. Altered by this method. 
        //      Orientation - Normalized (we hope) vector that points in the direction the ship faces. Altered by this method.
        //      Distance - Distance the object will move this frame regardless of distance between waypoints.
        //      Forward - True if motion is clockwise, and false for counter-clockwise.
        //
        //  Returns: None.
        //
        //  Purpose: Moves the object defined by the Position towards the next waypoint that can be reached, by traveling through
        //      all intermediary waypoints, by the given distance.
        //
        //  Explanation:
        //       The object's current position is passed in. The method starts by looking at the waypoint specified by NextPathPoint.
        //  NextPathPoint is maintained by the external program. It starts out set to the first waypoint, and then this method
        //  updates the external value to let the external program know what the correct next waypoint will be. It should be noted
        //  that the next waypoint is not simply incremented, but that many waypoints may be passed in determining the next waypoint.
        //
        //      The method updates the position to move towards the next waypoint, and if the next waypoint can be reached without
        //  exceeding the specified distance, it will go on and do the same for the waypoint after that, and so on and so forth. Once
        //  it reaches a point inbetween waypoints where the distance runs out, it will set the final position of the object to that
        //  spot. It will output the number of the next waypoint (NextPathPoint). Then it will calculate a direction vector to point to 
        //  the direction to that next waypoint. 
        //
        //      The object following the path could be anything. This method just treats the object according to it's position, orientation,
        //  and it's next waypoint. The next waypoint is calculated here and sent to the external program to be maintained and then
        //  it will be passed in again the next time, updated, and returned again.
        //
        //=======================================================================================================================
        {
            if (Distance > 0f)  //Don't try and move the object if the distance to be moved is zero. It will destroy the vectors, if you do.
            {
                Vector2 PathToNextWaypoint;     //Used to track direction to and distance of the next waypoint.
                float DistanceToNextWayPoint = 0f;  //Info contained in PathToNextWaypoint but made redundant for clarity.
                int NumberOfPathPoints = PathPoints.Count();


                PathToNextWaypoint = PathPoints[NextPathPoint] - Position; //Vector subtraction gives a new vector of distance & direction to waypoint.
                DistanceToNextWayPoint = PathToNextWaypoint.Length();   //Length is the distance between next path point and current position.
                while (Distance > DistanceToNextWayPoint)   //Loop until distance left to travel is less than distance to next point.
                {
                    Distance -= DistanceToNextWayPoint;         //Subtract the distance to next waypoint before moving there.
                    Position = PathPoints[NextPathPoint];     //Move to the next path point.
                    if (Forward == true)
                    {
                        //Move clockwise.
                        NextPathPoint++;
                        if (NextPathPoint >= PathPoints.Count()) NextPathPoint = 0; //Wrap around to the beginning if you go off the end.
                    }
                    else
                    {
                        //Move counter-clockwise.
                        NextPathPoint--;
                        if (NextPathPoint < 0) NextPathPoint = PathPoints.Count() - 1; //Wrap around to the beginning if you go off the end.
                    }
                    PathToNextWaypoint = PathPoints[NextPathPoint] - Position;  //Vector subtraction gives a new vector of distance & direction to waypoint.
                    DistanceToNextWayPoint = PathToNextWaypoint.Length();   //Length is the distance between next path point and current position.
                }

                //Distance is now smaller than distance between waypoints here.
                PathToNextWaypoint.Normalize(); //Normalize vector to remove distance information and prepare for scalar multiplication to reset distance/length.
                Position += PathToNextWaypoint * Distance; //Vector to scalar multiplication changes length of vector PathToNextWaypoint to Distance. Addition changes position by amount & direction of PathToNextWaypoint.
                //PathToNextWaypoint.Normalize(); //Normalize again because we want to use this for the Orientation normal which stores only the ship's heading.
                Orientation = PathToNextWaypoint;
            }
        }
        //=======================================================================================================================


        private void DefinePath()
        //=======================================================================================================================
        //  DefinePath()
        //  Parameters: None.
        //  Returns: None.
        //
        //  Purpose: Generates a path, or track, that an object can follow.
        //
        //  Explanation:
        //       When the Path is initialized before this, the control points are defined. The control points allow the programmer
        //  to layout the track by specifiying points along the track. Each control point will be a path on the track. They go in
        //  the order they were defined. Path points are generated between control points at that point.
        //
        //      This method uses Catmull-Rom to define smooth curves between control points. It looks at the waypoint that came
        //  before for the first handle. And it looks at the waypoint two ahead to determine the position of the second handle. 
        //  Then using those handles it shapes the curve between the two center waypoints into a smooth curve that turns to face
        //  the previous waypoint and the waypoint after the spline.
        //
        //=======================================================================================================================
        {
            int NumberOfControlPoints = ControlPoints.Count;

            PathPoints = new List<Vector2>();
            for (int ControlPoint = 0; ControlPoint < NumberOfControlPoints; ControlPoint++)
            {
                PathPoints.Add(ControlPoints[ControlPoint]);    //Add the control point to the list of Path Points that define the path.

                //Don't reprocess the ControlPoints(ends of the spline).
                for (int SplinePoint = 1; SplinePoint < SplinePoints; SplinePoint++)
                {
                    float Percent = (float)SplinePoint / (float)SplinePoints;
                    Vector2 PreviousControlPoint = ControlPoints[WrapPoint(ControlPoint - 1, NumberOfControlPoints - 1)];
                    Vector2 CurrentControlPoint = ControlPoints[ControlPoint];
                    Vector2 NextControlPoint = ControlPoints[WrapPoint(ControlPoint + 1, NumberOfControlPoints - 1)];
                    Vector2 NextNextControlPoint = ControlPoints[WrapPoint(ControlPoint + 2, NumberOfControlPoints - 1)];
                    Vector2 Position = Vector2.CatmullRom(PreviousControlPoint, CurrentControlPoint, NextControlPoint, NextNextControlPoint, Percent);
                    PathPoints.Add(Position);
                }
            }
        }
        //=======================================================================================================================


        private int WrapPoint(int Point, int MaxPoint)
        //=======================================================================================================================
        //  WrapPoint()
        //  Parameters: 
        //      Point - the control point number.
        //      MaxPoint - the last control point number in the list of control points.
        //  Returns: int - the control point number wrapped if it falls off the ends.
        //
        //  Purpose: Changes the control point number if it is out of range.
        //
        //  Explanation:
        //       The control points can all be numbered zero through the number of control points minus one. When doing that
        //  it's easy to specify a control point number that's outside of the range of valid control point numbers. This method
        //  verifies that the control point number given is in the valid range. And if it's not, it updates it to wrap it around
        //  the other side by the amount that it would have gone out of range. This allows the ends of the path to meet each other
        //  and become a closed circuit.
        //
        //=======================================================================================================================
        {
            if (Point > MaxPoint)
            {
                Point -= MaxPoint + 1;  //Point is already across "the line" and we subtract 1 from the top to bring it back in.
            }
            else
            {
                if (Point < 0) Point += MaxPoint + 1;    //Point is already across "the line" and we subtract 1 from the top to bring it back in.
            }
            return Point;
        }
        //=======================================================================================================================
    }

}





Hi,

First of all thanks BBeck for this awesome and helpful explanation about path movement.

I have played around with your code, and got it working pretty well.
However I have been unable to further develop it so that I could add any number of Ships to follow the curve, lets say when I press Space a new Ship is spawned at the beginning of track. I currently can spawn them at the position where the initial Ship is traveling..

How could I implement this simple modification?


BR,
-Tryk
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2