Voici une fiche pratique qui résume les différentes collisions que vous pourrez utiliser dans un jeu. Cette partie du Wiki étant dédiée à Flash et Actionscript, nous allons travailler dans ce format, cependant les formules qui vont suivre sont valables quel que soit vos outils de programmation.

Les algorithmes sont connus et vous en trouverez de nombreuses représentations partout sur la toile, en particulier sur ce tutoriel du site du Zéro (lui même tiré d’autres tutos, eux même tirés de bouquins, eux-mêmes tirés de l’apprentissage d’autres personnes, etc….), il n’y a pas vraiment d’auteur d’origine, elles sont pratiquement toutes tirées de ce qu’on apprend à l’école en géométrie…

Je ne suis pas une brute en maths, c’est pourtant une discipline indispensable pour gérer convenablement des tests de collisions, j’ai donc eu du mal sur certaines formules et c’est pourquoi je me suis monté ces fiches de révision. Je n’entrerai pas forcément dans les détails, si vous souhaitez étudier le développement des formules de base Wikipedia ou un bouquin de maths seront vos meilleurs amis, on va se contenter de passer en revue les formules utile et une petite implémentation de chacune en AS3.

Vous trouverez également énormément d’infos, d’explications et d’astuces complémentaires sur ces liens, dont sont tirées la plupart des formules utilisées dans cette fiche :

http://www.siteduzero.com/informatique/tutoriels/theorie-des-collisions
http://tonypa.nicoptere.net/

Tout le monde sait ce qu’est une collision, selon Wikipédia, une collision est un choc entre deux objets, elle peut être élastique ou inélastique. Mais dans le monde réel les objets ont une forme, une masse, ils sont régis par des lois physiques complexes, et ce qui peut paraître évident même à un enfant de 2 ans (boum, ça fait mal = collision), ne l’est pas forcément quand on travaille avec des objets virtuels qui par définition n’existent pas dans le monde réel.

Alors comment déterminer un choc entre deux objets en programmation ?
Pour bien faire il nous faut affiner un peu la définition en disant que :
Il y collision entre deux objets lorsque au moins un point de l’objet A est en contact avec la surface de l’objet B.

Ok on y est, il y a “point” et “surface”, de la géométrie……. c’est des maths !

Fort heureusement, ou pas, il n’existe pas qu’une méthode universelle pour tester une collision, mais différentes techniques plus ou moins simples et adaptées selon les situations, et nous allons commencer par … mettre les pieds dans le plat et tomber dans le piège vicieux qu’a tendu ce vil Flash à tous les débutants…

x = coordonnée de départ sur l’axe x
y = coordonnée de départ sur l’axe y
width = largeur de la box
heigth = hauteur de la box

Avec ces quelques coordonnées on peut donc définir la surface de la box et la zone qu’elle occupe dans le plan. Lorsque la BB est alignée avec les axes du plan dans lequel vous travaillez (la scène par exemple pour Flash), elle est dite “Axis Aligned” autrement dit “aligné avec les axes”, et elle est donc très facile à définir, comme nous venons de le voir, car elle ne nécessite aucun calcul mathématique supplémentaire. C’est le type de Bounding Box le plus courant que vous serez amenés à utiliser dans vos jeux et il s’agit tout simplement d’un rectangle. Les deux classes de bases qui seront les plus utiles pour les calculs de collision en Actionscript sont Rectangle et Point.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/aabb_vs_point.swf » width=480 height=480]

Pour vérifier si un point se trouve à l’intérieur d’une Bounding Box classique (nommée ci-après “B”) on peut utiliser la formule suivante :

function collisionPointAABB(X, Y, B){
	if (X>=B.x && X<B.x+B.width && Y>=B.y && Y<B.y+B.height) return true;
	return false;
}

On s’assure alors que la AABB est en contact avec le point spécifié en vérifiant si le point ( X,Y ) touche la surface de la box ( B ), c’est sommairement ce que fait “hitTestPoint” en AS3. Dans l’exemple donné ci-dessus je regarde simplement si la souris se trouve dans la AABB en me servant de ses coordonnées dans le plan, ce type de collision est utilisé dans certains jeux mais aussi pour les menus par exemple, elle peut donc servir aussi pour l’interactivité de vos interfaces.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/aabb_vs_aabb.swf » width=480 height=480]

