Théorie des collisions : Collision au pixel près (pixel-perfect)

Au sens strict du terme, on appelle « masque » une image faite de deux couleurs qui représente un objet de façon monochrome.
Ci-dessous par exemple, vous voyez ce cher Véga, à gauche, et la même image qui représente le masque de cette image à droite :

Si vous manipulez SDL par exemple, vous connaissez déjà la notion de masque, même sans forcément en connaître le nom, au moins pour le concept d'affichage.
Avec SDL, ou autre bibliothèque graphique 2D, vous définissez une « keycolor », c'est-à-dire une couleur qui sera transparente : si vous affichez Véga, vous ne voulez pas que le noir autour s'affiche, donc vous définirez que la keycolor sera le noir, et la carte graphique n'affichera que les pixels du personnage.

Si vous manipulez des PNG, ou des images 32 bits, le format permet directement de définir de la transparence pour chaque pixel (canal alpha). Il est d'usage de mettre les pixels qui correspondent à Véga en « opaque » et le noir autour en « complètement transparent ».

Finalement, pour l'affichage, la machine va afficher uniquement la partie « blanche » si on regarde le masque, donc uniquement Véga.

Si maintenant, vous souhaitez cliquer sur l'image, et savoir si vous cliquez bien sur Véga, au pixel près, et non sur le noir autour, vous considérez la collision « Point sur image ».

L'idée est très simple : vous cliquez sur l'image. Tout d'abord, il faut savoir si vous cliquez dans la AABB de cette image ou pas. En effet, si votre personnage est à l'autre bout de l'écran par rapport à votre pointeur de souris, inutile d'aller vérifier au pixel près si vous touchez, car ce n'est pas le cas.

Considérons la fonction « PixelMaskColor(I,x,y) » qui renverra 1 si le pixel du masque de l'image I à la coordonnée x,y est blanc, 0 s'il est noir.

Cette fonction dépendra de comment vous codez le bord du personnage :

• si vous utilisez une keycolor, il faudra lire le pixel, et le comparer à la keycolor. Si ce pixel est de la même couleur, on renvoie 0, sinon on renvoie 1 ;
• si vous utilisez l'alpha channel, vous regarderez la composante alpha du pixel, et renverrez 0 si le pixel est complètement transparent, 1 sinon.

Nous pouvons écrire la fonction suivante :

bool CollisionPixelMasque(Image I,AABB box,int curseur_x,int curseur_y) 
{ 
   if (CollisionPixelAABB(box,curseur_x,curseur_y)==false) 
      return false; 
   int xlocal = curseur_x - box.x; 
   int ylocal = curseur_y - box.y; 
   if (PixelMaskColor(I,xlocal,ylocal)==1) 
      return true; 
   else 
      return false; 
}

xlocal et ylocal sont les coordonnées locales du pixel à tester dans l'image I. Par exemple, si votre image démarre à la coordonnée 100,100, et que vous cliquez à la coordonnée 110,110, il est clair qu'il faudra tester les pixels de coordonnée 10,10 dans l'image. 10,10 étant les coordonnées locales du pixel à tester dans le repère de l'image.

Nous pourrons considérer des masques multicolores. Cela pourra être fort utile pour les jeux du genre « point & clic ». Si on regarde les images suivantes, de Day Of The Tentacle :

Le personnage évolue dans des décors farfelus. On peut cliquer sur une porte pour qu'il y aille, cliquer sur le sol pour qu'il se déplace, et également cliquer sur les objets.

Pour déterminer toutes ces zones à partir d'un masque, une idée est de dessiner deux images par décor : l'image affichée, et aussi une image faite de zones de couleur, comme l'image de droite.
Pour détecter la collision du pointeur de souris, il suffira de lire le pixel du masque à l'endroit où on a cliqué. Si je clique sur la zone rouge, Bernard ira vers la porte du fond. Si je clique sur la zone bleue, il ira vers la porte de droite.

