Cet article a pour but de vous présenter quelques idées et méthodes qui peuvent être utilisées pour gérer la détection de collision dans un jeu Flash. Il sera donc plus question de méthodologie que de code pur et dur.

Et hitTest() alors ?

La détection de collision est l’un des plus importants aspects d’un jeu d’action et c’est, hélas, généralement le point faible des jeux Flash. Une des raisons de cette limitation est l’utilisation quasi systématique de la fonction standard hitTest() qui reste très limitée : elle ne fonctionne qu’avec des points ou des rectangles dont les axes sont alignés et ne fournit qu’une réponse booléenne.

Il est bien évidemment possible de passer outre ces limitations en utilisant des astuces, par exemple en parsemant le contour de notre objet de multiples points qui serviront à faire autant de tests de collision. Mais ces astuces sont lentes et n’apportent finalement que peu d’informations sur la collision, or pour obtenir une réponse crédible à la collision, il faut des informations précises, c’est alors qu’entrent en jeu la physique et les maths.

Domaine de l’article

La détection de collision est un vaste sujet qui pourrait noircir des pages et des pages d’équations et de méthodes, c’est pourquoi je ne présenterai ici que quelques notions adaptées à Flash en nous limitant à des formes rigides et convexes (sachant qu’une forme concave peut se décomposer en plusieurs formes convexes). Un polygone est convexe lorsqu’il n’a pas d’angle rentrant ou de partie rentrante, Tous les angles intérieurs mesurent moins de 180 degrés.

Polygones : convexe et concave

Quand il y a n objets distincts sur le scène, les tests doivent se faire entre O(n²) différentes paires d’objets, c’est-à-dire que si nous avons 10 objets, il faudra faire 10×10 = 100 tests. Les systèmes de détection de collision les plus efficaces utilisent une approche en deux phases pour réduire le coût de ces tests :

• La recherche de proximité (broad phase) permet d’éliminer la plupart des paires en utilisant un simple test sur les enveloppes rectangulaires (bounding boxes), les enveloppes circulaires, les octrees ou les BSP. Les paires qui survivent à cette sélection passent alors à la phase suivante.
• Le test de collision de proximité (narrow phase) utilise alors un algorithme plus fin pour contrôler les collisions ou calculer les distances.

Etant donné que la recherche de proximité agit comme un filtre pour la collision, les choix des algorithmes pour ces deux phases peuvent être fait indépendamment.

Pour des lectures plus avancées sur la détection de collision, je vous renvoie à la bibliographie en fin d’article.

Prérequis : les vecteurs

Les seules notions de mathématiques dont nous aurons besoin sont les bases de l’algèbre et de la géométrie des vecteurs. En effet, l’étude des mouvements et des collisions impliquent un certain nombre de quantités (force, vitesse, masse, etc…) qui peuvent être séparées en deux groupes : les scalaires et les vecteurs. Un scalaire étant seulement un nombre (une quantité qui a une magnitude mais pas de direction) il vous reste peut être seulement à vous rafraîchir la mémoire avec les vecteurs.

Le vecteur

Un vecteur n’est finalement qu’un scalaire auquel on donne une direction, on peut se le représenter comme une flèche dont l’emplacement dans le plan n’a pas d’importance, seuls comptent sa longueur, sa direction et son sens.

Un vecteur est donc la différence entre deux points :

• point0 = (x0, y0)
• point1 = (x1, y1)
• vecteur du point0 au point1 = (v.x, v.y) = (x0 – x1, y0 – y1)

Vecteur

La normalisation

Normaliser un vecteur consiste tout simplement à le redimensionner de telle manière que sa longueur soit égale à 1. Les vecteurs unitaires sont utiles pour beaucoup de choses, comme représenter une direction (sans notion de force). Pour normaliser un vecteur v, il suffit de diviser chacune de ses composantes par la longueur de v :

• vecteur v0 = (v.x, v.y)
• long = longueur du vecteur v0
• vecteur unitaire parallèle au vecteur v0 = (v.x / long, v.y / long)

longueur_v = Math.sqrt(v.x * vx + v.y * v.y);
v.x /= longueur_v;
v.y /= longueur_v;