Pour tester la collision entre deux objets on teste la collision entre deux rectangles dont les axes sont alignés (AABB). Ce genre de détection est utilisée dans énormément de jeux de tous types, des jeux de plateformes aux Shoot’em Up en passant par la plupart des jeux à base de tuiles. Elle doit être rapide car le nombre d’objets à tester est souvent assez important, imaginez un shoot’em up plein d’ennemis où ça tire de partout. Et pour être rapide il faut simplifier et limiter les calculs, c’est là que réside toute l’astuce, c’est pourquoi on ne va pas chercher à tester la position de tous les points des surfaces occupées par les deux box, mais simplement voir si une box est totalement en dehors d’une autre. techniquement cela s’exprime ainsi :

Si la box 1 est complètement à gauche
ou complètement en haut
ou complètement à droite
ou complètement en bas de la box 2, alors elle ne touche pas.
Sinon, elle touche.

Ca tombe bien, nous venons de voir comment gérer la collision entre une box et une ligne, c’est pratiquement la même chose ici sauf qu’on regarde si il n’y a pas collision. Voyons ça avec deux box que je vais nommer A et B pour rendre la formule plus lisible :

function collisionBoxBox(A,B){
	if (A.y+A.height < B.y || A.y > B.y+B.height || A.x > B.x+B.width || A.x+A.width < B.x) return false;
	return true;
}

Notez qu’une simple ligne droite (AA) peut-être considérée comme un rectangle ayant une largeur ou une hauteur minimale, cette formule marche donc également avec les lignes.

Bien souvent cette solution est également utilisée en prémices à des collisions plus précises car elle demande moins de calculs et peut donc être utilisée avant de tenter une collision fine, on regarde d’abord grossièrement si les objets sont en contact, puis on affine pour savoir exactement où se trouve le ou les points de contact, nous verrons cela par la suite.

Avant de nous occuper de collisions plus détaillées, voyons quelques mises en applications avec des grilles et des tuiles. La plupart des jeux utilisent ce système pour gérer les interactions entre le joueur et le monde qui l’entoure, cela demande de nombreux tests de collisions, d’où ces quelques exemples simples mais bien pratiques.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/aabb_vs_grille_fermee.swf » width=480 height=480]

L’univers dans lequel évolue le joueur est une grille composée de cases, certaines sont solides, d’autres non. La box du joueur est un rectangle et il nous faut donc tester sa collision avec les cases solides que l’on peut également considérer comme des box. On va commencer par définir le monde, dessiner la grille, placer le joueur et créer le code de gestion des touches pour le déplacement (voir source pour plus de détail).

Note sur l’optimisation : une grille est généralement représentée par un tableau à deux dimensions, une liste qui pour chaque ligne contient une liste des cases. C’est très lourd, une solution intermédiaire consiste à utiliser une liste simple et une petite formule pour passer à la ligne suivante, c’est celle que j’utilise pour l’exemple, mais il existe d’autres solution pour gérer des maps, notamment les Bitmaps ou les entier de 32 bits, mais on s’éloigne un peu du sujet sur les collisions et on reparlera de ces optimisations plus tard, donc revenons à nos moutons, les collisions.

function collisionsGrilleAABB(dX,dY,B){
 
	var C;
	var L;
 
	B.x += dX*vitesse;
	if (dX<0) {
		C = B.x/taille ;
		for (L = B.y/taille; L<(B.y+B.height)/taille; L++) {
			if (map[C+L*colonnes]==1) B.x = (C+1)*taille;
		}
	} else if (dX>0) {
		C = (B.x+B.width)/taille ;
		for (L = B.y/taille; L<(B.y+B.height)/taille ; L++ ) {
			if (map[C+L*colonnes]==1) B.x = C*taille-B.width;
		}
	}
 
	B.y += dY*vitesse;
	if (dY<0) {
		L = B.y/taille;
		for (C=B.x/taille; C<(B.x+B.width)/taille; C++) {
			if (map[C+L*colonnes]==1) B.y = (L+1)*taille;
		}
	} else if (dY>0) {
		L = (B.y+B.height)/taille ;
		for (C=B.x/taille; C<(B.x+B.width)/taille; C++) {
			if (map[C+L*colonnes]==1) B.y = L*taille-B.height;
		}
	}		
 
	return {x:B.x, y:B.y};
}

