Article Discussion Modifier Historique Forums Salon IRC

Détection pixel-perfect des collisions 2D

Un article de Games Creators Network.

Si vous lisez ces lignes, c'est que vous vous êtes probablement déjà penché sur les techniques de réalisation d'un jeu d'action 2D (plate-forme, shoot'em up, voire beat'em all,...). Lors de la conception de ce type de soft, il est un aspect primordial auquel on ne pense pas forcément de prime abord et qui compose pourtant l'essence même du gameplay : les collisions. Dans cet article, je me contenterai de proposer une méthode générale de détection, vous laissant le loisir de déterminer la manière dont les sprites interagissent à l'écran, autrement dit la gestion des collisions (une balle va-t-elle rebondir ? Un missile se désintégrer ?). Cette présentation sera accompagnée, à titre d'exemple, d'une implémentation en langage C.

[modifier] Découverte du problème

On désire mettre en oeuvre un algorithme de détection des collisions entre objets dans le plan. Ils sont représentés à l'écran par des sprites possédant une position (abscisse et ordonnée) et des dimensions (largeur et hauteur) propres. La plupart du temps, pour un gameplay réellement fun, il faut faire intervenir le processus à chaque cycle du programme (inutile cependant de faire les tests si aucun objet susceptible d'entrer en collision n'est mobile à cet instant). Cela nécessite de la part des fonctions concernées un temps d'exécution relativement court, imperceptible dans le déroulement du jeu. Un minimum d'optimisation est donc requis afin de conserver une animation fluide. Il nous faut comparer les objets deux à deux, à l'aide de leurs positions et dimensions courantes.

N.B. : on considère dans la suite de l'article qu'il n'y a collision que si l'intersection n'est pas vide; si deux objets ne font que se "toucher", la détection s'avère négative. Il sera cependant très simple d'élargir cette conception en utilisant les tests ou masques appropriés.

[modifier] Une première approche

Tout d'abord, simplifions le problème en modélisant nos deux sprites (quelconques) par des formes simples qui les englobent. Cette technique, aussi très utilisée en 3D, est communément appelée la méthode des "bounding-boxes", car elle consiste en fait à déterminer si il y a intersection entre les "boîtes" que l'on a défini.

Prenons ici un rectangle de longueur et de largeur égales à celles de l'image originale. La difficulté se résume alors à trouver si oui ou non les aires définies par les deux rectangles se superposent en partie. Considérons nos amis le pingouin et le diablotin sur la figure 1 ci-dessous, dont les sprites ont été respectivement baptisés _tux et _bsd :

Fig. 1 : Intersection entre boîtes englobantes

Soient (x1,y1) le coin inférieur gauche et (x2,y2) le coin supérieur droit de chaque sprite. Pour que les boîtes englobantes se chevauchent, il faut :

d'une part que _tux.x1 < _bsd.x2 et que _tux.x2 > _bsd.x1, ainsi les deux sprites partagent une même "bande" d'écran verticale;

d'autre part que _tux.y1 < _bsd.y2 et que _tux.y2 > _bsd.y1, ainsi les deux sprites partagent une même "bande" d'écran horizontale.

Lorsque ces conditions sont vérifiées, alors on peut affirmer que les aires des boîtes partagent un même rectangle d'intersection, en rosé sur la figure 1.

Cette méthode détermine s'il y a ou non collision entre des sprites parfaitement rectangulaires, mais dans la plupart des cas permet seulement d'affirmer qu'il pourrait y avoir collision entre deux sprites de forme complexe (la fourche du diablotin peut raser la tête de Tux sans pour autant l'éborgner). Pour obtenir un résultat fiable, il faut augmenter la précision des tests.

[modifier] Allons plus loin

Peut-être vous êtes vous déjà renseigné ailleurs sur la détection des intersections rectangle-rectangle, rectange-disque, disque-disque, etc... Mais posons-nous la question de ce qui peut nous servir à détecter une collision entre deux sprites de taille et de forme quelconques. En effet à moins que vous ne simuliez une piscine à balles ou une pluie de briques, vous souhaitez sans doute que la seule limite à la forme de vos sprites soit la résolution de l'image qui les représente. C'est ici qu'interviennent les techniques de détections au pixel près, encore connues sous le nom de détections "pixel-perfect" chez les anglophones.