Notez qu’il faudrait ajouter un test pour garantir que v n’est pas un vecteur nul (0 de longueur), sinon attention à la division par 0.

Normalisation

La normale

Un vecteur normal (à ne pas confondre avec un vecteur normalisé !) est un vecteur perpendiculaire à un autre et de même longueur. Pour chaque vecteur, il existe deux vecteurs normaux : perpendiculaire à droite ou perpendiculaire à gauche. Les coordonnées de ces vecteurs sont très simples à obtenir :

• vecteur v0 = (v.x, v.y)
• vecteur normal à droite : v0d = (-v.y, v.x)
• vecteur normal à gauche: v0g = -v0d = (v.y, -v.x)

Vecteurs normaux

Le produit scalaire

Le produit scalaire de deux vecteurs v0 et v1 peut être considéré comme la mesure des directions relatives de ces deux vecteurs :

• vecteur v0 = (v0.x, v0.y)
• vecteur v1 = (v1.x, v1.y)
• produit scalaire de v0 et v1 = v0.x * v1.x + v0.y * v1.y

Les propriétés du produit scalaire (noté ps) sont les suivantes :

• quand deux vecteurs pointent dans la même direction, leur ps a sa valeur maximale
• quand ils pointent dans des directions opposées, leur ps est à son minimum (négatif)
• quand ils sont perpendiculaires leur ps est nul

Etant donné que la valeur du produit scalaire est déterminée par la longueur des deux vecteurs, seul le signe (positif ou négatif) est directement utile sans manipulation supplémentaire. Par contre, si le vecteur v0 est unitaire, le produit scalaire représente la longueur du vecteur v1 quand il est « mesuré le long » de la direction du vecteur v0.

Produit scalaire sur vecteur unitaire

La projection

La projection n’est finalement qu’une étape de multiplication ajoutée au produit scalaire. En effet, nous avons vu que lorsque le vecteur v0 est unitaire et que v1 ne l’est pas, le produit scalaire donne la longueur de « l’image » de v1 le long de v0. Pour obtenir la projection, il suffit donc de multiplier v0 (de longueur 1) par le produit scalaire, le vecteur résultant est nommé : projection du vecteur v1 sur v0.

Projection

Et voici donc le coeur de la méthode de l’axe séparateur que nous verrons plus loin : la projection sur un axe arbitraire. C’est comme ceci que nous projetterons nos formes sur tous les axes séparateurs potentiels :

• vecteur v0 = (v0.x, v0.y)
• vecteur v1 = (v1.x, v1.y)
• vecteur unitaire de v1 : v1u = (v1u.x, v1u.y)
• produit scalaire de v0 et v1u : ps
• projection de v0 sur v1 : p = (v1u.x * ps, v1u.y * ps)

//Calcul du vecteur unitaire
longueur_v1 = Math.sqrt(v1.x * v1.x + v1.y * v1.y);
v1u.x = v1.x / longueur_v1;
v1u.y = v1.x / longueur_v1;
//Calcul du produit scalaire
ps = v0.x*v1u.x + v0.y*v1u.y;
//Calcul du vecteur projeté
p.x = v1u.x * ps;
p.y = v1u.y * ps;

Projection sur un axe

Maintenant que nous sommes parés de tous ces outils, passons au vif du sujet : La détection de collision.

La recherche de proximité (broad phase)

Principe

Avant de savoir comment tester la collision entre deux objets (ce qui implique un certain nombre de calculs), peut être serait-il bon de connaître quels sont les objets à prendre en considération. En effet, si n objets (des tuiles par exemple) sont présents dans le monde, il faudrait faire O(n²) tests de collision par frame.

Le but de cette phase est donc de déterminer rapidement les paires d’objets qui pourraient entrer en collision. Qui dit rapidement, dit approximativement, nous n’avons pas besoin de le savoir de manière absolue, c’est le boulot de la phase suivante (collisions de proximité – narrow phase).

Recherche de proximité (broad phase)

