Colisión bola a bola: detección y manejo

Con la ayuda de la comunidad Stack Overflow, he escrito un simulador de física bastante básico pero divertido.

Hace clic y arrastra el mouse para lanzar una pelota. Saltará y finalmente se detendrá en el "piso".

Mi próxima gran característica que quiero agregar es la colisión bola a bola. El movimiento de la pelota se divide en hacha y vector de velocidad. Tengo gravedad (pequeña reducción del vector y en cada paso), tengo fricción (pequeña reducción de ambos vectores cada colisión con una pared). Las bolas se mueven honestamente de una manera sorprendentemente realista.

Supongo que mi pregunta tiene dos partes:

1. ¿Cuál es el mejor método para detectar la colisión de bola a bola?
   ¿Solo tengo un bucle O (n ^ 2) que itera sobre cada bola y comprueba cada otra bola para ver si se superpone el radio?
2. ¿Qué ecuaciones utilizo para manejar las colisiones entre bolas? Física 101
   ¿Cómo afecta a los vectores de velocidad x / y de dos bolas? ¿En qué dirección se dirigen las dos bolas? ¿Cómo aplico esto a cada bola?

Manejar la detección de colisiones de las "paredes" y los cambios de vectores resultantes fueron fáciles, pero veo más complicaciones con las colisiones de bolas. Con los muros, simplemente tenía que tomar el negativo del vector x o y apropiado y partirlo iría en la dirección correcta. Con las bolas no creo que sea así.

Algunas aclaraciones rápidas: por simplicidad, estoy bien con una colisión perfectamente elástica por ahora, también todas mis bolas tienen la misma masa en este momento, pero podría cambiar eso en el futuro.

Editar: recursos que he encontrado útiles

Física de la bola 2D con vectores: colisiones bidimensionales sin trigonometría.pdf
Ejemplo de detección de colisión de bola 2D: adición de detección de colisión

¡Éxito!

¡Tengo la detección y respuesta de colisión de bolas funcionando muy bien!

Código relevante:

Detección de colisiones:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
        }
    }
}

Esto verificará si hay colisiones entre cada bola, pero omite las verificaciones redundantes (si tiene que verificar si la bola 1 colisiona con la bola 2, entonces no necesita verificar si la bola 2 colisiona con la bola 1. Además, omite la comprobación de colisiones consigo mismo )

Luego, en mi clase de pelota tengo mis métodos colliding () y resolveCollision ():

public boolean colliding(Ball ball)
{
    float xd = position.getX() - ball.position.getX();
    float yd = position.getY() - ball.position.getY();

    float sumRadius = getRadius() + ball.getRadius();
    float sqrRadius = sumRadius * sumRadius;

    float distSqr = (xd * xd) + (yd * yd);

    if (distSqr <= sqrRadius)
    {
        return true;
    }

    return false;
}

public void resolveCollision(Ball ball)
{
    // get the mtd
    Vector2d delta = (position.subtract(ball.position));
    float d = delta.getLength();
    // minimum translation distance to push balls apart after intersecting
    Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); 


    // resolve intersection --
    // inverse mass quantities
    float im1 = 1 / getMass(); 
    float im2 = 1 / ball.getMass();

    // push-pull them apart based off their mass
    position = position.add(mtd.multiply(im1 / (im1 + im2)));
    ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));

    // impact speed
    Vector2d v = (this.velocity.subtract(ball.velocity));
    float vn = v.dot(mtd.normalize());

    // sphere intersecting but moving away from each other already
    if (vn > 0.0f) return;

    // collision impulse
    float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
    Vector2d impulse = mtd.normalize().multiply(i);

    // change in momentum
    this.velocity = this.velocity.add(impulse.multiply(im1));
    ball.velocity = ball.velocity.subtract(impulse.multiply(im2));

}

Código fuente: fuente completa para el colisionador bola a bola.

Si alguien tiene algunas sugerencias sobre cómo mejorar este simulador de física básica, ¡hágamelo saber! Una cosa que aún tengo que agregar es el momento angular para que las bolas rueden de manera más realista. ¿Cualquier otra sugerencia? ¡Deja un comentario!