On ne s'interesse désormais plus seulement à la forme des boîtes englobantes, mais à ce qu'il y a dedans, c'est-à-dire directement aux données des pixels de l'image. Imaginons le sprite comme sa représentation graphique le laisse supposer : un tableau rectangulaire de pixels, avec chacun sa couleur propre, et dont certains ne sont pas destinés à être affichés. Appelons ces derniers "pixels transparents" et considérons les autres comme "occupés". Ainsi, deux sprites dont les bounding boxes se chevauchent entrent en collision s'il existe au moins une position (x,y) dans le rectangle d'intersection tel que le pixel en (x,y) du premier sprite et celui du second soient tous les deux occupés. Evidemment, la précision se gagne au prix d'une complexité algorithmique accrue, et effectuer une détection de la sorte sera toujours bien plus coûteux que quelques comparaisons. C'est pourquoi on conservera le test des boîtes englobantes, en opérant seulement le pixel-perfect dans l'intersection, si elle existe.

Fig. 2 : Intersection véritable entre deux sprites

Observons l'exemple de la figure 2 : l'ensemble des pixels colorés en rouges forment l'intersection entre les deux images. L'algorithme qui pourrait servir à mettre en évidence la collision qui a lieu serait de la forme :

x <- 0
y <- 0
REPETER
  REPETER
    collision <- est_occupe(x,y,sprite1) ET est_occupe(x,y,sprite2)
    x <- x + 1
  JUSQU'A collision OU x >= largeur_intersection
  y <- y + 1
  JUSQU'A collision OU y >= hauteur_intersection
RETOURNER collision

Il va sans dire que ceci est un modèle simplifié, il faut évidemment prendre en compte la position relative du pixel en (x,y) par rapport aux repères d'origine et de chaque sprite.

[modifier] Les choix d'implémentation

Poursuivons notre raisonnement un chouïa plus près de la machine (puisque notre objectif final reste tout de même l'implémentation).

Chaque point de la bounding box d'un sprite a deux états possibles : soit il est occupé, soit il est transparent; soit il correspond à l'état "1", soit à l'état "0". Cette vision des choses laisse entrevoir une nette amélioration de notre implémentation. En effet, utiliser un masque binaire où chaque pixel de l'image originale est représenté par 0 ou 1 autorise à tirer parti des opérations bit à bit de base du processeur, tout en ne consommant qu'une place mémoire dérisoire (1 bit par pixel), et ceci a fortiori sur les machines actuelles. Le masque de détection n'est de plus pas forcé d'épouser la silhouette de l'image blittée, peut-être souhaitez-vous que la détection intervienne dans d'autres cas que la simple intersection entre les sprites à l'écran (on peut par exemple instaurer une "tolérance" en utilisant un masque légèrement plus contracté).

Les optimisations nécessaires à l'algorithme de détection requierent une vision relativement bas niveau de l'ensemble, il est ici très difficile d'appliquer une méthode à la fois générale et performante. C'est pourquoi je vous propose une implémentation en C, un langage à la fois accessible, très répandu dans le domaine de la programmation ludique et qui permet très facilement la manipulation bit à bit des données.

Pour information, je rappelle les principaux opérateurs logiques sur les bits et leurs équivalents C :

AND (ET) : 0011 &  0110 ->  0010
OR  (OU) : 0011 | 0110 ->  0111
NOT (NON, complémentaire) : ~0101 ->  1010
XOR (OU exclusif) : 0011 ^ 0110 ->  0101
SHR (décalage vers la droite) : 0100 >>  1 ->  0010
SHL (décalage vers la gauche) : 0010 <<  1 ->  0100

NB : décaler les chiffres d'un nombre vers la droite correspond à une division entière par la base de numération utilisée. Le processeur d'un ordinateur traitant exclusivement des valeurs binaires, le décalage vers la droite équivaut ici à diviser l'entier par 2. De même, le décalage vers la gauche correspond à une multiplication par 2.

On utilisera lors des tests l'opérateur AND (& en langage C), dont la table de vérité renvoie 1 uniquement si les deux bits comparés sont à 1. Ainsi, si la comparaison de deux entiers renvoie un résultat non nul, cela signifie que pour une position donnée (chaque bit correspond à un point (x,y) unique dans notre repère), le bit de chaque masque est "occupé", il y a donc superposition de deux pixels à l'écran. Si au contraire le AND retourne 0, il n'existe aucune correspondance entre deux bits à 1 et la collision n'a pas eu lieu.

La structure de masque choisie consiste en un tableau d'entiers. Les positions (x,y) relatives des points sont définies suivant un repère dont l'origine est le coin en bas à gauche; ainsi les valeurs de x et y croissent respectivement vers la droite et vers le haut. On accède au x-ième bit d'une ligne en se plaçant dans l'entier concerné, puis en effectuant un décalage pour amener ce bit en première position (bit de poids faible) :ValeurBit(x,y) = ((ptr_sur_origine_masque + (x/nb_bits_par_paquet) + (y*nb_paquets_par_ligne)) SHR (x MOD nb_bits_par_paquet)) AND 1

Ainsi le bit de poids faible d'un entier possède l'adresse la plus faible et correspond donc au pixel le plus à gauche à l'écran. Par exemple, le nombre binaire 11100000 se traduit par 8 pixels situés de gauche à droite, tels que les 5 premiers soient "vides" et les 3 derniers (les plus à droite) "occupés".

[modifier] Méthode efficace

Le cardinal de l'intersection des bounding boxes (le nombre de pixels qu'elle contient) peut rapidement devenir important et l'ensemble des tests sur chaque élément s'avérer très coûteux en temps d'exécution (a fortiori si beaucoup de sprites sont présents)... Peut-être pas sur la dernière machine à la mode, mais parfois l'avantage des jeux amateurs est de pouvoir tourner sur les petites configs d'antan.