Pour un faible nombre d’objets (inférieur à 5) il est possible de travailler avec hitTest() pour tester les cadres de délimitation des occurrences. Si hitTest() renvoie true, nous savons alors que les enveloppes des deux objets se recouvrent et nous pouvons donc passer à des tests plus complets pour savoir si effectivement les deux objets entrent en collision.

Par contre, pour un nombre plus important d’objets, nous avons besoin d’un moyen plus sophistiqué de déterminer si les objets sont proches les uns des autres. Une des méthodes les plus répandues est l’utilisation d’une grille pour partitionner l’espace (spatial database). Cette grille doit supporter :

• la mise à jour (déplacement d’un objet)
• la recherche de voisinage (déterminer rapidement si les cases voisines contiennent un objet)

Il existe plusieurs façons de découper l’espace qui sont représentées au niveau données par des tableaux ou par des arbres. Il faut savoir qu’en Flash l’utilisation des tableaux montre de meilleurs performances.

Subdivisions de l’espace

Un des problèmes de l’approche par décomposition de l’espace en une grille est que tous les objets dynamiques (comprendre : qui se déplacent) doivent être plus petit qu’une case de la grille (il est tout à fait possible de décomposé un objet en plusieurs plus petits). Pour simplifier le raisonnement, nous prendrons ici le cas d’un seul objet dynamique dans un monde composé de tuiles (tile-based).

Grille de tuiles basiques

L’utilité première de la grille est de stocker les tuiles qui définissent les parties solides du monde et la grille en elle-même est simplement un tableau 2D dont chaque entrée est un objet case. La première chose que l’on souhaite donc pouvoir faire c’est d’avoir la possibilité de déterminer quelle cellule contient le centre de notre objet. Rien de plus simple :

ligne = Math.floor(position.y / hauteur_cellule);
colonne = Math.floor(position.x / largeur_cellule);

Etant donné que nous avons forcé la taille de l’objet à être inférieure à la taille d’une case, nous savons que cet objet ne peut chevaucher que quatre cases au maximum.

Objet et cellules

On peut donc supposer sans trop s’avancer que l’objet peut au plus chevaucher : la cellule courante, la cellule voisine horizontalement, la cellule voisine verticalement et la cellule en diagonale (voisine elle-même des cellules horizontale et verticale). La détermination de ces cellules peut se faire de plusieurs façons :

• en faisant simplement les quatre calculs pour les quatre coins de l’objet
• en faisant un seul calcul pour le centre de l’objet pour déterminer l’index dans le tableau 2D de la cellule contenant le centre et ensuite en procédant par décalage depuis cet index en se basant sur la position relative de l’objet par rapport à cette cellule (en plus clair : si, par exemple, le centre de l’objet est en bas à droite de la cellule courante [i][j], nous savons que nous devons regarder les cellules voisines : basse [i][j+1], droite [i+1][j] et diagonale basse-droite [i+1][j+1]).

Si une partie de l’objet sort des limites de la scène, les méthodes précédentes peuvent générer des index de cellules qui n’existent pas. On peut éviter ça en utilisant des valeurs min/max pour garder les indices dans les limites de la grille ou en utilisant le modulo pour déplacer l’index fautif de l’autre côté de la grille. Une méthode encore plus simple consiste à entourer la grille avec des cellules « bordure » qui peuvent être occupées par des objets statiques qui empêcheraient les autres de sortir des limites de la grille.

Maintenant que nous connaissons les quatre cellules touchées par notre objet dynamique, nous avons besoin de tester la collision avec les tuiles contenues par ces cellules (la méthode pour faire ce test est décrite dans la prochaine section Les collisions de proximité (narrow phase)). Chaque case de notre grille contient donc des informations relatives à la tuile contenue dans cette cellule, ces informations incluent un flag indiquant la forme de la tuile ainsi que toutes les informations nécessaires à la routine de détection de collision (largeur, hauteur, position du centre, etc…). Pour implémenter cette méthode, on peut définir une collection d’objets tuiles de différentes formes, chaque type de tuile étant alors chargée de générer le résultat du test de collision avec l’objet dynamique :

tuile.CollisionAvecCercle(monCercle);

