
В процессе разработки игры в совершенно различных жанровых категориях может возникнуть потребность «запустить» какой-либо игровой объект вдоль гладкой кривой с постоянной или контролируемой скоростью, будь то грузовик, следующий из города А в город Б, выпущенная по хитрой траектории ракета, или самолет противника, выполняющий заложенный манёвр.
Наверное, каждый имеющий отношение к теме знает или, по крайней мере, слышал, про кривые Безье, B-сплайны, сплайны Эрмита и прочие интерполяционные и сглаживающие сплайны и совершенно правильно предложил бы использовать в описанной ситуации один из них, но не всё так просто, как хотелось бы.
В нашем случае сплайн — это функция, отображающая набор входных параметров (контрольные точки) и значение аргумента
В качестве примера можно рассмотреть кубическую кривую Безье, которая задаётся следующим уравнением:

Кубическая кривая Безье
На рисунке изображены две кубических кривые Безье, задаваемых четырьмя точками (через две из них кривая проходит, оставшиеся две задают кривизну).

Анимация отображения параметра t в точку кривой
Для того, чтобы из участков кривых построить более сложный и вариативный маршрут, их можно соединить по цепочке, оставляя одну общую точку-звено:

Кусочный сплайн
С заданием и параметризацией маршрута разобрались, теперь переходим к основному вопросу. Чтобы наш условный самолёт двигался вдоль маршрута с постоянной скоростью, нам нужно в любой момент времени уметь вычислять точку на кривой в зависимости от пройденного вдоль этой кривой расстояния
Первой мыслью было сделать линейное отображение

Проблема данного способа очевидна сразу же — на самом деле пройденная дистанция

«Равномерно» распределенные по пути точки
Самолёт будет замедляться на одних участках и ускоряться на других, чем делает данный способ параметризации кривой совершенно неприменимым для решения описанной задачи (самолёт выбран исключительно в качестве наглядного примера и цель описать его движение физически корректным способом не преследовалась):

Визуализация неправильной параметризации кривой
Обратившись за советом в поисковик, на stackoverflow и youtube, я обнаружил второй способ вычисления

Представление кривой в виде кусочно-линейного сплайна
Процедура эта итеративная: берется небольшой шаг по
Пример кода
Источник
public Vector2[] CalculateEvenlySpacedPoints(float spacing, float resolution = 1)
{
List<Vector2> evenlySpacedPoints = new List<Vector2>();
evenlySpacedPoints.Add(points[0]);
Vector2 previousPoint = points[0];
float dstSinceLastEvenPoint = 0;
for (int segmentIndex = 0; segmentIndex < NumSegments; segmentIndex++)
{
Vector2[] p = GetPointsInSegment(segmentIndex);
float controlNetLength = Vector2.Distance(p[0], p[1]) + Vector2.Distance(p[1], p[2]) + Vector2.Distance(p[2], p[3]);
float estimatedCurveLength = Vector2.Distance(p[0], p[3]) + controlNetLength / 2f;
int divisions = Mathf.CeilToInt(estimatedCurveLength * resolution * 10);
float t = 0;
while (t <= 1)
{
t += 1f/divisions;
Vector2 pointOnCurve = Bezier.EvaluateCubic(p[0], p[1], p[2], p[3], t);
dstSinceLastEvenPoint += Vector2.Distance(previousPoint, pointOnCurve);
while (dstSinceLastEvenPoint >= spacing)
{
float overshootDst = dstSinceLastEvenPoint - spacing;
Vector2 newEvenlySpacedPoint = pointOnCurve + (previousPoint - pointOnCurve).normalized * overshootDst;
evenlySpacedPoints.Add(newEvenlySpacedPoint);
dstSinceLastEvenPoint = overshootDst;
previousPoint = newEvenlySpacedPoint;
}
previousPoint = pointOnCurve;
}
}
return evenlySpacedPoints.ToArray();
}
И, вроде бы, задача решена, ведь можно разбить маршрут на очень много отрезков и радоваться тому, как плавно и размеренно движется объект, так как вычисление точки на кусочно-линейной функции — дело простое и быстрое. Но у такого подхода тоже есть довольно очевидные недостатки, которые не давали мне покоя — довольно затратная процедура изменения шага разбиения или геометрии кривой и необходимость поиска баланса между точностью (большее потребление памяти) и экономией памяти (становится более заметной «ломаность» маршрута).
Вследствие чего я продолжил поиски и наткнулся на отличную статью «Moving Along a Curve with Specified Speed», на основе которой строятся дальнейшие рассуждения.
Значение скорости можно вычислить как
Используя замену переменной дифференцирования, мы можем записать
Теперь получим соотношение между
Нас же интересует обратная операция, то есть вычисление значения аргумента
Метод образует последовательность приближений вида
Выбор
Далее выполняем итерации методом Ньютона до тех пор, пока погрешность решения не станет приемлемой, либо количество проделанных итераций — непозволительно большим.
При использовании стандартного метода Ньютона потенциально может возникнуть проблема. Функция
Остается выбрать метод численного интегрирования — я воспользовался квадратурами метода Гаусса, так как он обеспечивает достаточно точный результат при небольших затратах.
Код функции, вычисляющей t(s)
public float ArcLength(float t) => Integrate(x => TangentMagnitude(x), 0, t);
private float Parameter(float length)
{
float t = 0 + length / ArcLength(1);
float lowerBound = 0f;
float upperBound = 1f;
for (int i = 0; i < 100; ++i)
{
float f = ArcLength(t) - length;
if (Mathf.Abs(f) < 0.01f)
break;
float derivative = TangentMagnitude(t);
float candidateT = t - f / derivative;
if (f > 0)
{
upperBound = t;
if (candidateT <= 0)
t = (upperBound + lowerBound) / 2;
else
t = candidateT;
}
else
{
lowerBound = t;
if (candidateT >= 1)
t = (upperBound + lowerBound) / 2;
else
t = candidateT;
}
}
return t;
}
Код функции численного интегрирования
private static readonly (float, float)[] CubicQuadrature =
{(-0.7745966F, 0.5555556F), (0, 0.8888889F), (0.7745966F, 0.5555556F)};
public static float Integrate(Func<float, float> f, in float lowerBound, in float uppedBound)
{
var sum = 0f;
foreach (var (arg, weight) in CubicQuadrature)
{
var t = Mathf.Lerp(lowerBound, uppedBound, Mathf.InverseLerp(-1, 1, arg));
sum += weight * f(t);
}
return sum * (upperBound - lowerBound) / 2;
}
Далее можно настроить погрешность метода Ньютона, выбрать более точный метод численного интегрирования, но задача, по сути, решена — был построен алгоритм вычисления аргумента

Равномерно распределенные вдоль пути точки

Теперь самолет движется равномерно
Таким образом, нами были рассмотрены несколько способов параметризации сплайна относительно пройденного расстояния, в использованной мной в качестве источника статье в качестве варианта автор предлагает численно решать дифференциальное уравнение, но, по его собственной ремарке, предпочитает модифицированный метод Ньютона:
I prefer the Newton’s-method approach because generally t can be computed faster than with differential equation solvers.
В качестве заключения приведу таблицу времени расчета положения точки на представленной на скриншотах кривой в одном потоке на процессоре i5-9600K:
Кол-во вычислений | Среднее время, мс |
---|---|
100 | 0,62 |
1000 | 6,24 |
10000 | 69,01 |
100000 | 672,81 |