Para detectar si dos bolas chocan, solo verifique si la distancia entre sus centros es menor que dos veces el radio. Para hacer una colisión perfectamente elástica entre las bolas, solo necesita preocuparse por el componente de la velocidad que está en la dirección de la colisión. El otro componente (tangente a la colisión) se mantendrá igual para ambas bolas. Puede obtener los componentes de colisión creando un vector unitario que apunte en la dirección de una bola a la otra, luego tomando el producto de punto con los vectores de velocidad de las bolas. Luego puede conectar estos componentes en una ecuación de colisión 1D perfectamente elástica.

Wikipedia tiene un resumen bastante bueno de todo el proceso . Para bolas de cualquier masa, las nuevas velocidades se pueden calcular utilizando las ecuaciones (donde v1 y v2 son las velocidades después de la colisión, y u1, u2 son de antes):

Si las bolas tienen la misma masa, entonces las velocidades simplemente cambian. Aquí hay un código que escribí que hace algo similar:

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

En cuanto a la eficiencia, Ryan Fox tiene razón, debe considerar dividir la región en secciones, luego hacer una detección de colisión dentro de cada sección. Tenga en cuenta que las bolas pueden chocar con otras bolas en los límites de una sección, por lo que esto puede hacer que su código sea mucho más complicado. Sin embargo, la eficiencia probablemente no importará hasta que tengas varios cientos de bolas. Para obtener puntos de bonificación, puede ejecutar cada sección en un núcleo diferente o dividir el procesamiento de colisiones dentro de cada sección.

Bueno, hace años hice el programa como el que presentaste aquí.
Hay un problema oculto (o muchos, depende del punto de vista):

• Si la velocidad de la pelota es demasiado alta, puede perderse la colisión.

Y también, casi en un 100% de los casos, sus nuevas velocidades serán incorrectas. Bueno, no velocidades , sino posiciones . Tienes que calcular nuevas velocidades con precisión en el lugar correcto. De lo contrario, solo cambia las bolas en una pequeña cantidad de "error", que está disponible en el paso discreto anterior.

La solución es obvia: debe dividir el paso de tiempo de modo que primero cambie al lugar correcto, luego colisione y luego cambie el resto del tiempo que tenga.

Debe usar la partición de espacio para resolver este problema.

Lea sobre Particionamiento de espacio binario y Quadtrees

Como una aclaración a la sugerencia de Ryan Fox de dividir la pantalla en regiones, y solo buscar colisiones dentro de las regiones ...

por ejemplo, divida el área de juego en una cuadrícula de cuadrados (que arbitrariamente dirá que son de 1 unidad de longitud por lado), y verifique las colisiones dentro de cada cuadrado de la cuadrícula.

Esa es absolutamente la solución correcta. El único problema con él (como señaló otro afiche) es que las colisiones entre fronteras son un problema.

La solución a esto es superponer una segunda cuadrícula en un desplazamiento vertical y horizontal de 0,5 unidades a la primera.

Entonces, cualquier colisión que atraviese límites en la primera cuadrícula (y, por lo tanto, no se detecte) estará dentro de los cuadrados de la cuadrícula en la segunda cuadrícula. Siempre que realice un seguimiento de las colisiones que ya ha manejado (ya que es probable que haya alguna superposición), no tiene que preocuparse por manejar casos extremos. Todas las colisiones estarán dentro de un cuadrado de cuadrícula en una de las cuadrículas.

Una buena forma de reducir el número de comprobaciones de colisión es dividir la pantalla en diferentes secciones. Entonces solo compara cada bola con las bolas en la misma sección.

Una cosa que veo aquí para optimizar.

Si bien estoy de acuerdo en que las bolas golpean cuando la distancia es la suma de sus radios, ¡uno nunca debería calcular esta distancia! Más bien, calcule que es cuadrado y trabaje con él de esa manera. No hay razón para esa costosa operación de raíz cuadrada.

Además, una vez que haya encontrado una colisión, debe continuar evaluando las colisiones hasta que no queden más. El problema es que el primero puede causar otros que deben resolverse antes de obtener una imagen precisa. ¿Considera qué sucede si la pelota golpea una pelota en el borde? La segunda bola golpea el borde e inmediatamente rebota en la primera bola. Si golpeas una pila de bolas en la esquina, podrías tener bastantes colisiones que deben resolverse antes de poder repetir el siguiente ciclo.

En cuanto a la O (n ^ 2), todo lo que puede hacer es minimizar el costo de rechazar las que faltan:

1) Una pelota que no se mueve no puede golpear nada. Si hay un número razonable de bolas en el suelo, esto podría ahorrar muchas pruebas. (Tenga en cuenta que aún debe verificar si algo golpeó la bola estacionaria).

2) Algo que podría valer la pena hacer: divida la pantalla en varias zonas, pero las líneas deben estar borrosas: las bolas en el borde de una zona se enumeran en todas las zonas relevantes (podrían ser 4). Usaría una cuadrícula de 4x4, almacenaría las zonas como bits. Si un AND de las zonas de dos zonas de bolas devuelve cero, final de la prueba.

3) Como mencioné, no hagas la raíz cuadrada.

Encontré una página excelente con información sobre detección de colisión y respuesta en 2D.

http://www.metanetsoftware.com/technique.html

Tratan de explicar cómo se hace desde un punto de vista académico. Comienzan con la simple detección de colisión de objeto a objeto, y continúan con la respuesta de colisión y cómo escalarla.

Editar: enlace actualizado

Tienes dos formas fáciles de hacer esto. Jay ha cubierto la forma precisa de verificar desde el centro de la pelota.

La forma más fácil es usar un cuadro delimitador de rectángulo, establecer el tamaño de su cuadro en un 80% del tamaño de la pelota y simulará una colisión bastante bien.

Agregue un método a su clase de pelota:

public Rectangle getBoundingRect()
{
   int ballHeight = (int)Ball.Height * 0.80f;
   int ballWidth = (int)Ball.Width * 0.80f;
   int x = Ball.X - ballWidth / 2;
   int y = Ball.Y - ballHeight / 2;

   return new Rectangle(x,y,ballHeight,ballWidth);
}

Luego, en tu bucle:

// Checks every ball against every other ball. 
// For best results, split it into quadrants like Ryan suggested. 
// I didn't do that for simplicity here.
for (int i = 0; i < balls.count; i++)
{
    Rectangle r1 = balls[i].getBoundingRect();

    for (int k = 0; k < balls.count; k++)
    {

        if (balls[i] != balls[k])
        {
            Rectangle r2 = balls[k].getBoundingRect();

            if (r1.Intersects(r2))
            {
                 // balls[i] collided with balls[k]
            }
        }
    }
}

Lo veo insinuado aquí y allá, pero también podría hacer un cálculo más rápido primero, como comparar los cuadros delimitadores para la superposición, y LUEGO hacer una superposición basada en el radio si esa primera prueba pasa.

La matemática de adición / diferencia es mucho más rápida para un cuadro delimitador que todos los trigonométricos para el radio, y la mayoría de las veces, la prueba del cuadro delimitador descartará la posibilidad de una colisión. Pero si luego vuelve a probar con trigonometría, está obteniendo los resultados precisos que está buscando.

Sí, son dos pruebas, pero en general será más rápido.

Esta KineticModeles una implementación del enfoque citado en Java.

Implementé este código en JavaScript usando el elemento HTML Canvas, y produjo simulaciones maravillosas a 60 cuadros por segundo. Comencé la simulación con una colección de una docena de bolas en posiciones y velocidades aleatorias. Descubrí que a velocidades más altas, una colisión de deslumbramiento entre una bola pequeña y una mucho más grande hizo que la bola pequeña pareciera PEGAR al borde de la bola más grande, y se movió hasta alrededor de 90 grados alrededor de la bola más grande antes de separarse. (Me pregunto si alguien más observó este comportamiento).

Algunos registros de los cálculos mostraron que la Distancia mínima de traducción en estos casos no era lo suficientemente grande como para evitar que las mismas bolas colisionen en el siguiente paso. Experimenté un poco y descubrí que podía resolver este problema ampliando el MTD en función de las velocidades relativas:

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

Verifiqué que antes y después de esta solución, la energía cinética total se conservaba para cada colisión. El valor 0.5 en mtd_factor fue aproximadamente el valor mínimo encontrado que siempre causa que las bolas se separen después de una colisión.

Aunque esta solución introduce una pequeña cantidad de error en la física exacta del sistema, la desventaja es que ahora se pueden simular bolas muy rápidas en un navegador sin disminuir el tamaño del paso de tiempo.