Or pourquoi tester chaque "case" individuellement alors qu'elle peut être représentée par un seul bit ? Et rappelons-nous que les opérateurs logiques de base prennent en opérandes des entiers contenant jusqu'à 32 bits (sur la plupart des machines actuelles). On peut ainsi planifier une implémentation comparant en un seul test, non un couple unique, mais deux "paquets" de bits de chaque masque, et se révéler jusqu'à 32 fois plus rapide que l'algorithme précédent !

Rappelons par ailleurs que les processeurs actuels ne peuvent manipuler de paquets plus petits que 8 bits (1 octet), qu'il est en conséquence impossible d'implémenter directement un tableau de bits et d'effectuer dessus les tests standards (excepté en utilisant les champs binaires sous forme d'unions en C, méthode "virtuelle" peu fiable et le plus souvent, paradoxalement, coûteuse en place mémoire).

La figure 3 ci-après illustre le cas d'une collision à déterminer entre deux masques dans l'aire d'intersection bleue. Les masques sont des tableaux d'entiers 32 bits, dont les indices croissent de gauche à droite et de bas en haut; les colonnes en surbrillance désignent donc les premiers bits (0-ième bit) de chaque "paquet". On remarque l'apparition d'une nouvelle difficulté : les paquets de deux masques distincts ne sont pas forcéments alignés, c'est-à-dire qu'il ne suffit pas d'opérer une comparaison directe du type paquet_a & paquet_b.

Fig. 3 : Mise en évidence de l'intersection des masques

Dans notre exemple les deux masques sont en effet décalés de 6 pixels en abscisse, donc les paquets de 6 bits les uns par rapport aux autres. Les détails des tests sur une ligne de bits exemple sont illustrés sur la figure 4 (les pixels noirs sont vides, les blancs occupés) :

Fig. 4 : Tests sur les bits d'une ligne de masque

