Collision de balle à balle - Détection et manipulation

266

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

texte alternatif

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?

texte alternatif

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!

mmcdole
la source
16
Je ne pense pas que cet algorithme soit assez bon parce que si vos balles se déplacent trop vite (ex: plus rapide que 2 * rayon par image, une balle peut passer à travers une autre balle sans collision.
Benji Mizrahi
@Simulcal pourriez-vous télécharger à nouveau votre code source (tous les liens de deposedperper.com semblent rompus). Pourriez-vous également mettre en place le fichier pdf que vous avez obtenu de [geocities.com/vobarian/2dcollisions/2dcollisions.pdf] car les géocités ont été déconnectées récemment
bguiz
1
Voici un lien vers la dernière version de BallBounce sur laquelle j'ai travaillé: dl.dropbox.com/u/638285/ballbounce.rar
mmcdole
@Pour tous ceux qui ont contribué: pouvez-vous faire la lumière pour transformer ce moteur en 3D? Comment ce grand moteur peut également fonctionner dans Java3D.
vide principal statique
2
La ligne Vector2d impulse = mtd.multiply(i);doit être i * le vecteur mtd normalisé. Quelque chose comme:Vector2d impulse = mtd.normalize().multiply(i);
klenwell

Réponses:

117

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

v_ {1} = \ frac {u_ {1} (m_ {1} -m_ {2}) + 2m_ {2} u_ {2}} {m_ {1} + m_ {2}}

v_ {2} = \ frac {u_ {2} (m_ {2} -m_ {1}) + 2m_ {1} u_ {1}} {m_ {1} + m_ {2}}

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.

Jay Conrod
la source
2
Disons que les masses des deux balles ne sont pas égales. Comment cela affecte-t-il le changement de vecteur entre les boules?
mmcdole
3
Cela fait un moment depuis la 12e année, mais je pense qu'ils obtiennent un rapport de l'élan correspondant au rapport des masses.
Ryan Fox
6
@Jay, juste pour souligner .. qu'une image d'équation que vous avez ajoutée est pour une collision à 1 dimension, pas à 2 dimensions.
mmcdole
@simucal. pas vrai ... u et v sont des vecteurs dans cette équation. Autrement dit, ils ont des composants x, y (et z).
Andrew Rollings,
2
@Simucal, vous avez raison, ils sont pour le cas unidimensionnel. Pour plus de dimensions, utilisez simplement les composantes de la vitesse qui sont en ligne avec la collision (aci, bci dans le code). Les autres composants sont orthogonaux à la collision et ne changeront pas, vous n'avez donc pas à vous en préoccuper.
Jay Conrod
48

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.

avp
la source
Si les positions de décalage timeframelength*speed/2étaient activées, les positions seraient statistiquement fixes.
Nakilon
@Nakilon: non, cela n'aide que dans certains cas, mais il est généralement possible de rater la collision. Et la probabilité de manquer la collision augmente avec la taille de la durée. Soit dit en passant, il semble qu'Aleph ait démontré la bonne solution (je l'ai juste survolée cependant).
avp
1
@avp, je n'étais pas sur Si la vitesse de la balle est trop élevée, vous pouvez manquer la collision. , mais vos nouvelles positions seront fausses . En raison de la collision est détectée un peu plus tard, ils sont vraiment entrés en collision, si soustraire timeframelength*speed/2de cette position, la précision augmentera deux fois.
Nakilon
20

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

grepsedawk
la source
4
Au lieu de partitionner l'espace, un algorithme de balayage et d'élagage ne fonctionnerait-il pas mieux? les boules se déplacent rapidement, donc tout partitionnement devra être mis à jour fréquemment, entraînant des frais généraux. Un balayage et un pruneau pourraient trouver toutes les paires en collision dans O (n log n), sans aucune structure de données transitoire. Voici un bon tutoriel pour les bases
HugoRune
13

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.

Andrew Rollings
la source
+1 pour une solution plus précise, et pour contrer le lâche downvoter drive-by
Steven A. Lowe
1
c'est une bonne idée. Je l'ai fait une fois et j'ai vérifié la cellule actuelle et toutes les cellules voisines, mais votre méthode est plus efficace. Une autre façon dont je viens de penser est de vérifier la cellule actuelle, puis de vérifier si elle intersecte les limites des cellules actuelles, et si oui, de vérifier les objets dans CETTE cellule voisine.
LoveMeSomeCode
10

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.

Ryan Fox
la source
5
Correction: vous devez vérifier les collisions avec les mêmes sections ET adjacentes
impression
7

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.

Loren Pechtel
la source
Merci pour les informations sur la pointe de la racine carrée. Je ne connaissais pas sa nature chère par rapport à la place.
mmcdole
Une autre optimisation consisterait à trouver des balles qui sont loin des autres balles. Cela ne fonctionnerait de manière fiable que si les vitesses des billes sont limitées.
Brad Gilbert
1
Je ne suis pas d'accord sur la recherche de balles isolées. C'est aussi cher que de détecter la collision. Pour améliorer les choses, vous avez besoin de quelque chose qui est inférieur à O (n) pour la balle en question.
Loren Pechtel
7

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

Markus Jarderot
la source
3

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]
            }
        }
    }
}
FlySwat
la source
1
Cela ferait entrer les boules dans l'autre 20% sur les collisions horizontales et verticales. Autant utiliser des boîtes de délimitation circulaires, car la différence d'efficacité est négligeable. En outre, (x-width)/2devrait l'être x-width/2.
Markus Jarderot
Bon appel à la faute de frappe de priorité. Vous constaterez que la plupart des jeux 2d utilisent des boîtes de délimitation rectangulaires sur des formes non rectangulaires car c'est rapide, et l'utilisateur ne le remarque presque jamais de toute façon.
FlySwat
Vous pouvez faire un cadre de délimitation rectangulaire, puis s'il a un hit, cochez le cadre de délimitation circulaire.
Brad Gilbert
1
@Jonathan Holland, votre boucle interne devrait être pour (int k = i + 1; ...) Cela supprimera tous les contrôles redondants. (c.-à-d. vérification avec collision de soi et vérification collision collision balle1 avec balle2 puis balle2 avec balle1).
mmcdole
4
En fait, une boîte de délimitation carrée est susceptible d'être moins performante en termes de performances qu'une boîte de délimitation circulaire (en supposant que vous avez optimisé la racine carrée)
Ponkadoodle
3

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.

Jason Kleban
la source
6
Vous n'avez pas besoin de trig. bool is_overlapping(int x1, int y1, int r1, int x2, int y2, int r2) { return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<(r1+r2)*(r1+r2); }
Ponkadoodle
3

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

trashgod
la source
2

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.

Stefan Musarra
la source
1
le péché (..) n'est pas une fonction bon marché
PaulHK