Une autre méthode consiste à utiliser une table de hachage 2D contenant des fonctions de détection de collisions spécifiques à des couples de formes. Les flags de forme sont alors utilisés comme des clefs de hachages pour retrouver la bonne fonction :

Collision[tuile.forme][objet.forme](tuile, objet);

Grille de tuiles avancée

L’idée précédente d’un tableau 2D contenant des tuiles sous forme d’objet peut être poussée un peu plus loin. On peut en effet envisager de stocker dans chaque cellule une référence directe aux quatre cellules voisines. De cette manière, une fois déterminée la cellule qui contient le centre de l’objet, il est possible d’accéder très facilement aux voisines. Certes cette méthode technique utilise plus de mémoire mais elle permet de faire l’économie de quelques calculs. Cette économie de calculs étant pratiquement négligeable, le principal bénéfice est une facilité et une clarté de développement :

cellule.vD; //désignera par exemple la case voisine à droite
cellule.vG; //à gauche
cellule.vH; //en haut
cellule.vB; //en bas

Une autre amélioration que l’on peut apporter à notre grille est de stocker des informations concernant la cellule elle-même mais aussi concernant ses quatre propres bordures. Les données stockées doivent rester minime, par exemple un flag déterminant l’état de la bordure :

• vide : aucune des cellules qui partagent cette bordure ne contient une tuile solide
• solide : la forme de la tuile fait qu’un de ses côtés s’adapte parfaitement à la bordure courante
• intéressante : les bordures adjacentes à une cellule contenant une tuile solide, mais qui ne s’adapte pas parfaitement à cette tuile sont marquées comme intéressantes, ce qui indique que des tests de collisions plus poussés doivent être effectués.

Bordures d’une tuile

Une fois que chaque tuile a reçu les états de ses bordures, on peut simplifier les futurs calculs en comparant les états des bordures des tuiles voisines, ainsi chaque bordure dont les deux tuiles adjacentes ont des bordures solides doit être considérée comme vide. Une telle simplification ne fausse pas les résultats tests de collisions car les objets dynamiques ne sont sensés percuter que la surface du monde hors la configuration citée précédemment ne peut arriver que sous la surface…

Cette structure permet de supprimer les calculs spécifiques à la forme de la tuile, si un objet croise une bordure solide, il suffit de le projeter sur cette bordure plutôt que d’avoir recours à des tests plus complexes. Les seules fois où nous devrons effectivement effectuer ces tests complexes seront lorsqu’un objet touchera une bordure dites intéressante.

Grille d’objets

Les chapitres précédents considéraient principalement la recherche de proximité mettant en jeu un objet dynamique et le monde dans lequel il évolue. Quand est-il de la détection objet/objet ?

Tout comme la structure précédente contenait des informations sur la tuile de la cellule, cette structure peut aussi rassembler des données concernant chaque objet dynamique actuellement contenu dans la cellule. Chaque cellule contient donc une liste d’objet dynamique et alors que les objets bouge, ils sont insérés ou supprimés de la liste des cellules concernées. Une grille étant simplement une structure de données, plusieurs approches sont possibles et les deux plus courantes sont les suivantes :

• la grille régulière : chaque objet est associé a toutes les cellules qu’il touche (entre une et quatre dans notre cas) et lorsqu’il se déplace, il est supprimé des cellules qu’il touchait et inséré dans les nouvelles cellules qu’il recouvre à présent. Le test de proximité se fait alors seulement sur les cellules qu’il touche.
• la grille lâche : chaque objet est placé dans une unique cellule qui contient son centre, lorsqu’il se déplace, il est supprimé de cette unique cellule et inséré dans la nouvelle qui contient sa nouvelle position. Pour le test de proximité nous devons alors prendre en plus en considération la totalité des huit cellules qui entoure la position de l’objet.

Types de grilles

Le choix du type de la grille dépendra vraiment du type de jeu, il faut juste savoir que la grille régulière permet de faire moins de tests de proximité mais sa mise à jour est plus longue et inversement pour la grille lâche. Il faut aussi garder à l’esprit que les performances d’un jeu sont directement reliées aux règles qui le régissent. Prenons l’exemple de missiles, si vous décidez qu’ils ne pourront pas entrer en contact les uns avec les autres, vous aurez simplement à leur faire lire la grille pour savoir si ils entrent en contact avec un objet ou une tuile sans avoir à la mettre à jour. Vous imaginez le gain de calculs ?

