![](https://habrastorage.org/webt/y_/wd/wb/y_wdwbqye7xiqsbs1h6q_zhklg4.png)
В процессе разработки игры в совершенно различных жанровых категориях может возникнуть потребность «запустить» какой-либо игровой объект вдоль гладкой кривой с постоянной или контролируемой скоростью, будь то грузовик, следующий из города А в город Б, выпущенная по хитрой траектории ракета, или самолет противника, выполняющий заложенный манёвр.
Наверное, каждый имеющий отношение к теме знает или, по крайней мере, слышал, про кривые Безье, B-сплайны, сплайны Эрмита и прочие интерполяционные и сглаживающие сплайны и совершенно правильно предложил бы использовать в описанной ситуации один из них, но не всё так просто, как хотелось бы.
В нашем случае сплайн — это функция, отображающая набор входных параметров (контрольные точки) и значение аргумента (обычно принимающего значения от 0 до 1) в точку на плоскости или в пространстве. Получившаяся кривая — это множество значений функции-сплайна при .
В качестве примера можно рассмотреть кубическую кривую Безье, которая задаётся следующим уравнением:
![image](https://habrastorage.org/getpro/habr/post_images/4fe/d70/665/4fed70665a7725b68800e2bbda333509.jpg)
Кубическая кривая Безье
На рисунке изображены две кубических кривые Безье, задаваемых четырьмя точками (через две из них кривая проходит, оставшиеся две задают кривизну).
![image](https://habrastorage.org/getpro/habr/post_images/45d/35c/b4e/45d35cb4e1b446501fcefac07b3dab55.gif)
Анимация отображения параметра t в точку кривой
Для того, чтобы из участков кривых построить более сложный и вариативный маршрут, их можно соединить по цепочке, оставляя одну общую точку-звено:
![](https://habrastorage.org/webt/tu/h0/8u/tuh08u9rpqyzhryludrl0taerze.png)
Кусочный сплайн
С заданием и параметризацией маршрута разобрались, теперь переходим к основному вопросу. Чтобы наш условный самолёт двигался вдоль маршрута с постоянной скоростью, нам нужно в любой момент времени уметь вычислять точку на кривой в зависимости от пройденного вдоль этой кривой расстояния , при этом имея лишь возможность вычислить положение точки на кривой по значению параметра (функцию ). Именно на этом этапе начинаются сложности.
Первой мыслью было сделать линейное отображение и вычислить от получившегося значения — легко, вычислительно дёшево, в общем, то, что нужно.
![image](https://habrastorage.org/getpro/habr/post_images/d19/81b/533/d1981b5337d2a2b740ad8fc49e0350ea.jpg)
Проблема данного способа очевидна сразу же — на самом деле пройденная дистанция зависит от нелинейно, и чтобы в этом убедиться достаточно расставить по маршруту равномерно распределенные по значению точки:
![](https://habrastorage.org/webt/uj/uh/_s/ujuh_scbhlf9p0iporcu_0be5qy.png)
«Равномерно» распределенные по пути точки
Самолёт будет замедляться на одних участках и ускоряться на других, чем делает данный способ параметризации кривой совершенно неприменимым для решения описанной задачи (самолёт выбран исключительно в качестве наглядного примера и цель описать его движение физически корректным способом не преследовалась):
![](https://habrastorage.org/webt/fp/mx/71/fpmx71bdh4dcjk5oze7tjuo3y6w.gif)
Визуализация неправильной параметризации кривой
Обратившись за советом в поисковик, на stackoverflow и youtube, я обнаружил второй способ вычисления , а именно представление кривой в виде кусочно-линейной функции (расчета набора равноудаленных друг от друга по кривой точек):
![](https://habrastorage.org/webt/ej/s_/50/ejs_50c-xaggklwvmnuenaavevc.png)
Представление кривой в виде кусочно-линейного сплайна
Процедура эта итеративная: берется небольшой шаг по , с ним движемся по кривой, суммируя пройденное расстояние как длину кусочно-линейного сплайна до тех пор, пока не будет пройдено заданное расстояние, после чего точка запоминается, а процесс возобновляется.
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», на основе которой строятся дальнейшие рассуждения.
Значение скорости можно вычислить как , где — функция сплайна. Чтобы решить поставленную задачу, нужно найти функцию , где — длина дуги от начальной точки до искомой, и это выражение устанавливает соотношение между и .
Используя замену переменной дифференцирования, мы можем записать
Учитывая, что скорость — величина неотрицательная, получаем
так как по условию неизменности модуля вектора скорости (вообще говоря, равен не единице, а константе, но для простоты выкладок примем эту константу равной единице).
Теперь получим соотношение между и в явном виде:
откуда полная длина кривой , очевидно, вычисляется как . С помощью полученной формулы можно, имея значение аргумента , вычислить длину дуги до точки, в которую это значение отображается.
Нас же интересует обратная операция, то есть вычисление значения аргумента по заданной длине дуги :Так как не существует общего аналитического способа нахождения обратной функции, придется искать решение численное. Обозначим При заданном , требуется найти такое значение , при котором . Таким образом, задача превратилась в задачу поиска корня уравнения, с чем может прекрасно справиться метод Ньютона.
Метод образует последовательность приближений видагдеДля вычисления требуется вычислить , вычисление которого, в свою очередь, требует численного интегрирования.
Выбор в качестве начального приближения теперь выглядит разумным (вспоминаем первый подход к решению задачи).
Далее выполняем итерации методом Ньютона до тех пор, пока погрешность решения не станет приемлемой, либо количество проделанных итераций — непозволительно большим.
При использовании стандартного метода Ньютона потенциально может возникнуть проблема. Функция — неубывающая, так как её производная неотрицательна. Если вторая производная , то функцию называют выпуклой и метод Ньютона на ней гарантированно сходится к корню. Однако, в нашем случае, может оказаться отрицательной, из-за чего метод Ньютона может сойтись за пределами диапазона определения . Автор статьи предлагает использовать модификацию метода Ньютона, которая, в случае если очередной результат итерации методом Ньютона не попадает в текущий ограничивающий корень интервал, вместо него выбирает середину интервала (метод дихотомии). Вне зависимости от результата вычисления на текущей итерации, диапазон сужается, а значит, метод сходится к корню.
Остается выбрать метод численного интегрирования — я воспользовался квадратурами метода Гаусса, так как он обеспечивает достаточно точный результат при небольших затратах.
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;
}
Далее можно настроить погрешность метода Ньютона, выбрать более точный метод численного интегрирования, но задача, по сути, решена — был построен алгоритм вычисления аргумента сплайна для заданной длины дуги. Для объединения нескольких участков кривых в один и написания обобщенной процедуры вычисления можно хранить длины всех участков и предварительно вычислять индекс участка, на котором требуется произвести итеративную процедуру модифицированным методом Ньютона.
![](https://habrastorage.org/webt/gk/k7/ks/gkk7ksj5stqixot3zxlsrwfhxho.png)
Равномерно распределенные вдоль пути точки
![](https://habrastorage.org/webt/jz/yb/f9/jzybf9coxnny8hvtvz5bn6fxy44.gif)
Теперь самолет движется равномерно
Таким образом, нами были рассмотрены несколько способов параметризации сплайна относительно пройденного расстояния, в использованной мной в качестве источника статье в качестве варианта автор предлагает численно решать дифференциальное уравнение, но, по его собственной ремарке, предпочитает модифицированный метод Ньютона:
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 |
Griboks
Можно посмотреть с другой стороны: задать вектор скорости и вращать его по необходимости. И если уж мы говорим про игры, то самый частый случай — вращение в сторону цели с фиксированной скоростью, то необходимо на каждой итерации всего лишь вычислять знак полуплоскости цели от вектора скорости.