Notez que pour mon exemple, j'ai laissé le reste du décor, alors qu'un masque multicolore aurait effacé tout décor, simplifiant au maximum le schéma de la pièce.

Il faudra donc, quand on dessinera la pièce, dessiner en parallèle le masque multicolore. Cela se fait facilement, il suffit de charger une copie de l'image de la pièce dans un logiciel de dessin, puis de barbouiller de couleurs l'image au bon endroit. Personnellement, j'ai fait l'image de droite avec Paint…

Ce masque créé sera compact sur le disque, car il contiendra peu de couleurs différentes, donc se compressera bien. Il pourra également prendre peu de place en mémoire, car on pourra stocker chaque pixel sur un octet, voire moins. Si vous avez de la mémoire et que ce concept de stockage vous fait peur, vous pourrez simplement garder l'image multicolore en mémoire comme une autre…

Le concept n'est pas complexe. Supposons que j'aie deux objets, deux personnages par exemple (avec leur masque) :

Je veux simplement savoir s'ils se touchent, au pixel près, si leurs zones blanches (dans le masque) se touchent ou non.

Et si les deux boîtes englobantes se touchent, on va voir s'il y a collision réelle, donc si ce sont bien les « parties blanches » qui se touchent.

Pour cela, nous utiliserons un algorithme très lourd : pour chaque pixel de l'image 1, on regarde si ce pixel est « blanc » sur le masque. Si c'est le cas, on regarde le pixel correspondant sur l'image 2. Si ce pixel est également blanc, il y a collision, sinon, on continue à tester les autres pixels. Il n'y aura pas collision si et seulement si on a tout testé, et qu'aucun des pixels ne touche la zone blanche de l'image 2.

IV-A-1. Choix de l'ordre des images▲

IV-A-2. Complexité▲

Outre les ressources en calcul assez lourdes, cet algorithme présente beaucoup d'inconvénients.

Prenons nos deux Véga, mettons-les côte à côte. Puis faisons en sauter un verticalement : le pied sera bloqué par la griffe. On pourra « coincer » un bras entre la jambe et la griffe de l'autre Véga.
Cela complique énormément les choses au niveau programmation, et « coincera » nos personnages de façon gênante au niveau gameplay.

Si on considère un Zelda vu de haut, on se promène près d'un arbre, et notre bouclier pourra se coincer dans une branche, si un pixel « dépasse » …

Ensuite, au niveau animations. Notre Véga, quand il marche, bouge ses jambes. En réalité, et c'est bien là le problème, il ne « déplace » pas ses jambes comme dans la réalité, mais c'est un nouveau dessin avec les jambes dessinées à une autre position qui apparaît à la place du premier, comme s'il « téléportait » ses jambes à un autre endroit.

Du coup, imaginons une pierre posée à ses pieds, entre ses jambes : il n'y a pas collision. Le dessin d'après nous dessine son pied pile sur la pierre : il est dans la pierre, ce n'est pas logique, pas acceptable. Pour pallier ce problème, que fait-on ? On le décale ? Si la pierre est assez grosse, on le décale d'un coup de 25 pixels, ça fait un sautillement vif bien moche.
Et si en le décalant, ça l'amène sur un mur, que fait-on ? On le décale ailleurs ? Et si on ne peut pas, il est coincé à cause d'une petite pierre ?

Le pixel perfect est selon moi une vraie boîte de Pandore, un nid à ennuis.

Alors pour des sprites qui ne s'animent pas (une balle par exemple), on n'aura pas les problèmes cités ci-dessus, mais n'oublions pas la lourdeur du calcul. Est-ce bien nécessaire ? Dans un jeu qui bouge à toute vitesse, est-ce que l'exactitude de collisions au pixel près est fondamentale ?
Je pense que dans la plupart des cas, non.

Sûrement qu'il y a des cas où c'est obligatoire.

Voici donc quelques algorithmes de collision au pixel près.