Les collisions de proximité (narrow phase)

Principe

Dans ce chapitre nous allons voir comment savoir si deux objets entrent en contact mais surtout déterminer de quelle façon ils se recouvrent. La manière dont les deux formes entrent en contact est représentée par le vecteur de pénétration.

Vecteur de pénétration

Ce vecteur de pénétration nous permet d’empêcher les deux objets de s’interpénétrer mais il permet aussi de gérer la réponse à la collision en l’utilisant dans des calculs physiques. Nous pouvons alors par exemple : infliger des dommages plus ou moins grand selon la longueur du vecteur de pénétration, orienter l’objet pour qu’il s’aligne par rapport à l’autre, gérer le rebond, etc…

Pour déterminer ce vecteur nous allons voir ici la méthode de l’axe séparateur, il en existe bien d’autres mais cette dernière est particulièrement bien adaptée au développement de jeux en Flash :

• rapide
• simple
• flexible

Le Théorème de l’Axe Séparateur (TAS)

En langage mathématique, le théorème de l’axe séparateur s’annonce comme suit :

Deux polyèdres convexes sont disjoints si il existe un axe séparateur. Un axe est dit séparateur pour deux polyèdres si il existe un plan dans l’espace orthogonal à cet axe qui sépare les deux polyèdres, et que cet axe soit orthogonal à la face d’un des deux polyèdres ou orthogonal à deux cotés de chaque polyèdre.

En langage un peu plus clair on peut dire que deux formes convexes ne se touchent pas si on peut tracer une ligne entre les deux.

Méthode de l’Axe Séparateur

Ca parait évident de prime abord mais on ne voit pas bien où cela peut nous mener en raison du nombre infini de droite qu’il faudrait tester. En fait, toujours d’après le théorème, si un axe séparateur existe, il est forcément perpendiculaire à une des faces de la forme ce qui va faciliter grandement nos calculs. La méthode des axes séparateurs consiste donc à :

• déterminer tous les axes séparateurs des deux formes dont on test la collision potentielle.
• tester chaque axe séparateur jusqu’à trouver un axe le long duquel les formes sont disjointe.
• affirmer la collision si les formes ne sont séparées sur aucun axe.

Pour utiliser cette méthode il suffit donc de connaître :

• quelles directions sont perpendiculaires à nos objets.
• comment projeter ces objets sur un axe arbitraire.

On pourra alors déterminer le vecteur de pénétration qui est situé sur l’axe séparateur ayant le taux de pénétration minimum entre les deux objets.

TAS : Les boites

Une des formes les plus communes utilisées dans les jeux pour représenter des formes en mouvement est la boite, appelé AABB (Axis-Aligned Bounding Box) ou OBB (Oriented Bounding Box) selon le cas. Un AABB/OBB est définit par sa position, deux vecteurs unitaires et les deux demi-longueurs le long des vecteurs unitaires. Le concept de demi-longueur est similaire à celui de rayon pour un cercle excepté qu’il est définit le long d’un axe particulier.

Demi-longueurs

Nous allons maintenant illustrer le théorème de l’axe séparateur appliqué à un AABB (le problème d’un OBB, se ramenant facilement à ce cas) contre des formes classiques. Dans tous les schémas qui vont suivre, le recouvrement des formes le long de chaque axe séparateur est représenté par un vecteur en gris et si les formes se recouvrent sur tous les axes, le vecteur de projection sera dessiné en violet. Pour chaque axe, les lignes bleues et rouges montrent la taille des formes le long des ces axes.

AABB vs AABB

Pour deux boites alignées sur leurs axes, il existe seulement deux axes séparateurs qu’il suffit donc de tester.

AABB vs AABB

AABB vs Triangle

Dans le cas d’une collision d’une boite et d’un triangle, il faut tester les deux axes séparateurs de la boite et les trois du triangle. Dans le cas d’un triangle rectangle aligné avec la boite il suffit donc de considérer un axe de plus que le cas AABB vs AABB.

