About Store Forum Documentation Contact



Post Reply 
Creating/moving along a path
Author Message
Tottel Offline
Member

Post: #1
Creating/moving along a path
Hello everyone!

For my benchmarking tool, I needed a way to create and visualize smooth paths. And then, I needed a way to move an object (camera) along that path. Since it's a benchmarking tool, it has to work flawlessly at any framerate.
This required a bit more work than I had anticipated, since movement could just stop working or be totally wrong with low FPS, or high movement speed.
But after redesigning the movement calculation, it now works absolutely perfect under all conditions.

I present to you, a test project that allows you to:
- Place points by left-clicking on the screen. A continuous spline will be generated, connecting these points (you need a minimum of 4 points first).
- Move a dot along the path by holding Right mouse
- Set speed and resolution in real time
- Movement is always exact and smooth, no matter what framerate or dot-speed you run at.

I have made this test project in 2D so I could easily isolate just the path and movement code. I'm using the same code for my 3D application, all you need to do is replace Vec2 with Vec.
Lastly, I use "points" that I placed in the world editor, instead of placing them with clicking.

Have fun! I hope it's useful for someone.

Spline Project

(Yes, the project is just 3KB)
(This post was last modified: 04-06-2015 10:47 AM by Tottel.)
04-06-2015 10:29 AM
Find all posts by this user Quote this message in a reply
Zervox Offline
Member

Post: #2
RE: Creating/moving along a path
first and last points aren't calculated in the path. ; )
04-06-2015 11:17 AM
Find all posts by this user Quote this message in a reply
Tottel Offline
Member

Post: #3
RE: Creating/moving along a path
Zervox: That's because of how the spline is calculated smile

It uses Lerp4, which is a hermite spline function. It only connects the 2nd and 3rd point, based on the 1st and 4th. They are control points.
(This post was last modified: 04-06-2015 11:23 AM by Tottel.)
04-06-2015 11:23 AM
Find all posts by this user Quote this message in a reply
Zervox Offline
Member

Post: #4
RE: Creating/moving along a path
you are using pointers and new for the lines without deleting them, this results in memory leaks. wink
(This post was last modified: 04-06-2015 11:45 AM by Zervox.)
04-06-2015 11:44 AM
Find all posts by this user Quote this message in a reply
Tottel Offline
Member

Post: #5
RE: Creating/moving along a path
Haha will fix. Been using C# for too long now xD
04-06-2015 11:53 AM
Find all posts by this user Quote this message in a reply
Zervox Offline
Member

Post: #6
RE: Creating/moving along a path
(04-06-2015 11:53 AM)Tottel Wrote:  Haha will fix. Been using C# for too long now xD

You are getting infected by it! wink
Anyways all in all a neat tool.
(This post was last modified: 04-06-2015 12:01 PM by Zervox.)
04-06-2015 12:00 PM
Find all posts by this user Quote this message in a reply
Tottel Offline
Member

Post: #7
RE: Creating/moving along a path
File has been updated. I've fixed the memory leaks (thanks, Zervox!) and added some comments.
04-06-2015 12:13 PM
Find all posts by this user Quote this message in a reply
Rubeus Offline
Member

Post: #8
RE: Creating/moving along a path
I am interested in seeing the calculations you use for this, but I just moved and am unable to use my PC. Specifically, I've been having an issue with varying speeds between splines. If you don't mind, could I get you post the calculations you use in plain text format?
04-06-2015 05:02 PM
Find all posts by this user Quote this message in a reply
Tottel Offline
Member

Post: #9
RE: Creating/moving along a path
Hey Rubeus, of course!

First of all, I have a line class, which simply contains a start and end point. But it also has a bunch of methods that return useful things.

Code:
class Line
{
   Line()
   {
      
   }
   Line(Vec2 p1, Vec2 p2)
   {
      _p1 = p1;
      _p2 = p2;
   }
   /******************************************************************************/
   void Draw()
   {
      D.line(GREEN, _p1, _p2);
   }
   /******************************************************************************/
   Vec2 GetP1() { return _p1; }
   Vec2 GetP2() { return _p2; }
  
   Vec2 GetDir()
   {
      Vec2 dir = (_p2 - _p1);
      dir.normalize();
      
      return dir;
   }
  
   flt GetLength () { return (_p2 - _p1).length() ; }
   flt GetLength2() { return (_p2 - _p1).length2(); }
  
   // What is the position in screenspace if we have moved 0..1 along the line
   Vec2 GetPosForProgress(flt prog) { return Lerp(_p1, _p2, prog); }
   // What is the remaining length of the line if we have move 0..1 along the line
   flt GetLengthLeftForProgress(flt prog)
   {
      return (_p2 - GetPosForProgress(prog)).length();
   }
   /******************************************************************************/
  
private:
  
   Vec2 _p1, _p2;
}

Now, for my path, I store the points that will connect the lines, and the lines itself. The amount of lines is dependent on the spline resolution. You just need to calculate this once, unless you want to update the path in real-time.
Here is how I calculate and store the lines in between the path nodes:

Code:
void ConstructPath()
{
   // Clean up the existing path
   FREPA(_pathLines)
   {
      delete _pathLines[i];
   }
   _pathLines.clear();
      
   // Only start constructing the path when we have at least 4 points
   if(_pathPoints.elms() > 3)
   {
      int conn = _pathPoints.elms() - 3; // This is the amount of connections we have to calculate
        
      // For every connection
      FREPD(start, conn)
      {
         flt index = 0.0f;
            
         // Calculate all line segments, based on the line resolution
         FREP(_lineRes)
         {
            Vec2 p1 = Lerp4(_pathPoints[start+0], _pathPoints[start+1], _pathPoints[start+2], _pathPoints[start+3], index);
            index += 1.0f / _lineRes;
            Vec2 p2 = Lerp4(_pathPoints[start+0], _pathPoints[start+1], _pathPoints[start+2], _pathPoints[start+3], index);
            
            _pathLines.add(new Line(p1, p2));
         }
      }
   }
}

Next, we move along the spline. To do this, we set a bool to start moving, and we update a member CurrPos every frame, like so:

Code:
if(_moving)
{
    if(_pathLines.elms() > 0)
    {
        _currPos = FindNextPointOnLineToMove();
        _dir     = FindDirectionFromLine();
    }
}

Direction you can return from the current line segment (_pathLines[_currIndex].GetDir(); ), but finding the position takes some more calculations:

Code:
// For movement, calculate the distance that we want to move in ONE frame.
   // Then calculate how much we move along the line segments with this distance.
   Vec2 FindNextPointOnLineToMove()
   {
      flt distance = Time.d() * _speed; // This is how much we want to move in 1 frame
      
      // Keep moving until we run out of distance to move
      while(distance > 0)
      {
         flt lineLengthLeft = _pathLines[_currIndex].GetLengthLeftForProgress(_currLineProgress);
        
         if((distance - lineLengthLeft) > 0)
         {
            distance -= lineLengthLeft;
            _currIndex++;
            _currLineProgress = 0;
            
            if(_currIndex >= _pathLines.elms())
            {
               StopMovingAlongPath();
              
               return _pathLines[_pathLines.elms()-1].GetP2(); // Return end position, stop there
            }
         }
         else
         {
            flt length = _pathLines[_currIndex].GetLength();
            
            _currLineProgress += distance * (1 / length); // Convert the distance we have left, relative to the line length
            break;
         }
      }
      
      return _pathLines[_currIndex].GetPosForProgress(_currLineProgress);
   }

This gives you a completely uniform move speed along the spline, and it will work regardless of which speed you set or how low your FPS is or how smooth or crude your spline is.

I hope that helps!
04-06-2015 05:34 PM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #10
RE: Creating/moving along a path
Thanks for sharing!

As a side note:
You can achieve something similar with Game.Waypoint method:
Code:
Vec pos   (Flt x, Bool smooth=false)C; // get position at 'x' total length, 'smooth' if use additional spline based smoothing
04-06-2015 09:08 PM
Find all posts by this user Quote this message in a reply
Tottel Offline
Member

Post: #11
RE: Creating/moving along a path
(04-06-2015 09:08 PM)Esenthel Wrote:  As a side note:
You can achieve something similar with Game.Waypoint method:
Code:
Vec pos   (Flt x, Bool smooth=false)C; // get position at 'x' total length, 'smooth' if use additional spline based smoothing

:x

Ah well, at least I did something, right? grin
04-06-2015 09:14 PM
Find all posts by this user Quote this message in a reply
Rofar Offline
Member

Post: #12
RE: Creating/moving along a path
(04-06-2015 11:53 AM)Tottel Wrote:  Haha will fix. Been using C# for too long now xD

Using C# a lot (me too) will definitely make you lazy and forget about important things like that. As much as I like C#, that is the one thing that worries me about using it so often.
04-06-2015 10:01 PM
Find all posts by this user Quote this message in a reply
Rubeus Offline
Member

Post: #13
RE: Creating/moving along a path
Ok, so instead of using the spline for the movement, you use the spline to create a list of points along the spline. I ended up doing pretty much the same thing. It has always seemed so inefficient when the spline can be calculated in so many fewer calculations. But trying to iterate multiple non-uniform splines at a constant speed is an impossibility, as far as I've been able to research.
In my code, I stored the direction of the next point, as well as the distance between each point to avoid any extra heavy calcs(divides, .length()s, etc). Uses a small bit more memory, but for a good amount of cpu time.

But I haven't played around with Game.Waypoint at all. I'll have to give it a more indepth look when I finally can use my PC again(5 weeks and counting).
(This post was last modified: 04-07-2015 12:38 AM by Rubeus.)
04-07-2015 12:38 AM
Find all posts by this user Quote this message in a reply
Zervox Offline
Member

Post: #14
RE: Creating/moving along a path
I guess I could suggest and additional feature that might be of interest of people which I used for prelocked camera before(don't have the source code anymore as I accidentally deleted some of the small projects I had over a year ago) and that was placing connected points which the camera would rotate look direction towards, this way I could set a focus point at any time having a camera move along the path but maintain a focused object(and it was alot more flexible and easier than having to hardcode look directions in code.)

@Rubeus, The calculations done in such an occasion should never impact performance by any noticeable degree, that is assuming you aren't calculating hundreds of lengths and divides per frame(Which is kind of overkill for a camera path atleast).
04-07-2015 01:04 AM
Find all posts by this user Quote this message in a reply
Post Reply