两运动圆形对象碰撞时间预测算法实现问题排查

原实现的核心问题 #

你的代码存在三类明显问题，会导致结果不符合预期，同时存在不必要的性能损耗：

• 精度缺失：循环仅检查整数步长t=1,2...149的位置，会漏掉两个整数时刻之间发生的碰撞；同时硬编码150的遍历上限，会把t≥150才发生的碰撞全部误判为不碰撞
• 逻辑漏洞：没有判断两物体的相对运动方向，如果两物体初始未碰撞且处于互相远离的状态，依然会无意义跑满149次循环才返回结果
• 性能与计算冗余：逐帧遍历的时间复杂度为O(n)，完全可以通过数学推导用O(1)复杂度算出结果；此外每次循环重复计算(a.Radius + b.Radius)的平方，这个固定值完全可以提前算好复用

解析法实现原理 #

匀速运动的圆形碰撞不需要逐帧遍历，可以直接通过求解一元二次方程得到精确碰撞时刻：

1. 把问题转换到相对运动坐标系：设两物体位置差向量 s = a.Position - b.Position，相对速度向量 v = a.LinearVelocity - b.LinearVelocity，两物体半径和为r
2. 碰撞发生的充要条件是存在t≥0，使得t时刻两物体距离等于半径和，即 |s + t*v|² = r²
3. 展开向量方程得到标准一元二次方程：|v|² * t² + 2*(s·v)*t + (|s|² - r²) = 0
4. 根据方程系数和判别式即可判断碰撞情况，算出精确碰撞时间，不需要任何循环

优化后代码 #

public float CalculateCollisionTime(CircleEntity a, CircleEntity b)
{
    // 预计算固定常量，避免重复运算
    float totalRadius = a.Radius + b.Radius;
    float totalRadiusSq = totalRadius * totalRadius;

    Vector3 posDelta = a.Position - b.Position;
    Vector3 velDelta = a.LinearVelocity - b.LinearVelocity;

    // 初始时刻已经处于碰撞状态
    float posDeltaSq = posDelta.sqrMagnitude;
    if (posDeltaSq <= totalRadiusSq)
    {
        return 0f;
    }

    float velDeltaSq = velDelta.sqrMagnitude;
    // 两物体相对静止，初始未碰撞则永远不会碰撞
    if (velDeltaSq < 1e-6f)
    {
        return float.PositiveInfinity;
    }

    // 构造一元二次方程 At² + Bt + C = 0
    float A = velDeltaSq;
    float B = 2f * Vector3.Dot(posDelta, velDelta);
    float C = posDeltaSq - totalRadiusSq;

    float discriminant = B * B - 4 * A * C;
    // 判别式小于0，无实根，运动轨迹无交点
    if (discriminant < 0f)
    {
        return float.PositiveInfinity;
    }

    float sqrtD = MathF.Sqrt(discriminant);
    float t1 = (-B - sqrtD) / (2 * A);
    float t2 = (-B + sqrtD) / (2 * A);

    // 最早碰撞时刻小于0，说明碰撞发生在过去，当前两物体正在远离
    if (t1 < 0f)
    {
        return float.PositiveInfinity;
    }

    // 返回精确的连续碰撞时刻，无整数步长带来的精度损失
    return t1;
}

方案优势 #

• 精度无损失：直接计算连续时间域内的精确碰撞时刻，不会漏判、晚判碰撞
• 性能极高：仅需固定次数的浮点运算，无循环开销，适合大规模碰撞检测场景
• 边界覆盖完整：覆盖了初始碰撞、相对静止、轨迹不相交、互相远离等所有边界情况，不会出现逻辑误判

内容的提问来源于stack exchange，提问作者Ioannis Kiaras