Afin de simplifier les tests (et de tirer pleinement parti de notre choix d'implémentation), chaque ligne de masque contient un nombre entier de "paquets" (quitte à retrouver entre 0 et 31 bits inutilisés par ligne). On peut ainsi traiter chaque ligne de bits individuellement. Rappelons que dans le masque le bit de poids faible se trouve à gauche selon le repère d'écran, ainsi lorsqu'on décale les bits vers la droite dans l'écriture binaire d'un nombre, on pourrait représenter géométriquement les pixels du paquet décalés vers la gauche.

Etape 1 : on compare le premier paquet du masque de _tux (en orange) avec celui du masque de _bsd dont on décale les bits de 6 pas vers la droite, car on écarte les bits ne faisant pas partie de l'intersection. Le test est ainsi réalisé sur deux groupes de 26 bits : du n°6 au n°31 (bits n°0 et 25 après décalage) dans le paquet du masque rouge, du n°0 au n°25 dans le masque orange.

Etape 2 : on teste ensuite la fin du premier paquet orange, décalé des 26 bits déjà testés (on garde les 32 - 26 = 6 restants), et le début du second paquet rouge.

Etape 3 : puis on recommence un cycle en comparant le reste du n-ième paquet rouge, toujours décalé de 6 bits, et le début du n-ième paquet orange.

NB : En pratique nous aurions bien sûr arrêté le processus après le premier test, qui présente deux bits à 1 qui correspondent entre eux (bit n°24 dans le premier masque et n°18 dans le second). Cela traduit une collision évidente. NB(bis) : Puisque nous testons ligne par ligne, le décalage vertical des positions des masques n'a pas d'influence sur le déroulement des opérations.

Dans l'implémentation effective finale, cette technique ne fonctionne pas lorsque les "paquets" sont parfaitement alignés (le n-ième bit du paquet rouge correspond au n-ième du paquet jaune, aucun décalage n'est alors nécessaire), j'ai donc dissocié le cas quelconque (ci-avant) et le cas aligné. Pour information cette dernière configuration permet les tests les plus rapides (on compare des groupes de 32 bits exactement), le pire cas (complexité maximale) se présentant lorsque le test des bounding boxes est positif mais qu'il n'y a pas de collision au niveau des pixels (l'ensemble de l'intersection est parcouru).

[modifier] Améliorations

Notre méthode est à présent opérationnelle, mais la réponse du processus de détection est binaire, et sans doute cherchez-vous à aller plus loin. Toujours à titre d'exemple, j'ai développé une variante des mêmes fonctions qui renvoie le cardinal de l'intersection, qui peut-être interprété comme l'intensité de la collision. D'autres fonctionnalités avancées vous sont peut-être nécessaires, comme par exemple la localisation précise de la collision, ou un vecteur d'intersection pour déterminer le "sens" de cette collision. Chaque service supplémentaire coûtera du temps de calcul, ce qui ne devrait pas poser de problème majeur si le tout est bien implémenté. à vous maintenant de développer votre propre approche en matière de détection et de gestion de ce type d'évènement.

Le code fourni n'est sans doute pas un modèle de programmation structurée, notion qui ne fait pas souvent bon ménage avec celle d'optimisation. Provoquer des débranchements en forçant le retour de valeur d'une fonction ou en sortant d'une boucle (à l'aide du mot-clé break en C) après une conditionnelle est formellement prohibé en algorithmique. Néanmoins ces "aberrations" se révèlent parfois indispensables pour obtenir un coût plus faible lorsque l'on programme au bas niveau (peut-être savez vous déjà, si vous possédez des notions d'assembleur, que le processeur ne sait faire que "sauter" d'une adresse d'instruction à une autre). Par ailleurs l'utilisation judicieuse du mot-clé inline entre les mains de programmeurs plus expérimentés peut s'avérer efficace.

Il existe de nombreux articles sur le net traitant bien mieux ce sujet; quelques méthodes d'optimisations C++ facilement applicables sont par exemple exposées par Joris Timmermans à l'adresse : http://www.gamedev.net/reference/articles/article1139.asp. Quoiqu'il en soit, en matière de perfectionnement, penchez-vous sur votre algorithme papier avant toute chose.

[modifier] À vos claviers !

Cette présentation, tout comme le programme qui l'accompagne, est le fruit du travail et des tests d'un être certes consciencieux mais humain, et de fait je ne peux pas garantir qu'elle est exempte d'erreurs en tout genre. Si vous constatiez quelque information erronée ou bug dans le code, n'hésitez pas à m'en faire part.

NB : le code de détection des collisions commenté ici est indépendant du programme exemple. Pour information, ce dernier utilise la librairie SDL pour l'interaction avec le système et la gestion des entrée-sorties, cependant l'affichage est réalisé à l'aide de la librairie OpenGL qui permet de définir simplement un repère orthogonal avec l'origine en bas à gauche. Ce choix convient mieux à l'implémentation exemple mais n'est pas obligatoire.