Bonjour,
 
Je suis entrain de réaliser une petite application mettant en scène un certain nombres de billes se déplaçant dans un cadre. Elles seront soumises à un système de collision simple (choc élastique, que j'ai pu voir dans un autre topic).
 
Ma question est comment articuler tout ça ?
 
Aujourd'hui j'ai un vector de Billes et une bille possède une fonction du genre bille.estEnCollision(bille). Mon problème se situe un niveau au dessus, au niveau du système. Comment faire à chaque frame pour tester les collisions ? Parcourir le vector et tester pour chaque bille si elle est en collision avec les autres (Double boucle) ?
 
Où est-ce que la fonction estEnCollision doit être implémenter dans un manager de billes ?
 
J'ai pas trop d'idée sur la façon de structurer ce système de collision. Si vous avez des liens ou des articles, je suis preneur !
Merci de votre aide.

Y'a pas d'autre méthode que de comparer les collisions de chaque objet avec un autre.
Des moteurs physiques comme Havok, au plus simple de leur structure, fonctionnent comme ça. Tout ce qu'on peut faire ensuite, c'est améliorer la façon dont ça procède.
On peut couper l'espace en plusieurs zones, de façon à restreindre la recherche. Ou alors on peut juste regrouper les objets par petits groupes qui disposent alors d'une forme de collision simplifiée (genre un gros cube), car l'on sait que si un objet du groupe est touché, il y a des chances que les autres le soient aussi, ce qui s'étend ensuite aux groupes voisins. Ou alors tu peux simplifier le calcul... la méthode la plus simple consiste à effectuer le calcul sur des formes plus simples. Par exemple dans un Mario, chaque objet est un cube, mais les polygones ne sont pas gérés un par un. Ca simplifie le calcul de collision, et ça permet ainsi de mettre plus d'objets.

Quoi qu'il en soit, tu devras tester tous les cas possibles, il n'y a aucune parade à ça, et tu ne peux qu'optimiser ce processus. A toi de trouver la meilleure façon de procéder.

Ou alors y'a une méthode qui m'est inconnue qui permet de se passer ça, mais franchement, j'en doute...

Commence par la méthode simple avant de tenter les facons plus complexes (uniquement utiles si t'as un grand nombre de billes).
 
Il faut faire effectivement toutes les paires, à chaque frame, mais il te faut juste éviter de faire les tests en double (a vs. b et b vs. a) sinon tu va répondre en double aux collisions (et gaspiller la moitié de ton temps).
 
Le "manager de bille" est une bonne idée, il devra aussi manager les collisions avec les bords de ton cadre.
 
Occupe toi en premier de répondre correctement aux collisions.
 
C'est déjà pas si simple d'avoir de bonnes réponses aux collisions si tu ne fais que des détections à intervales régulier, par ex. comment réagir correctement à un choc élastique si les billes ont eu le temps de se traverser presque entièrement ? et comment réagir quand un groupe de plus de deux billes se cognent simultanément ? si tu résous les collisions bêtement l'une après l'autre tu risque déjà de voir apparaitre d'étranges bugs.
 
Optimiser et tenter d'éviter les tests inutiles avec des indexes spatiaux & co. ça peut venir après (c'est pas facile de debugger si t'as un mélange de tests de collisions qui manquent et de réactions aux collisions buggées, un bug à la fois c'est moins pénible).

En toute logique, on a (presque) jamais plus de deux objets qui entrent en collision l'un dans l'autre. Y'en a (presque) toujours deux qui se heurtent avant l'arrivée du troisième.
 
En ce qui concerne la traversée, c'est effectivement un problème. Il y a deux méthodes pour déterminer ça, bien que je sache pas du tout ce que c'est que ce truc de choc élastique : la méthode discrète, et la méthode continue.
 
La méthode discrète consiste à calculer à chaque frame un nouvel état après mise à jour de la position de tous les objets. Bien évidemment, si un objet se déplace à une vitesse supérieure à sa taille divisée par le pas de temps, cet objet passera à travers tous les autres. Pour résoudre ce problème, une seule solution : diminuer le pas de temps, donc faire plus de calculs. C'est dans 100% des cas la cause des bugs de moteur physique dans les jeux, où l'on voit des trucs qui se comportent bizarrement, comme des corps coincés à travers un mur ou autres du genre. Mais si tu définis une limite à la vitesse et que la taille du plus petit objet divisée par le pas de temps est inférieure à cette vitesse, alors tu n'auras aucun problème.
 
La méthode continue consiste à prévoir les collisions à l'avance pour les gérer parfaitement, calcul qui doit être intégralement refait à chaque changement de condition, aussi petit soit-il. Ça revient à une méthode discrète avec un pas de temps infiniment petit. C'est bien évidemment bieeeeeeeeeen plus lourd à exécuter, et bien plus lent, mais par contre la gestion est parfaite.
 
Evidemment, je te conseille la méthode discrète, c'est bien plus simple à mettre en place, et suffisant pour des petites applications graphiques.

Avec une méthode discrète et quelques billes coincées dans un coin de cadre ça arrive à coup sûr (et y'a de grandes chances de voir les billes finir par s'agglutiner les unes contre les autres ou passer à travers les murs).

Même avec une vitesse assez faible pour ne pas avoir de pénétration complète, avec des billes les angles de rebonds vont être pratiquement aléatoire (dans un impact avec des vecteurs non-colinénaires, un peu de retard et les centres des billes se décalent beaucoup, même si la pénétration est faible, et les centres des billes servant souvent à calculer l'angle de rebord, c'est la cata).

C'est juste une division et une racine carrée en plus pour savoir quand aura lieu une collision en plus de si elle a lieu. Y'a des complications pour avoir une résolution nickel ensuite, mais y'a aussi des méthodes à cout limité (en calcul et en code) qui améliorent déjà nettement la qualité des réponses.

Si la gestion des collisions est bien faite, y'a aucune raison que ça arrive. J'ai fait des animations de ce genre des tonnes de fois pour des projets à la con, j'ai jamais eu de problème franchement...
 

Ah non c'est un peu plus compliqué, vu qu'une collision peut en cacher une autre
Il faut lister les collisions, les trier de façon temporelle, et ne conserver que la première, vu qu'elle va logiquement perturber toutes les suivantes, et tous ces calculs auront été faits pour rien... Mais c'est vrai que j'avais une optique davantage 3D pour ça, où là ça devient un peu plus tendu... en effet pour des billes, ça posera pas vraiment problème.

Ça dépends le genre d'anim, un grand festival de billes façon feux-d'artifice de particules ça passe nickel, par contre si y'a peu de billes et que l'utilisateur observe ou pire, doit jouer avec, il risque de pas aimer les collisions qui partent de travers.

Vu que tu n'avance que jusqu'à la première collision, tu sais que la suivante est soit :
- la suivante dans la liste triée
- une nouvelle collision issue de la collision tout juste résolue, mais il n'y a que 2 billes (enfin, sauf collision simultanée ) qui peuvent y participer, seulement 2 billes à tester et pas tout le bordel.
Du coup, les calculs n'ont pas été fait pour rien. la première tournée est en O(n²), comme pour la méthode discrète mais les tours suivants sont en O(n) (+ le maintient de la liste des collisions futures, y'a le choix dans les structures de données, il faut pouvoir éliminer tout les events associés à une bille dès que celle-ci est impliquée dans une collision réalisée, pusher des nouveaux events et poper le plus proche) et on peut continuer comme ça jusqu'à la fin d'un gros pas de temps.
Ça devient seulement problématique si les collisions sont trop rapprochées et que le temps n'avance presque plus (voire pas du tout, à cause d'un manque de précision par exemple), et dans ce cas on peut soit sortir l'artillerie lourde et considérer qu'il faut faire une résolution collision simultanée bien lourdingue, soit simplement sauter un petit pas façon méthode discrète (sauf que le pas est bien plus petit, donc moins de problème de précision, et on fait ça moins souvent que si le pas était tout le temps tout petit), et surtout combiner avec un cutoff pour stopper les billes presques immobiles qui pourraient "vibrer" l'une contre l'autre et faire ramer sans rien produire.

