☔️ 👨‍👩‍👦‍👦 ☂️ 沿曲线均匀移动对象 ☦️ 🥡 📒

在开发完全不同流派类别的游戏的过程中，可能有必要以恒定或受控的速度沿着平滑曲线“发射”任何游戏对象，无论是卡车从城市A到城市B的移动，还是沿着狡猾的轨道发射的导弹，或者是敌机执行放下的动作。

可能与该主题相关的每个人都知道或至少听说过贝塞尔曲线，B样条曲线，Hermite样条曲线以及其他插值和平滑样条曲线，并且绝对会在上述情况下正确建议使用其中之一，但并非一切都那么简单如我们所愿。

在我们的例子中，样条函数是显示一组输入参数（控制点）和参数值的函数

t

$t$ （通常取值从0到1）到平面或空间中的一个点。结果曲线是样条函数的一组值

t \in [0, 1]

$t\in[0,1]$ ...

例如，考虑三次贝塞尔曲线，它由以下方程式给出：

$图片$

三次贝塞尔曲线

该图显示了两个三次贝塞尔曲线，由四个点定义（曲线通过其中两个点，其余两个点定义曲率）。

将参数t显示到曲线点的动画

为了从曲线部分构建更复杂且可变的路线，可以将它们连接成链，留下一条共同的点链接：

分段样条线我们已经

确定了路线的任务和参数设置，现在我们转向主要问题。为了使我们的常规飞机以恒定的速度沿路线移动，我们需要在任何时候都能够根据沿该曲线行进的距离来计算曲线上的一个点。

s (l e n)

$s(len)$ ，而仅具有根据参数值计算曲线上点的位置的能力

t

$t$ （功能

y (t)

$y(t)$ ）。困难就在这个阶段开始。

我的第一个想法是做线性映射

l e n \in [0, L e n g t h] \Rightarrow t \in [0, 1]

$len\in[0, Length] \Rightarrow t\in[0,1]$ 并计算

y (t)

$y(t)$ 从产生的价值中获取-简单，计算便宜，通常是您需要的。

这种方法的问题是显而易见的-实际上，所覆盖的距离

s

$s$ 取决于

t

$t$ 非线性的，并且为了确信这一点，沿着路径按值均匀分布就足够了

t

$t$ 点：

沿路径“均匀”分布的点

飞机在某些部分会减速，在其他部分会加速，这使得曲线的参数化方法完全不适用于解决所描述的问题（只选择了飞机作为说明性示例，而没有追求以物理上正确的方式描述其运动的目标）：

错误的曲线参数化可视化

在咨询了搜索引擎之后，在stackoverflow和youtube上，我找到了第二种计算方法

s (l e n) = g (t)

$s(len) = g(t)$ ，即以分段线性函数的形式表示曲线（计算沿曲线彼此等距的一组点）：

将曲线表示为分段线性样条曲线

此过程是迭代的：仅需花一小步

t

$t$ ，我们沿着它沿着曲线移动，将经过分段的线性样条曲线的长度的总和求和，直到覆盖指定的距离为止，然后记住该点，然后继续该过程。

样例代码

来源

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();
  }

而且，似乎可以解决问题，因为您可以将路线划分为多个段，并享受对象移动的平稳性，因为计算分段线性函数上的点既简单又快速。但是这种方法也有令我烦恼的明显缺点-更改分区步骤或曲线几何结构的成本很高，并且需要在精度（更多的内存消耗）和节省的内存之间找到平衡（“断路”变得更加明显）。

结果，我继续寻找并发现了一篇出色的文章“以指定速度沿曲线移动”，在此基础上进一步进行了推理。

速度值可以计算为

σ (t) = | V (t) | = | \frac{d X}{d t} |

$\sigma(t) = |V(t)|=|\frac{dX}{dt}|$ 哪里

X (t)

$X(t)$ -样条函数。要解决问题，需要找到功能

Y (t) = X (s)

$Y(t)=X(s)$ 哪里

s

$s$ -从起点到所需弧的弧长，此表达式建立了之间的关系

t

$t$ 和

s

$s$ ...

使用微分变量替换，我们可以编写

\frac{d Y}{d t} = \frac{d X}{d s} \frac{d s}{d t} .

$\frac{dY}{dt}=\frac{dX}{ds}\frac{ds}{dt}.$

考虑到速度是一个非负量，我们得到

| \frac{d Y}{d t} | = | \frac{d X}{d s} | | \frac{d s}{d t} | = \frac{d s}{d t},