AABB vs Triangle rectangle

AABB vs Formes Arrondis

Comme nous venons de le voir, il n’est finalement pas très compliqué de gérer les collisions entre une boite et des polyèdres convexes. Mais que faire si l’on a des formes arrondies ?

Les cercles ne sont pas directement gérés par le TAS car ils possèdent en fait une infinité d’axes séparateurs : tous les axes sont perpendiculaires à leur surface. Pour appliquer notre méthode il faut donc déterminer quels axes tester en plus de ceux de la boite. Heureusement pour nous, la réponse est évidente (d’un point de vue mathématique au moins) : les axes séparateurs potentiels supplémentaires sont parallèles au vecteur reliant le centre du cercle et les coins de la boite.

AABB vs Forme convexe

AABB vs Forme concave

TAS : Les cercles

La seconde forme 2D la plus utilisée en tant qu’objet se déplaçant est le cercle et comme nous l’avons vu, nous devons légèrement adapter notre méthode pour le prendre en compte. En effet, dans le cas d’une collision entre un cercle et un AABB par exemple, nous devons considérer non seulement les axes perpendiculaires aux côtés de la boite mais également les quatre axes parallèles aux vecteurs reliant le centre du cercle aux quatre sommets de la boite.

Cercle vs AABB – Brut

Tester en plus les axes cercle -> sommets peut ajouter beaucoup de calculs supplémentaires car en effet chacun de ces axes peut être considéré comme séparateur. Par contre, comme nous pouvons le voir dans le schéma « AABB vs Forme convexe », un seul sommet peut raisonnablement entrer en contact avec le cercle : il s’agit du sommet le plus proche du centre du cercle.

Une des techniques pour pouvoir calculer le sommet le plus proche du centre du cercle et d’utiliser les régions de Voronoï. Les régions de Voronoï décrivent en fait une série de régions dans le plan autour d’un polygone qui contiennent la totalité des points les plus proches d’un élément (sommet ou arête) du polygone.

Régions de Voronoï

Donc finalement, si nous connaissons quelle région de Voronoï contient le centre du cercle, nous savons alors quel élément tester en plus des axes séparateurs de la boite.

Cercle vs AABB – Voronoï

Tester la collision d’un cercle avec d’autres formes, comme les triangles rectangles ou les formes circulaires concaves/convexes, s’effectuent exactement de la même manière : il faut tester les axes séparateurs de l’autre formes puis ajouter un axe supplémentaire si le cercle est dans une des régions de Voronoï de la forme.

Conclusion

Voilà, j’espère que cela vous aura donné quelques pistes pour gérer la détection de collision de manière précise et rapide. Bien d’autres techniques et théorèmes mathématiques existent mais cet article avait pour but de vous exposer une des méthodes possibles, cette dernière pouvant être étendue à n’importe quel forme.

Je voulais remercier Raigan de www.harveycartel.org pour son aide et son aimable autorisation de s’inspirer plus que grandement de leurs tutoriaux.

En tous cas : bon courage .

Codes sources et bibliographie

Sources

Toutes les sources des exemples utilisés ici sont disponibles au format zip à l’adresse suivante : detection_collision.zip

Bibliographie

• www.harveycartel.org
• www.gamasutra.com
  • Advanced Character Physics
  • Fast, Accurate Collision Detection between Circles or Spheres
  • Advanced Collision Detection Techniques
  • Crashing into the New Year: Collision Detection
  • Simple Intersection Tests For Games
  • Collision Response: Bouncy, Trouncy, Fun
• Collisions et Intersections
• Intersection of Convex Objects: The Method of Separating Axes
• tilebased collision detection and response
• Un moteur de physique Article 3 – La détection de collisions (PDF)
• Effcient Algorithms for Two-Phase Collision Detection (PDF)
• Game Development Course
• Collision Detection Paper
• An Introduction to Spatial Database Systems (PDF)
• Tile/Map-Based Game Techniques: Base Data Structures
• Rigid Body Dynamics
• Generic Collision Detection for Games Using Ellipsoids (PDF)

Réalisé par : lythium