Cette formule semble longue et complexe mais il n’en est rien, en fait ici notre joueur est plus grand que la taille d’une tuile de la map, du coup il faut tester chaque case qu’occupe la box du joueur pour déterminer la collision, c’est à ça que servent les boucles.

On utilise la direction prise par le joueur (dX et dY) pour savoir quel côté de la box doit effectuer le test de collision, puis on regarde la case où elle se trouve et si c’est un mur infranchissable on replace le joueur devant le mur.

Précisons enfin que chaque calcul doit être fait indépendamment sur chaque axe, d’abord X puis Y (ou l’inverse) mais jamais les deux en même temps, c’est à la fois une question d’optimisation et de précision.

La fonction renvoie un point, il représente les coordonnées que doit avoir le joueur à la fin des tests de collision.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/aabb_vs_pente.swf » width=480 height=480]

Nous avons vus au début de ce document comment gérer la collision avec une ligne droite (deux AABB), mais le joueur évolue alors dans un monde tout en angles droits, quelques pentes pourraient bien agrémenter un peu le décor et le gameplay, cette fois nous allons donc tester la collision avec une pente et pour cela nous allons utiliser des fonction affines (voir : http://fr.wikipedia.org/wiki/Fonction_affine ).

function collisionPenteAABB(B){
 
	var X = B.x+B.width*.5;
	var Y = B.y+B.height;
 
	var PY;
	var oldPY;
	var p1;
	var p2;
 
	for each (var ligne in lignes) { 
		p1 = ligne.p1;
		p2 = ligne.p2;
		if ( X >= p1.x && X <= p2.x ) {
			PY = p1.y+(X-p1.x)*(p2.y-p1.y)/(p2.x-p1.x); 
			oldPY = p1.y+(oldX-p1.x)*(p2.y-p1.y)/(p2.x-p1.x); 
			if ( Y >= PY && oldY <= oldPY ) B.y = PY-B.height;
		}
	}
 
 	oldY = B.y+B.height;
	oldX = X;
 
	return {x:B.x, y:B.y};
}

On déplace d’abord le joueur, puis on regarde où se trouvent ses pieds, on replace ensuite le joueur sur Y en fonction de la pente de la ligne. Afin de simplifier les calculs on ne va pas partir du repère du plan (la scène) mais d’un repère local à la pente, son point gauche. La fonction renvoie un nouveau point de coordonnées qui est la correction de la position en fonction de la pente. Notez que “oldX” et “oldY” sont deux variables externes à la fonction car nous devons les conserver à chaque pas du programme, et que toutes les lignes sont stockées dans un tableau sous forme de points (deux points par ligne).

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/droite_vs_segment.swf » width=480 height=480]

La différence entre une droite et un segment de droite, c’est que la droite n’est pas considérée comme finie, alors que le segment possède un début et une fin clairement identifiés. Nous allons donc commencer par tester la collision entre une droite et un segment de droite.

function collisionDroiteSegment(a,b,c,d){
	var AB = {x:b.x-a.x,y:b.y-a.y};	// vecteur AB
	var AD = {x:d.x-a.x,y:d.y-a.y};	// vecteur AD
	var AC = {x:c.x-a.x,y:c.y-a.y};	// vecteur AC
	if ((AB.x*AD.y - AB.y*AD.x)*(AB.x*AC.y - AB.y*AC.x)<0) return true;
	return false;
}

Ici on considère les points a,b,c,d où “a” et “b” forment une droite et “c” et “d” forment un segment de droite. Nous allons calculer les vecteurs de chacun et un vecteur peut être représenté par un simple point.

Par exemple pour calculer le vecteur de la droite formée entre les points “a” et “b” nous avons la formule suivante :

AB = (b.x-a.x, b.y-a.y)

Dans cette formule on calcule trois vecteurs, AB, AD, AC.
On considère que A est le point de départ du vecteur et qu’il se dirige vers B

On souhaite savoir si les points C et D du segment sont tous deux du même côté de la droite, auquel cas il n’y a pas de collision, en effet il ne peut y avoir collision que si C et D sont chacun d’un côté de la droite AB.

Les vecteurs AC et AD partent du point A et se dirigent vers le point du segment qui nous intéresse, on va donc obtenir un chiffre négatif si le vecteur monte et positif si il descend. Il est ainsi possible de déterminer si les deux vecteurs sont tous deux positifs ou négatifs (auquel cas les points C et D sont du même côté de la droite) ou de signe différents. A l’aide d’une simple multiplication on s’évite de tester un à un chaque point du segment.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/segment_vs_segment.swf » width=480 height=480]

Nous venons de voir comment tester la collision entre une droite et un segment de droite, intéressons nous à présent à deux segments et essayons de trouver le point de collision.

function collisionDroiteSegment(a,b,c,d){
	var AB = {x:b.x-a.x,y:b.y-a.y};	// vecteur AB
	var AD = {x:d.x-a.x,y:d.y-a.y};	// vecteur AD
	var AC = {x:c.x-a.x,y:c.y-a.y};	// vecteur AC
	if ((AB.x*AD.y - AB.y*AD.x)*(AB.x*AC.y - AB.y*AC.x)<0) return true;
	return false;
}
 
function collisionSegmentSegment(a,b,c,d){
	if (!collisionDroiteSegment(a,b,c,d)) return false;
	if (!collisionDroiteSegment(c,d,a,b)) return false;
	return true;
}

Trouver la collision entre deux segment n’est pas plus compliqué qu’entre une droite et un segment, il suffit en fait de faire deux fois le test avec des points différents en considérant à chaque test que l’un des deux segments est une droite.

Ce qui va donc nous intéresser ici c’est trouver le point d’intersection, ceci pouvant servir dans un jeu à déterminer l’angle d’un rebond ou tout simplement le point d’impact d’un projectile ou d’un rayon (dans le cas d’un raycasting).

function pointIntersection(a,b,c,d){
	var AB = {x:b.x-a.x,y:b.y-a.y};	// vecteur AB
	var AD = {x:d.x-c.x,y:d.y-c.y};	// vecteur AD
	var AC = {x:c.x-a.x,y:c.y-a.y};	// vacteur AC
	var t = (AC.x*AD.y-AC.y*AD.x)/(AB.x*AD.y-AB.y*AD.x);
	return {x:a.x+AB.x*t,y:a.y+AB.y*t}
}

Comme je le disait en introduction, j’ai mes limites en maths, et même si je comprend les formules, si je sent qu’il y a un risque de me tromper dans les explications, je préfère ne pas m’y lancer et vous renvoyer vers une source qui l’explique mieux que moi 😉 Donc si vous souhaitez en savoir plus sur la formule qui permet de trouver ce point d’intersection jetez un oeil ici : http://geomalgorithms.com/a05-_intersect-1.html

Ces collisions entre des lignes et des segments nous à permis d’introduire rapidement la notion de vecteurs, sans non plus entrer trop dans le détail, c’est important car par la suite nous allons énormément les utiliser pour simplifier tout un tas de calculs de collision.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/point_vs_polygone.swf » width=480 height=480]

Pour le cas d’un polygone on va considérer la forme du polygone comme un ensemble de points contenus dans un tableau. Pour déterminer si le point se trouve dans le polygone on va prendre un autre point très éloigné en dehors de la scène et tracer un segment entre ce point et le point sur lequel on fait la détection de collision. On va ensuite utiliser une simple détection d’intersection entre deux segments. Puis on va compter le nombre d’intersections entre le segment et le polygone, si ce nombre est impair alors le point est dans le polygone, si il est pair alors le point est en dehors du polygone.

function collisionPolygone(tab,nbp,P){
	var i;
	var I = {x:10000+Math.floor(Math.random()*100),y:10000+Math.floor(Math.random()*100)};
	var nbintersections = 0;
	for(i=0;i<nbp;i++){
		var A = tab[i];
		var B;
		i==nbp-1 ? B = tab[0] : B = tab[i+1];	// si c'est le dernier point, on relie au premier sinon on relie au suivant
		var iseg = intersectSegment(A,B,I,P);
		if (iseg == -1) return collisionPolygone(tab,nbp,P);  // cas limite, on relance la fonction.
		nbintersections+=iseg;
	}
	if (nbintersections%2==1) return true; // nbintersections est-il impair ?
	return false;
}
 