$|\frac{dY}{dt}|=|\frac{dX}{ds}||\frac{ds}{dt}|=\frac{ds}{dt},$

因为

| \frac{d X}{d s} | = 1

$|\frac{dX}{ds}| = 1$ 根据速度矢量的模数保持不变的条件（通常来说，

| \frac{d X}{d s} |

$|\frac{dX}{ds}|$ 不等于1，而是一个常数，但是为了简化计算，我们将此常数设为1。

现在我们得到

t

$t$ 和

s

$s$ 明确地：

s = g (t) = \int_{0}^{t} | \frac{d Y (τ)}{d t} | d τ,

$s=g(t)=\int_{0}^{t}|\frac{dY(\tau)}{dt}|d\tau,$

曲线的总长度

L

$L$ 显然计算为

g (1)

$g(1)$ ... 使用结果公式，可以具有参数的值

t

$t$ ，计算到此值的弧长

t

$t$ 被展示。

我们对反向运算感兴趣，即计算参数的值

t

$t$ 沿给定的弧长

s

$s$ ：

t = g^{- 1} (s) .

$t=g^{-1}(s).$

由于没有找到反函数的通用解析方法，因此您将不得不寻找数值解。我们表示

F (t) = g (t) - s .

$F(t)=g(t)-s.$ 对于给定

s

$s$ ，则需要找到这样的值

t

$t$ 在哪

F (t) = 0

$F(t)=0$ ... 因此，任务变成了找到方程根的任务，牛顿的方法可以完美地解决。

该方法形成以下形式的近似序列

t_{i + 1} = t_{i} - \frac{F (t_{i})}{F^{'} (t_{i})},

$t_{i+1}=t_i-\frac{F(t_i)}{F'(t_i)},$

哪里

F^{'} (t) = \frac{d F}{d t} = \frac{d g}{d t} = | \frac{d Y}{d t} | .

$F'(t)=\frac{dF}{dt}=\frac{dg}{dt}=|\frac{dY}{dt}|.$

计算

F (t)

$F(t)$ 需要计算

g (t)

$g(t)$ ，其计算又需要数值积分。

选择

t_{0} = \frac{s}{L}

$t_0=\frac{s}{L}$ 因为初始近似值现在看起来是合理的（请回想一下解决问题的第一种方法）。

接下来，我们使用牛顿法进行迭代，直到解决方案误差变得可以接受，或者完成的迭代次数过大。

使用标准牛顿法存在潜在的问题。功能

F (t)

$F(t)$ -自减，因为其衍生

F^{'} (t) = | d Y / d t |

$F'(t)=|dY/dt|$ 是非负的。如果二阶导数

F^{″} (t) > 0

$F''(t)>0$ ，则该函数称为凸函数，并且可以保证该函数收敛到根。但是，就我们而言

F^{″} (t)

$F''(t)$ 可能为负，因此牛顿法可能收敛到定义范围之外

t \in [0, 1]

$t\in[0,1]$ ... 本文的作者建议使用牛顿法的一种修改，如果牛顿法的下一次迭代结果不属于当前以根为中心的区间，则选择区间的中间（二分法）。无论当前迭代的计算结果如何，范围都会缩小，这意味着该方法收敛于根。

仍然需要选择数值积分的方法-我使用了高斯方法的正交函数，因为它以低成本提供了相当准确的结果。

计算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;
}

接下来，您可以调整牛顿法的误差，选择一种更精确的数值积分方法，但是实际上，这个问题已解决-建立了用于计算自变量的算法

t

$t$ 给定弧长的样条曲线。将曲线的多个部分合并为一个并编写通用的计算过程

s (t)

$s(t)$ 您可以存储所有段的长度，并使用修改后的Newton方法预先计算要在其中执行迭代过程的段的索引。

点沿着路径均匀分布

现在平面均匀移动

因此，我们考虑了几种相对于行进距离对样条曲线进行参数化的方法，在我作为资料来源的文章中，作者建议通过数值方法求解微分方程，但是，根据他自己的评论，他倾向于采用改进的方法牛顿：

我更喜欢牛顿法，因为通常t可以比使用微分方程求解器更快地计算。

总结一下，我将给出一个时间表，用于计算i5-9600K处理器的一个线程中的屏幕快照中显示的曲线上的点的位置：

计算次数	平均时间，毫秒
100	0.62
1000	6.24
10000	69.01
100,000	672.81

我相信，如此高的计算速度使其有可能在各种游戏和模拟中使用它们。我很乐意在评论中进行实质性的澄清和批评。

沿曲线均匀移动对象

More articles: