Collision de balle à balle - Détection et manipulation

Avec l'aide de la communauté Stack Overflow, j'ai écrit un simulateur de physique assez basique mais amusant.

Vous cliquez et faites glisser la souris pour lancer une balle. Il rebondira et finira par s'arrêter sur le "sol".

Ma prochaine grande fonctionnalité que je veux ajouter est la collision balle à balle. Le mouvement de la balle est divisé en un vecteur de vitesse ax et y. J'ai la gravité (petite réduction du vecteur y à chaque pas), j'ai le frottement (petite réduction des deux vecteurs à chaque collision avec un mur). Les balles se déplacent honnêtement d'une manière étonnamment réaliste.

Je suppose que ma question comporte deux parties:

1. Quelle est la meilleure méthode pour détecter une collision balle à balle?
   Ai-je juste une boucle O (n ^ 2) qui itère sur chaque balle et vérifie toutes les autres billes pour voir si son rayon se chevauche?
2. Quelles équations dois-je utiliser pour gérer les collisions de balle à balle? Physique 101
   Comment affecte- t-il les vecteurs x / y de vitesse des deux balles? Quelle est la direction résultante dans laquelle les deux balles se dirigent? Comment appliquer cela à chaque balle?

La gestion de la détection de collision des «murs» et des changements de vecteur qui en ont résulté a été facile, mais je vois plus de complications avec les collisions boule-balle. Avec les murs, je devais simplement prendre le négatif du vecteur x ou y approprié et il irait dans la bonne direction. Avec des balles, je ne pense pas que ce soit comme ça.

Quelques précisions rapides: pour plus de simplicité, je suis d'accord avec une collision parfaitement élastique pour l'instant, aussi toutes mes balles ont la même masse en ce moment, mais je pourrais changer cela à l'avenir.

Edit: Ressources que j'ai trouvées utiles

Physique de la balle 2D avec des vecteurs: Collisions bidimensionnelles sans trigonométrie.pdf
Exemple de détection de collision de balle 2D: Ajout de la détection de collision

Succès!

J'ai la détection de collision de balle et la réponse qui fonctionnent très bien!

Code pertinent:

Détection de collision:

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

Cela vérifiera les collisions entre chaque balle mais sautera les contrôles redondants (si vous devez vérifier si la balle 1 entre en collision avec la balle 2, vous n'avez pas besoin de vérifier si la balle 2 entre en collision avec la balle 1. En outre, elle ignore la vérification des collisions avec elle-même. ).

Ensuite, dans ma classe de balle, j'ai mes méthodes colliding () et resolCollision ():

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

}

Code source: source complète pour collisionneur de balle à balle.

Si quelqu'un a des suggestions pour améliorer ce simulateur de physique de base, faites-le moi savoir! Une chose que je n'ai pas encore ajoutée est l'élan angulaire afin que les balles roulent de manière plus réaliste. D'autres suggestions? Laissez un commentaire!

Pour détecter si deux boules entrent en collision, vérifiez simplement si la distance entre leurs centres est inférieure à deux fois le rayon. Pour faire une collision parfaitement élastique entre les billes, il suffit de se soucier de la composante de la vitesse qui est dans le sens de la collision. L'autre composant (tangent à la collision) restera le même pour les deux balles. Vous pouvez obtenir les composants de collision en créant un vecteur unitaire pointant dans la direction d'une balle à l'autre, puis en prenant le produit scalaire avec les vecteurs de vitesse des billes. Vous pouvez ensuite brancher ces composants dans une équation de collision 1D parfaitement élastique.

Wikipedia a un assez bon résumé de l'ensemble du processus . Pour les balles de n'importe quelle masse, les nouvelles vitesses peuvent être calculées en utilisant les équations (où v1 et v2 sont les vitesses après la collision et u1, u2 sont d'avant):

Si les balles ont la même masse, les vitesses sont simplement commutées. Voici un code que j'ai écrit qui fait quelque chose de similaire:

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 ce qui concerne l'efficacité, Ryan Fox a raison, vous devriez envisager de diviser la région en sections, puis de détecter les collisions dans chaque section. Gardez à l'esprit que les balles peuvent entrer en collision avec d'autres balles aux limites d'une section, cela peut donc rendre votre code beaucoup plus compliqué. L'efficacité n'aura probablement aucune importance tant que vous n'aurez pas plusieurs centaines de balles. Pour les points bonus, vous pouvez exécuter chaque section sur un noyau différent, ou diviser le traitement des collisions au sein de chaque section.

Eh bien, il y a des années, j'ai créé le programme comme vous l'avez présenté ici.
Il y a un problème caché (ou plusieurs, cela dépend du point de vue):

• Si la vitesse de la balle est trop élevée, vous pouvez rater la collision.

Et aussi, presque dans 100% des cas, vos nouvelles vitesses seront fausses. Pas des vitesses , mais des positions . Vous devez calculer précisément les nouvelles vitesses au bon endroit. Sinon, vous déplacez simplement les balles sur une petite quantité "d'erreur", qui est disponible à partir de l'étape discrète précédente.

La solution est évidente: vous devez diviser le pas de temps de manière à ce que vous vous déplaciez d'abord au bon endroit, puis que vous vous heurtiez, puis que vous changiez pour le reste du temps dont vous disposez.

Vous devez utiliser le partitionnement d'espace pour résoudre ce problème.

En savoir plus sur le partitionnement de l'espace binaire et les Quadtrees

Pour clarifier la suggestion de Ryan Fox de diviser l'écran en régions et de ne vérifier que les collisions à l'intérieur des régions ...

Par exemple, divisez la zone de jeu en une grille de carrés (qui sera arbitrairement indiquée comme étant d'une unité de longueur par côté) et vérifiez les collisions à l'intérieur de chaque carré de la grille.

C'est absolument la bonne solution. Le seul problème avec cela (comme l'a souligné une autre affiche) est que les collisions à travers les frontières sont un problème.

La solution à cela consiste à superposer une deuxième grille à un décalage vertical et horizontal de 0,5 unité par rapport à la première.

Ensuite, toutes les collisions qui dépasseraient les limites de la première grille (et donc ne seraient pas détectées) se trouveront dans les carrés de la grille de la deuxième grille. Tant que vous gardez une trace des collisions que vous avez déjà traitées (car il y aura probablement des chevauchements), vous n'avez pas à vous soucier de la gestion des cas de bord. Toutes les collisions se feront à l'intérieur d'un carré de grille sur l'une des grilles.

Un bon moyen de réduire le nombre de contrôles de collision consiste à diviser l'écran en différentes sections. Vous ne comparez alors que chaque balle aux balles de la même section.

Une chose que je vois ici pour optimiser.

Bien que je convienne que les balles frappent lorsque la distance est la somme de leurs rayons, il ne faut jamais réellement calculer cette distance! Calculez plutôt son carré et travaillez de cette façon. Il n'y a aucune raison pour cette opération coûteuse de racine carrée.

De plus, une fois que vous avez trouvé une collision, vous devez continuer à évaluer les collisions jusqu'à ce qu'il n'en reste plus. Le problème est que le premier peut en entraîner d'autres qui doivent être résolus avant d'obtenir une image précise. Considérez ce qui se passe si la balle frappe une balle au bord? La deuxième balle touche le bord et rebondit immédiatement dans la première balle. Si vous frappez dans un tas de boules dans le coin, vous pourriez avoir un bon nombre de collisions qui doivent être résolues avant de pouvoir itérer le cycle suivant.

Quant au O (n ^ 2), tout ce que vous pouvez faire est de minimiser le coût du rejet de ceux qui manquent:

1) Une balle qui ne bouge pas ne peut rien toucher. S'il y a un nombre raisonnable de balles sur le sol, cela pourrait économiser beaucoup de tests. (Notez que vous devez toujours vérifier si quelque chose a touché la balle stationnaire.)

2) Quelque chose qui pourrait valoir la peine d'être fait: divisez l'écran en un certain nombre de zones mais les lignes doivent être floues - les boules au bord d'une zone sont répertoriées comme se trouvant dans toutes les zones pertinentes (peut-être 4). Je voudrais utiliser une grille 4x4, stocker les zones sous forme de bits. Si un ET des zones de deux zones de balles renvoie zéro, fin du test.

3) Comme je l'ai mentionné, ne faites pas la racine carrée.

J'ai trouvé une excellente page avec des informations sur la détection et la réponse aux collisions en 2D.

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

Ils essaient d'expliquer comment cela se fait d'un point de vue académique. Ils commencent par la simple détection de collision d'objet à objet, puis passent à la réponse à la collision et à la manière de l'intensifier.

Modifier: lien mis à jour

Vous avez deux façons simples de procéder. Jay a couvert la façon précise de vérifier depuis le centre de la balle.

Le moyen le plus simple consiste à utiliser un rectangle englobant, définissez la taille de votre boîte à 80% de la taille de la balle, et vous simulez assez bien la collision.

Ajoutez une méthode à votre classe de balle:

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

Ensuite, dans votre boucle:

// 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]
            }
        }
    }
}

Je le vois ici et là, mais vous pouvez également faire un calcul plus rapide, comme comparer les boîtes englobantes pour le chevauchement, puis faire un chevauchement basé sur le rayon si ce premier test réussit.

Le calcul d'addition / différence est beaucoup plus rapide pour une boîte englobante que tous les trig pour le rayon, et la plupart du temps, le test de la boîte englobante écarte la possibilité d'une collision. Mais si vous testez à nouveau avec trig, vous obtenez les résultats précis que vous recherchez.

Oui, c'est deux tests, mais ce sera globalement plus rapide.

Il KineticModels'agit d'une implémentation de l' approche citée en Java.

J'ai implémenté ce code en JavaScript en utilisant l'élément HTML Canvas, et il a produit de merveilleuses simulations à 60 images par seconde. J'ai commencé la simulation avec une collection d'une douzaine de balles à des positions et des vitesses aléatoires. J'ai trouvé qu'à des vitesses plus élevées, une collision en jetant un coup d'œil entre une petite balle et une balle beaucoup plus grande faisait que la petite balle semblait coller au bord de la plus grande balle et se déplaçait jusqu'à environ 90 degrés autour de la plus grande balle avant de se séparer. (Je me demande si quelqu'un d'autre a observé ce comportement.)

Une certaine journalisation des calculs a montré que la distance de translation minimale dans ces cas n'était pas assez grande pour empêcher les mêmes boules de se heurter au pas de temps suivant. J'ai fait quelques expériences et j'ai découvert que je pouvais résoudre ce problème en augmentant la MTD en fonction des vitesses relatives:

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

J'ai vérifié qu'avant et après cette correction, l'énergie cinétique totale était conservée pour chaque collision. La valeur 0,5 dans le mtd_factor était approximativement la valeur minimale trouvée pour toujours provoquer la séparation des billes après une collision.

Bien que ce correctif introduise une petite quantité d'erreur dans la physique exacte du système, le compromis est que des boules très rapides peuvent maintenant être simulées dans un navigateur sans diminuer la taille du pas de temps.