function intersectSegment(A,B,I,P) {
	var AB = {x:B.x-A.x,y:B.y-A.y};
	var IP = {x:P.x-I.x,y:P.y-I.y};
	var denom = AB.x*IP.y-AB.y*IP.x;
	if (denom==0) return -1;   // erreur, cas limite
	var t = - (A.x*IP.y-I.x*IP.y-IP.x*A.y+IP.x*I.y) / denom;
	if (t<0 || t>=1) return 0;
	var u = - (-AB.x*A.y+AB.x*I.y+AB.y*A.x-AB.y*I.x) / denom;
	if (u<0 || u>=1) return 0;
	return 1;
}

Il existe des cas particulier par exemple pour le point de départ et le point d’arrivé de la forme du polygone, qui sont les mêmes, dans ce cas on exclu un des deux points de la détection.

Le point aléatoire est également susceptible de poser des problèmes, le segment entre les deux points peut dans certains cas se retrouver parallèle et strictement sur une ligne du polygone, dans ce cas il faut signaler l’exception et retirer un autre point, puis recommencer la détection.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/cercle_vs_point.swf » width=480 height=480]

Pour savoir si un point se trouve dans un cercle il suffit de calculer la distance qui sépare le point au centre du cercle, si elle est inférieure ou égale au rayon alors le point touche le cercle.

Une distance entre deux points “a” et “b” se calcule normalement de la manière suivante :

distance = racine carré de ((b.x-a.x)*(b.x-a.x) + (b.y-a.y)* (b.y-a.y))

Mais les calculs de racine carrées sont très lourds, c’est pourquoi on va essayer de l’éviter. Tout ce que nous souhaitons savoir pour ce type de collision c’est si le point est plus proche du centre du cercle que la longueur du rayon, si on prend la distance au carré entre le point et le centre du cercle et le rayon au carré, on saura tout autant si l’une est inférieure à l’autre qu’avec la racine carrée, on peut donc se passer de la racine et calculer directement les carrés des deux longueurs, ce qui nous donne :

function collisionCerclePoint(X,Y,C){
	var cX = C.x+C.rayon;
	var cY = C.y+C.rayon;
	var distance = (X-cX)*(X-cX) + (Y-cY)*(Y-cY);
   	if (distance<C.rayon*C.rayon) return true;
	return false;
}

La fonction renvoie un booléen si le point touche le cercle. Attention, vous noterez que c’est le centre du cercle que l’on souhaite tester, or il se trouve que les objets ont en général leur point de repère de position dans le coin supérieur gauche. Pour trouver le centre du cercle (cX, cY) il faut donc ajouter le rayon de celui-ci à la fois à la hauteur et à la largeur du point de repère de position. Il en sera de même pour tous les tests sur les cercles que nous allons effectuer.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/cercle_vs_cercle.swf » width=480 height=480]

Là encore c’est assez simple, il suffit de regarder la distance qui sépare les centres des cercles et de vérifier si elle est inférieure à la somme des rayons, et cela marche avec des cercles de n’importe quelle taille.

function collisionCercleCercle(A,B){
 
	var AX = A.x+A.rayon;
	var AY = A.y+A.rayon;
	var BX = B.x+B.rayon;
	var BY = B.y+B.rayon;
 
	var distance = (AX-BX)*(AX-BX) + (AY-BY)*(AY-BY);
   	if (distance < (A.rayon+B.rayon)*(A.rayon+B.rayon)) return true;
	return false;
}

Les jeux qui utilisent le plus ce type de collision sont les jeux de billard par exemple.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/cercle_vs_ligne.swf » width=480 height=480]

Pour calculer la collision entre un cercle et une droite il faut projeter un point sur la droite de manière à ce que le segment représenté par le point projeté et le centre du cercle forme un angle droit avec la droite, puis calculer la longueur du segment ainsi trouvé pour savoir si elle est plus petite que le rayon du cercle, auquel cas il y a collision.

Nous ne connaissons pas encore le point projeté sur la droite à partir du centre du cercle, mais nous connaissons la position du centre du cercle (C), et au moins un point de la droite (A). Nous savons également que le segment entre le centre du cercle et le point projeté (B) doit faire un angle droit avec la droite. Tout ceci forme un triangle rectangle, on se tourne donc vers Pythagore, ce qui nous donne avec des vecteurs :

function collisionCercleDroite(a,b,c){
 
	var cX = c.x+c.rayon;
	var cY = c.y+c.rayon;
 
	var AB =  		{x:b.x-a.x, y:b.y-a.y}; 		// Vecteur AB
	var AC = 		{x:cX-A.x, y:cY-a.y};			// Vecteur AC
	var numerateur = 	Math.abs(AB.x*AC.y-AB.y*AC.x);   	// numerateur
	var denominateur = 	Math.sqrt(AB.x*AB.x + AB.y*AB.y);  	// denominateur
 
	if (numerateur/denominateur<c.rayon) return true;
	return false;
}

Pour en savoir plus sur le théorème de Pythagore : http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Pythagore

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/cercle_vs_segment.swf » width=480 height=480]

A partir d’ici ça se complique un peu car il va nous falloir faire des produits scalaire, pas de panique on va survoler ça, mais avant de nous jeter dans les calculs on va se simplifier un peu la vie. Il y a tout un tas de collisions simples que nous pouvons tester avant de plonger dans des calculs complexes, en effet on peut déjà vérifier que le cercle ne touche pas la droite, si c’est le cas il ne touchera pas le segment, ensuite on peut vérifier si le cercle touche un des deux points du segment, auquel cas la solution est simple,. On va donc utiliser deux méthodes que nous avons déjà vues, la collision avec un point et avec une droite, si ces deux conditions ne sont pas remplies on passe aux calculs.

function collisionCercleSegment(a,b,c){
  	if (!collisionCercleDroite(a,b,c)) 	return false;  	// ne touche pas la droite
	if (collisionCerclePoint(a,c)) 		return true;	// A dans le cercle
	if (collisionCerclePoint(b,c)) 		return true; 	// B dans le cercle
	var cX = c.x+c.rayon;
	var cY = c.y+c.rayon;
	var AB = {x:b.x-a.x,y:b.y-a.y}; 			// Vecteur AB
	var AC = {x:cX-a.x,y:cY-a.y}; 				// Vecteur AC
	var BC = {x:cX-b.x,y:cY-b.y}; 				// Vecteur BC
	var S1 = AB.x*AC.x + AB.y*AC.y;  			// produit scalaire AB AC
	var S2 = -AB.x*BC.x - AB.y*BC.y;  			// produit scalaire AB BC
	if (S1>=0 && S2>=0)			return true;  	// entre A et B
	return false;
}
 
function collisionCercleDroite(a,b,c){
	var cX = c.x+c.rayon;
	var cY = c.y+c.rayon;
	var AB = {x:b.x-a.x, y:b.y-a.y}; 			// vecteur AB
	var AC = {x:cX-a.x, y:cY-a.y};				// vecteur AC
	var numerateur = Math.abs(AB.x*AC.y-AB.y*AC.x);   	// numerateur
	var denominateur = Math.sqrt(AB.x*AB.x + AB.y*AB.y);  	// denominateur
	if (numerateur/denominateur<c.rayon) return true;
	return false;
}
 
function collisionCerclePoint(p,c){
	var cX = c.x+c.rayon;
	var cY = c.y+c.rayon;
	var distance = (p.x-cX)*(p.x-cX) + (p.y-cY)*(p.y-cY);
   	if (distance<c.rayon*c.rayon) return true;
	return false;
}

Le produit scalaire c’est quoi ?

Un petit tour par Wikipedia vous donnera une définition exacte : http://fr.wikipedia.org/wiki/Produit_scalaire

Notre objectif pour savoir si il y a une collision entre le cercle et le segment, est de savoir si le point projeté (du centre du cercle sur le segment, via le rayon) se trouve bien entre les bornes du segment, à savoir ici A et B. Pour cela on a besoin de deux produits scalaires, un entre AB et AC, où AC est le vecteur entre le point A et le centre du cercle, et un entre BA et BC, B étant le second point du segment. Si ces deux produits scalaires nous renvoient une valeur strictement supérieure à zéro, alors le point projeté est bien sur le segment.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/cercle_vs_segment_-_point_d_impact.swf » width=480 height=480]

Essayons à présent de trouver le point d’impact entre le cercle et le segment, pour cela on va utiliser une projection du centre du cercle sur le segment, comme ceci :

function pointImpact(a,b,c){
	var cX = c.x+c.rayon;
	var cY = c.y+c.rayon;
	var AB = {x:b.x-a.x,y:b.y-a.y}; 	// vecteur AB
	var AC = {x:cX-a.x,y:cY-a.y}; 		// vecteur AC
	var t = (AC.x*AB.x+AC.y*AB.y)/(AB.x*AB.x + AB.y*AB.y);	
	return new Point(a.x+AB.x*t,a.y+AB.y*t);
}