A un détail près : des collisions peuvent disparaître suite à d'autres collisions... Par conséquent, il est toujours nécessaire de se retaper tous les calculs, et il est plutôt recommandé d'invalider systématiquement tous les calculs précédents pour éviter d'avoir à gérer des collisions fantômes

 
Je l'ai marqué dans la parenthèse sur le tas d'events, et il "suffit" de virer les events futurs de collisions de billes impliquées dans les collisions traitées, pas tout les events futurs (et comme au passage on sait que si y'a 2 events futurs sur une bille, le traitement du premier va écarter le second, sauf si le premier event est écarté par le traitement d'un event précédent sur l'autre bille, on peut se permettre de ne stocker dans le tas que le 1er event par bille, et donc alléger les tâches de recherche et de prune, pourvu que la réinclusion dans le set de billes à traiter suite à une collision soit viral même entre billes dont l'event de collision n'est pas premier sur ces billes, et calculer ce set viral c'est pas cher (et plus simple en code que le léger méli-mélo de ma phrase) ).

Ouais tu l'as marqué après édition

Bonjour,
Merci pour toutes ces réponses et cet échange vraiment intéressant !
 
Vu que je débute le projet, je n'ai pas encore beaucoup avancé dans les différentes façon de faire, mais je vais suivre votre conseil. Je vais partir de façon très simlpe avec un petit manager qui testera les collisions entre chaque billes pour débuter, je modifierais au fur et à mesure que les problématiques arriveront
 
Merci

 
Pas faux

Voila, j'ai fini d'implémenter mon système et a part les bugs que vous avez cités, ça fonctionne plutôt bien.
 
