I’m playing around with the TrackGenerator Blueprint from Blueprint Splines Track available from the Learn section in the Unreal Engine Launcher.
Now that I’ve created a simple track, I want to track the progress of vehicles on the track. One way would be using checkpoints at each spline point. Another would be comparing the distance from the vehicle to the previous spline point with the distance to the next one and incrementing a variable if the latter is lesser. This solution is what I have implemented right now, but I’m wondering if there’s a better way. I’d also prefer to get the exact distance along spline, not just the number of the last visited spline point.
The main reason I’m asking is because the following blog article makes it sound like there is a better way: RED:OUT by 34BigThings - Unreal Engine
The quote I’m referring to is “It’s very easy to know at which point of the spline players are, at any given time.”
There are many ways to get approximations, but none (I think), will give you the exact position on a spline. There are too many variables to solve the equation to get the exact closet point.
The simplest way is just to take a sample of 10, 100, or 1000 points on the spline and see which is closest. This is inefficient and won’t get very close if your spline is long. The method I use now is get 3 points: first, middle, and last. Check to see which are the closest 2 points and again and check those against one that lies in the middle of those. With just a couple iterations of that you can get very close. Put in a tolerance so it doesn’t keep checking forever.
That still seems like a lot of work. If I understand correctly, you’re basically doing the same thing you described in the first sentence, but you’re doing it using bisection, instead of doing it linearly (much faster, but still not O(1)).
As I mentioned in the question, your vehicle should have a member variable that holds the number of the last spline point it reached. Then, you can just compare two points at a time, not N (all) of them.
I’ll write an answer with more details.
Since there has been no answer for a long time now, I’ll describe what I ended up doing. Different answers are still welcome.
Let the vehicle class have two member variables: LastSplinePointNumber and DistanceTravelledAlongSpline.
At each tick (or any interval you’d like), set DistanceTravelledAlongSpline to GetDistanceAlongSplineAtSplinePoint(LastSplinePointNumber) + distance travelled from GetWorldLocationAtSplinePoint(LastSplinePointNumber) to GetWorldLocationAtSplinePoint(LastSplinePointNumber + 1). You can calculate that second addend using vector projection.
If DistanceTravelledAlongSpline is now greater than GetDistanceAlongSplineAtSplinePoint(LastSplinePointNumber + 1), the vehicle has reached the next spline point, so increment its LastSplinePointNumber.
This assumes that the spline is a polygonal chain (set all spline points’ types to linear), but it works well enough with a curved spline.
you can also factor in the last spline position to get the new spline position. This is the algorithm I use for my game since the character goes though jumps, loops, slow motion etc all based on physical forces, and I needed the exact location down to the 0.1 unit.
I believe I was able to write a function(a pure one even) in blueprint to achieve this. I have included a screenshot of my graph. I have tested this a few times and it seems to work. If anyone finds that this doesn’t work please say so.
I was part way into trying to implement an expandable checkpoint and distance comparison thing to do this, I knew there had to be a better way but couldn’t see how to get the right info off the spline to get it to work. that example is so much simpler and think solves all the headache, cheers for posting it
This is a good solution but as a heads up to anyone in a similar situation to mine - I’ve found this solution to be innacurate when your spline points are not equally spaced. Our splines tend to have wildly different distances between points and when testing this solution we had issues.
Hmm ok, well in our game, the distances can range point-to-point from around 10 meters to around 1000 meters. Is that similar to yours? It was in the most extreme change that I was finding innacuracy
Oh mine aren’t that far apart, ranging from 1 meter to about 5 meters, so no where near as different as yours. I hope you find a solution that works for you, and I’m sorry mine didn’t.
I had the same problem. I initially tried that linear interpolation approach but is not as exact as I needed it to be in spline curves. So I added this numerical approximation to iteratively correct the distance value.
float GetDistanceAlongSplineForWorldLocation(FVector Location) const
{
const float ClosestInputKey = Spline->FindInputKeyClosestToWorldLocation(Location);
const int32 PreviousPoint = FMath::TruncToInt(ClosestInputKey);
// Lerp between the previous and the next spline points
float Distance = Spline->GetDistanceAlongSplineAtSplinePoint(PreviousPoint);
Distance += (ClosestInputKey - PreviousPoint) * (Spline->GetDistanceAlongSplineAtSplinePoint(PreviousPoint + 1) - Distance);
// The linear approximation is not enough. So here is a kinda numerical approximation.
for (int32 i = 0; i < DistanceSolverIterations; ++i)
{
const float InputKeyAtDistance = Spline->SplineCurves.ReparamTable.Eval(Distance, 0.0f);
// The euclidean distance between the current calculated distance and the real closest point
const float Delta = (Spline->GetLocationAtSplineInputKey(InputKeyAtDistance, ESplineCoordinateSpace::World) - Spline->GetLocationAtSplineInputKey(ClosestInputKey, ESplineCoordinateSpace::World)).Size();
if (InputKeyAtDistance < ClosestInputKey)
{
Distance += Delta;
}
else if (InputKeyAtDistance > ClosestInputKey)
{
Distance -= Delta;
}
else
{
break;
}
}
return FMath::Clamp(Distance, 0.0f, GetPathLength());
}
This gives a really good approximation with just 1 or 2 iterations.