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, néanmoins je vous invite à télécharger les sources des illustrations si vous êtes curieux.
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 10x10 = 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 :
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)