Le principal problème finalement, c'est que souvent (tout le temps même au bout d'un moment), mes billes forment des grappes et ne bougent plus. Comme vous l'avez dit, je dois tester mes collisions un brin trop tard. Il est possible également que les paramètres de mes billes ne soit pas adaptés. Une bille possède un vecteur direction (x, y) toujours à 1 ou -1 et une vitesse (= 100). Pour déplacer mes billes je fais ce calcul :
 

 
Ma boucle principale ressemble à ça :

 
Malheureusement, en relisant votre discussion, je ne sais pas vraiment sur quel système partir  

Tu parles juste des conditions initiales ou quand tu résouds les collisions tu fais un truc en sorte de garder cette contrainte ? Tu as quoi dans tes fonctions resolveCollision* ?

 
Oui, pour les collisions avec les bordures, j'inverse la direction qui va bien. C'est d'ailleurs peut-être pas la meilleure solution :
 

 
Et pour ce qui concerne la résolution des collisions entre mes billes, je parcours mes billes :
 

 
Et je calcul mes nouvelles directions. Pour l'instant j'ai bêtement recopié le calcul de cet article : http://fr.wikipedia.org/wiki/Choc_élastique
 

dans ton isInCollisionWith, tu vérifie que les balles s'intersectent seulement ou aussi qu'elles vont bien l'une vers l'autre ?

Si tu oublie la seconde condition, des billes qui s'intersectent mais qui sont entrain de se séparer l'une de l'autre, par exemple suite à un choc imparfaitement résolu à la frame d'avant, vont être considérées comme encore en collision, le faux choc va être résolu et va inverser leur direction, elles vont se foncer de nouveau l'une vers l'autre et augmenter leur intersection, il y aura une résolution qui va ensuite les écarter, mais pas assez pour qu'elles cessent de s'intersecter, et le truc va former une grappe petit à petit...

 
Exact, je n'avais pas pensé à ce cas de figure. Je vais ajouter comme condition (en plus de savoir si elles sont dans la zone), si les directions sont opposées, comme tu le suggère. Au passage, ma fonction IsInCollisionWith :
 

 
Au passage, si tu as un avis sur ma façon de coder, ou de structurer la chose, hésites pas, j'essai de progresser en cpp. Bon pour l'instant je suis me suis limité à un GameManger qui gère un peu tout, mais c'est pour passer plus de temps sur le système de collision.
 
Merci en tout cas.

Tu peux enlever le sqrt et compare la distance au carré de la somme des rayons, l'optimisation c'est pas prioritaire mais cette modification est ultra-courante (les sqrt c'est vachement lourd).

Niveau style, bah chacun ses gouts, mais les accesseurs pour x et y ainsi que les "this->" superflus ça alourdit vachement la lecture et dans tes grandes boucles, n'hésite pas à faire un const Ball ball = balls_.at(i) pour alléger. Et les commentaires qui disent exactement la même chose que le nom de la fonction ça sert à rien.

Si tu le sens, tu peux tenter de convertir ton code en remplaçant tout les x et y par une "struct point {float x, y; }" avec les opérateurs -, +, -=, +=, =, dotProduct(point b), crossProduct(point b), squaredLength() et length(). Ton code sera nettement plus court (finit les copier/coller de la même ligne pour x et y), et en bonus il suffira presque de rajouter z dans ta structure pour que le code marche aussi en 3D.

 
Merci pour les conseils !

 
const Ball &ball = balls_.at(i) plustôt ?

Pas forcément, si le compilo est stupide et que Ball est gros, copier un Ball entier pour n'en lire que des bouts serait effectivement une perte de temps, sauf que le compilo est pas complètement stupide dans ce cas, s'il utilise pas un membre de Ball, il ne le copiera pas dans la stack pour rien, il ne prendra que les bouts utiles, exactement comme quand tu fais un "const Ball&" et que quand tu lis un membre il le copie.
Par contre, si dans ton scope en cours tu as un Ball& ou un Ball* qui traine, que tu fais des écritures dessus, il est possible que ça invalide les données lues par ton const Ball& (peut-être que c'est pas vraiment possible, mais que le compilo arrive pas à le déduire), par exemple (un cas super-pathologique):

for (int i=1; i<balls_.size(); ++i) {
  Ball& foo = balls_.at(i);
  for (int j=0; j<i; ++j) {
    const Ball& bar = balls_.at(j);
    foo.x += bar.x;
    foo.x += bar.x;
  }
}

Imaginons que le compilo n'arrive pas à comprendre que puisque j est toujours inférieur à i, alors foo et bar ne peuvent pas pointer sur le même objet. alors le compilo est obligé de se dire que peut-être que quand on modifie foo, on modifie bar aussi, donc après le premier "foo.x += bar.x;" peut-être que bar.x a changé, donc qu'il faut aller le relire en mémoire pour faire le second +=. Si t'avais simplement eu un "Ball bar", il saurait que les données de bar sont inacessible via la référence foo et éviterait de recharger la valeur de bar.x une seconde fois. Et comme le compilo élimine les load inutile, il n'aurait copié que Ball.x dans la stack (sauf si le constructeur par copie de Ball est non-trivial).