我在这里看到了一个需要优化的东西。

虽然我同意球的撞击距离是它们的半径之和，但实际上不应该计算这个距离!更确切地说，计算它是方形的，并以这种方式处理它。没有理由进行昂贵的平方根运算。

Also, once you have found a collision you have to continue to evaluate collisions until no more remain. The problem is that the first one might cause others that have to be resolved before you get an accurate picture. Consider what happens if the ball hits a ball at the edge? The second ball hits the edge and immediately rebounds into the first ball. If you bang into a pile of balls in the corner you could have quite a few collisions that have to be resolved before you can iterate the next cycle.

至于O(n²)，你所能做的就是尽量减少拒绝错过的代价:

1)不动的球打不到任何东西。如果有一个合理数量的球躺在地板上，这可以节省很多测试。(注意，你仍然必须检查是否有东西击中了固定球。)

2)可能值得做的事情:将屏幕划分为许多区域，但线条应该是模糊的——区域边缘的球被列为所有相关的区域(可能是4个)。我会使用4x4网格，将区域存储为位。如果两个球的区域的AND返回0，测试结束。

3)正如我提到的，不要做平方根。

I implemented this code in JavaScript using the HTML Canvas element, and it produced wonderful simulations at 60 frames per second. I started the simulation off with a collection of a dozen balls at random positions and velocities. I found that at higher velocities, a glancing collision between a small ball and a much larger one caused the small ball to appear to STICK to the edge of the larger ball, and moved up to around 90 degrees around the larger ball before separating. (I wonder if anyone else observed this behavior.)

一些计算记录显示，在这些情况下，最小平移距离不足以防止相同的球在下一个时间步中发生碰撞。我做了一些实验，发现我可以通过根据相对速度放大MTD来解决这个问题:

dot_velocity = ball_1.velocity.dot(ball_2.velocity);
mtd_factor = 1. + 0.5 * Math.abs(dot_velocity * Math.sin(collision_angle));
mtd.multplyScalar(mtd_factor);

我验证了在修正之前和之后，每次碰撞的总动能都是守恒的。mtd_factor中的0.5值大约是在碰撞后总是导致球分离的最小值。

虽然这个修复在系统的精确物理中引入了少量的错误，但代价是现在可以在浏览器中模拟非常快的球，而不减少时间步长。

我找到了一个很棒的页面，上面有关于2D碰撞检测和响应的信息。

http://www.metanetsoftware.com/technique.html (web.archive.org)

他们试图从学术的角度解释这是如何做到的。他们从简单的对象对对象碰撞检测开始，然后转向碰撞响应以及如何扩展它。

编辑:更新链接

为了澄清Ryan Fox的建议，将屏幕分割成区域，并且只检查区域内的冲突……

例如，将游戏区域分割成一个方格网格(即每边有一个单位长度)，并检查每个方格网格之间的冲突。

这绝对是正确的解决方案。唯一的问题(正如另一个帖子指出的那样)是跨边界的碰撞是一个问题。

解决方案是在第一个网格上以0.5单位的垂直和水平偏移覆盖第二个网格。

然后，任何跨越第一个网格边界的碰撞(因此不会被检测到)将在第二个网格的方格内。只要跟踪已经处理过的碰撞(因为可能会有一些重叠)，就不必担心处理边缘情况。所有的碰撞都将发生在其中一个网格上的方格内。

To detect whether two balls collide, just check whether the distance between their centers is less than two times the radius. To do a perfectly elastic collision between the balls, you only need to worry about the component of the velocity that is in the direction of the collision. The other component (tangent to the collision) will stay the same for both balls. You can get the collision components by creating a unit vector pointing in the direction from one ball to the other, then taking the dot product with the velocity vectors of the balls. You can then plug these components into a 1D perfectly elastic collision equation.

维基百科对整个过程有一个很好的总结。对于任何质量的球，新的速度可以用以下公式计算(其中v1和v2是碰撞后的速度，u1和u2是碰撞前的速度):

如果两个球质量相同，那么速度只是互换。下面是我写的一些类似的代码:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
    // Check whether there actually was a collision
    if (a == b)
        return;

    Vector collision = a.position() - b.position();
    double distance = collision.length();
    if (distance == 0.0) {              // hack to avoid div by zero
        collision = Vector(1.0, 0.0);
        distance = 1.0;
    }
    if (distance > 1.0)
        return;

    // Get the components of the velocity vectors which are parallel to the collision.
    // The perpendicular component remains the same for both fish
    collision = collision / distance;
    double aci = a.velocity().dot(collision);
    double bci = b.velocity().dot(collision);

    // Solve for the new velocities using the 1-dimensional elastic collision equations.
    // Turns out it's really simple when the masses are the same.
    double acf = bci;
    double bcf = aci;

    // Replace the collision velocity components with the new ones
    a.velocity() += (acf - aci) * collision;
    b.velocity() += (bcf - bci) * collision;
}

至于效率，Ryan Fox是对的，您应该考虑将区域划分为部分，然后在每个部分中进行碰撞检测。请记住，球可以在一个部分的边界上与其他球碰撞，所以这可能会使您的代码更加复杂。不过，在你有几百个球之前，效率可能并不重要。为了获得额外的奖励，你可以在不同的核心上运行每个部分，或者在每个部分中拆分碰撞处理。

这是一个支持质量的简单例子。

private void CollideBalls(Transform ball1, Transform ball2, ref Vector3 vel1, ref Vector3 vel2, float radius1, float radius2)
{
    var vec = ball1.position - ball2.position;
    float dis = vec.magnitude;
    if (dis < radius1 + radius2)
    {
        var n = vec.normalized;
        ReflectVelocity(ref vel1, ref vel2, ballMass1, ballMass2, n);

        var c = Vector3.Lerp(ball1.position, ball2.position, radius1 / (radius1 + radius2));
        ball1.position = c + (n * radius1);
        ball2.position = c - (n * radius2);
    }
}

public static void ReflectVelocity(ref Vector3 vel1, ref Vector3 vel2, float mass1, float mass2, Vector3 intersectionNormal)
{
    float velImpact1 = Vector3.Dot(vel1, intersectionNormal);
    float velImpact2 = Vector3.Dot(vel2, intersectionNormal);

    float totalMass = mass1 + mass2;
    float massTransfure1 = mass1 / totalMass;
    float massTransfure2 = mass2 / totalMass;

    vel1 += ((velImpact2 * massTransfure2) - (velImpact1 * massTransfure2)) * intersectionNormal;
    vel2 += ((velImpact1 * massTransfure1) - (velImpact2 * massTransfure1)) * intersectionNormal;
}