détection des collisions entre des balles
macounette
Membre
rebonjour !
Toujours dans mon appli, j'ai réussi à afficher plusieurs balles en mouvement grâce à vous :
http://www.objective-cocoa.org/forum/index.php?topic=3361.0
Maintenant je me suis attaquée à la gestion des collisions. Alors attention j'ai réussi à faire quelque chose qui marche correctement. C'est pas encore parfait.
Petit résumé :
J'ai une BallView IUView qui lance un timer
Mes objets Ball :
Je me suis beaucoup appuyée sur cet algo :
http://home.hkstar.com/~yyf/game1.html
EDIT : Et de ça aussi http://www.phy.ntnu.edu.tw/ntnujava/index.php?topic=4.0
Bon pour 3 ou 4 balles ça marche plutôt bien.
Mais alors pour une dizaine de balle voire plus, c'est nul de chez nul ! C'est hyper saccadé : à peu près 2 rafraà®chissements de l'écran par seconde !!!
Donc bof bof ce que j'ai fais. Ca me sert pas à grand chose si pour plus de 10 balles ça ne marche plus
Snif j'étais plutôt contente de moi, mais vous m'aviez prévenu que ça allait pas être si simple !
Des idées ? Des suggestions ? Des pistes ?
Toujours dans mon appli, j'ai réussi à afficher plusieurs balles en mouvement grâce à vous :
http://www.objective-cocoa.org/forum/index.php?topic=3361.0
Maintenant je me suis attaquée à la gestion des collisions. Alors attention j'ai réussi à faire quelque chose qui marche correctement. C'est pas encore parfait.
Petit résumé :
J'ai une BallView IUView qui lance un timer
<br />@implementation BallView<br /><br />- (id)initWithFrame:(CGRect)frameRect {<br /><br /> ballArray = [[NSMutableArray alloc] initWithCapacity:ballNumber];<br /> for(int i=0; i<ballNumber; i++) {<br /> //ici j'ai une fonction qui crée des instances de Ball et qui les ajoute dans mon tableau<br /> }<br /><br /> timer = [NSTimer scheduledTimerWithTimeInterval:1.0 / 30.0 target:self selector:@selector(repaint) userInfo:nil repeats:YES];<br />}<br /><br />- (void)repaint {<br /> <br /> for(int i=0; i<ballNumber; i++) {<br /> Ball* ball = [ballArray objectAtIndex:i];<br /> [ball move]; // MAJ des coordonnées de balles<br /> [ball checkCollision:ballArray:ballNumber:i]; //je vérifie si j'ai des collisions<br /> }<br /> [self setNeedsDisplay];<br />}<br /><br />- (void)drawRect:(CGRect)rect {<br /> CGContextRef context = UIGraphicsGetCurrentContext();<br /> <br /> for(int i=0; i<ballNumber; i++) {<br /> Ball* ball = [ballArray objectAtIndex:i];<br /> [ball draw:context];<br /> }<br />}<br />
Mes objets Ball :
<br />@implementation Ball<br /><br />// met a jour la position du cercle à dessiner<br />- (void)move {<br /> velocity.y += gravity;<br /> position.x += velocity.x;<br /> position.y += velocity.y;<br /> <br /> if(position.x + radius> 320.0) {<br /> position.x = 320.0 - radius;<br /> velocity.x *= bounce;<br /> }<br /> else if(position.x - radius <0.0) {<br /> position.x = radius;<br /> velocity.x *= bounce;<br /> }<br /> <br /> if(position.y + radius> 460.0) {<br /> position.y = 460.0 - radius;<br /> velocity.y *= bounce;<br /> }<br /> else if(position.y - radius <0.0) {<br /> position.y = radius;<br /> velocity.y *= bounce;<br /> } <br />}<br /><br />-(void)checkCollision:(NSMutableArray*)ballArray:(int)ballNumber:(int)i {<br /> <br /> for (int j=i+1; j<ballNumber; j++) <br /> {<br /> Ball* ballj = [ballArray objectAtIndex:j]; //je récupère mes autres balles<br /> <br /> float dy = position.y - ballj.position.y;<br /> float dx = position.x - ballj.position.x;<br /> <br /> float r2 = 2*radius;<br /> <br /> if (((dy<r2)&&(dy>-r2))||((dx<r2)&&(dx>-r2)))<br /> {<br /> <br /> // distance^2 between ball i and ball j<br /> float d =dx*dx+dy*dy;<br /> <br /> // too close!<br /> if (d<(r2*r2))<br /> {<br /> // There is "real" collision only if they approach each other<br /> if (((velocity.x*dx+velocity.y*dy)-(ballj.velocity.x*dx+ballj.velocity.y*dy))<0)<br /> {<br /> <br /> float txj = (velocity.x*dx*dx + velocity.y*dx*dy + ballj.velocity.x*dy*dy - ballj.velocity.y*dx*dy)/d;<br /> float tyj = (velocity.x*dx*dy + velocity.y*dy*dy - ballj.velocity.x*dx*dy + ballj.velocity.y*dx*dx)/d;<br /> <br /> //je change la vélocité de ma balle courante<br /> velocity.x= (ballj.velocity.x*dx*dx + ballj.velocity.y*dx*dy + velocity.x*dy*dy - velocity.y*dx*dy)/d; <br /> velocity.y= (ballj.velocity.x*dx*dy + ballj.velocity.y*dy*dy - velocity.x*dx*dy + velocity.y*dx*dx)/d;<br /><br /> //et aussi celle de l'autre balle responsable de la collision<br /> [ballj velocity:txj:tyj];<br /> }<br /> }<br /> }<br /> }<br />}<br /><br />
Je me suis beaucoup appuyée sur cet algo :
http://home.hkstar.com/~yyf/game1.html
EDIT : Et de ça aussi http://www.phy.ntnu.edu.tw/ntnujava/index.php?topic=4.0
Bon pour 3 ou 4 balles ça marche plutôt bien.
Mais alors pour une dizaine de balle voire plus, c'est nul de chez nul ! C'est hyper saccadé : à peu près 2 rafraà®chissements de l'écran par seconde !!!
Donc bof bof ce que j'ai fais. Ca me sert pas à grand chose si pour plus de 10 balles ça ne marche plus
Snif j'étais plutôt contente de moi, mais vous m'aviez prévenu que ça allait pas être si simple !Des idées ? Des suggestions ? Des pistes ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
L'idée est donc :
1) de ne surtout pas comparer chaque balle avec chacune des autres balles pour tester leur collision, mais de commencer par éliminer rapidement les balles dont on est sûr qu'elles sont trop loin pour entrer en collision.
2) De faire une comparaison rapide pour les balles proches avant d'envisager une comparaison plus fine
Les diverses astuces auxquelles je pense sur le moment :
1) Fonctionner avec des entiers plutôt que des flottants (les calculs sur les entiers sont beaucoup plus rapides)
2) Découper le "plateau de jeu" en secteurs rectangulaires et garder d'un moyen ou d'un autre la liste des balles dans chaque secteur. Et comme ça tu peux ne tester que les collisions des balles dans le même "secteur" plutôt que toutes les balles du plateau. Bon il faut que les secteurs se superposent un peu pour les cas des balles à la limite entre 2 secteurs. Mais ça limite le nombre de tests.
On peut avoir le même principe aussi avec une organisation des balles en "graphe", mais c'est un peu plus compliqué à gérer. Alors que savoir dans quel secteur rectangulaire se trouve la balle peut être fait rapidement (par exemple un décalage de bits genre x>>5 pour diviser super rapidement x par 2^5 = 32 si tes secteurs rectangulaires font 32 de large). Rien que ça ça élimine très rapidement des balles à tester
3) Pour les balles qui n'ont pas été éliminées par l'algo précédent, faire un test rapide, genre rectangle englobant : récupérer le rectangle englobant des 2 balles à tester et vérifier si l'intersection de ces CGRects n'est pas nulle.
4) Si l'intersection est nulle, pas la peine d'aller plus loin les balles ne se choqueront pas. Si elles le sont, alors tu peux faire un test plus fin, c'est à dire là enfin vérifier que la distance entre les 2 centres des balles est inférieure à la somme de leurs rayons pour savoir si elles se touchent ou pas (et là tu peux faire le calcul en floats et pas int)
En tout cas ce qu'il ne faut pas faire c'est :
1) tester toutes les balles directement avec les distances, genre sqrt((x2-x1)^2+(y2-y1)^2)<(r1+r2) car ça nécessite deux différences entre des floats + deux mises au carré (multiplications) + un calcul de racine carré... ce qui est énorme comme utilisation CPU
2) Calculer la racine carré pour la distance! Il faut mieux tester que ((x2-x1)^2+(y2-y1)^2)<(r2-r1)^2 plutôt ! Beaucoup moins consommateur de ressources aussi.
Mais déjà imagine si tu as N balles et que tu testes chaque balle avec toutes les autres, ça fait N*(N-1) tests (en réalité normalement N*(N-1)/2 puisque si tu testes la collision entre A et B pas besoin de tester aussi la collision entre B et A)... mais vu comment les calculs entre les multiplications sont coûteuses...
Imagine, tester les collisions sur 10 balles ça fait 10*9/2 = 45 tests. Sur 7 balles ça fait 7*6/2 = 21, sur 4 balles ça fait 4*3/2 = 6 balles... comme quoi ça descent très vite ! Donc ça vaut énormément le coup de faire des tests éliminatoires rapides avant !
Ca me semble pas la mer à boire pour l'iPhone non?
Edit:Voici ce que je tire de mon iPhone avec le simu de particules -> Benchmark iPhone
Et surtout 45 calculs de sqrt((x2-x1)^2+(y2-y1)^2) contre 45 calculs de CGRectIntersect(rct1,rct2) la différence est pas mince surtout à chaque boucle de composition...
Au niveau de la boucle de collision, il me semble y avoir beaucoup de calculs redondants aussi. Je suis pas sûr que GCC optimise tout ça au mieux. Après vérifier aussi que le mode Thumb est désactivé car pour ce genre de calcul il est important de basculer en ARM.
J'ai édité mon poste entre temps. Regardes le liens que j'ai ajouté à ma réponse. Je monte à 20 img/s avec 384 particules sur mon simu en force brute.
On calcule mathématiquement précisément les trajectoires sur n secondes (analytiques... pour ce cas, ce sont des fonctions paramétriques affines par morceaux), puis pendant l'affichage, on calcule (dans un autre thread) les trajectoires pendant les secondes suivantes etc.
Suite à vos conseils, j'ai découpé ma vue principale BallView (mon plateau de jeu) en case.
J'ai créé un NSObject Case
Dans BallView mon timer appelle la méthode repaint :
Ouah ! vous avez vu le nombre de boucles que je fais pour y arriver ! Du coup même sans vérifier les collisions entre balles, mon animation sacade :-\\ Et j'ai que 2 balles dans mon test. C'est embêtant...
Je crois que je m'y suis pris comme un pied, mais je n'arrive pas à limiter mes boucles... Ca commencer à me rendre dingue cette histoire.
Et pour info dans mon checkCollision
Ta méthode est fausse.
Le membre cgRect.origin représente le coin inférieur gauche du rectangle.
Regarde la définition de CGRect pour plus d'infos.
La formule valide est donc
Note que ta méthode fonctionne tout de même (puisque l'erreur est la même pour toutes les balles).