Vous noterez que le point d’impact est calé sur le centre du cercle. Dans mon exemple lorsque la collision à lieu sur un des bords du segment, le point de projection sur le segment est toujours au centre du cercle et non sur le bord du segment. C’est une réaction normale puisque nous ne prenons pas en compte le rayon du cercle dans nos calculs mais son centre.

[swf src= »http://www.cmarzin.fr/site/content/tutos/collisions/cercle_vs_aabb.swf » width=480 height=480]

Et nous attaquons la méthode la plus complète concernant ces formes simples (dites primitives) que sont les lignes, les segments, les rectangles et les cercles. Ici il s’agit de tester la collision entre un cercle et une AABB, et comme nous l’avons fait plus haut pour le cercle et le segment, nous allons utiliser ici presque toutes les méthodes de collisions appliquées à un cercle que nous avons vues.

function collisionCercleAABB(C,B){
 
   var B1 = new Rectangle(C.x, C.y, C.width, C.height);
   var B2 = new Rectangle(B.x, B.y, B.width, B.height);
 
   if (!collisionBoxBox(B1,B2)) return false; 
 
   if (collisionCerclePoint(B2.x,B2.y,C)
    || collisionCerclePoint(B2.x,B2.y+B2.height,C)
    || collisionCerclePoint(B2.x+B2.width,B2.y,C)
    || collisionCerclePoint(B2.x+B2.width,B2.y+B2.height,C))
   return true;  
 
   if (collisionPointAABB(C.x+C.rayon,C.y+C.rayon,B2)) return true;   
 
   var PV = projectionSurSegment(B1.x+C.rayon,B1.y+C.rayon,B2.x,B2.y,B2.x,B2.y+B2.height);
   var PH = projectionSurSegment(B1.x+C.rayon,B1.y+C.rayon,B2.x,B2.y,B2.x+B2.width,B2.y);
   if (PV || PH) return true; 
   return false; 
}
 
function projectionSurSegment(Cx,Cy,Ax,Ay,Bx,By){
   var ACx = Cx-Ax;
   var ACy = Cy-Ay;
   var ABx = Bx-Ax;
   var ABy = By-Ay;
   var BCx = Cx-Bx;
   var BCy = Cy-By;
   var s1 = (ACx*ABx) + (ACy*ABy);
   var s2 = (BCx*ABx) + (BCy*ABy);
   if (s1*s2>0) return false;
   return true;
}

Dans l’ordre on commence par un premier test qui vérifie si les Bounding Box de la AABB et du Cercle ne sont pas en contact, auquel cas inutile d’aller plus loin, il n’y a pas de collision.

Puis on vérifie si un des 4 coins de la AABB est en contact avec le cercle, si c’est le cas il y a collision.

On vérifie ensuite si le centre du cercle est en contact avec la AABB, si c’est le cas il y a collision.

Nous utilisons bien sur pour cela les méthodes déjà vues précédemment à savoir :

function collisionBoxBox(A,B){
	if (A.y+A.height < B.y || A.y > B.y+B.height || A.x > B.x+B.width || A.x+A.width < B.x) return false;
	return true;
}
 
function collisionCerclePoint(X,Y,C){
	var cX = C.x+C.rayon;
	var cY = C.y+C.rayon;
	var distance = (X-cX)*(X-cX) + (Y-cY)*(Y-cY);
   	if (distance<C.rayon*C.rayon) return true;
	return false;
}
 
function collisionPointAABB(X, Y,B){
	if (X>=B.x && X<B.x+B.width && Y>=B.y && Y<B.y+B.height) return true;
	return false;
}

Si aucun de ces tests n’a stoppé la détection il va falloir vérifier un peu plus finement si il y a contact, pour cela on va une nouvelle fois utiliser un produit scalaire, comme nous l’avons vus dans la collision entre un cercle et un segment, afin de déterminer si le point projeté sur un segment de la AABB se trouve à l’intérieur de ce segment. A partir de là vous pouvez déterminer précisément le point d’impact et gérer par exemple les rebonds comme nous l’avons vus avec la collision de cercle sur segment.