Collisions au pixel près

L’utilisation des masques va permettre de détecter des collisions sur des zones de forme quelconques.

Définition

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 librairie 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 la noire, 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 (alpha channel). 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.

Point sur une image

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 vous 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.

Masques multicolores

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 ou 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 aura 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 pixel perfect est un algorithme de collision qui va détecter la collision de 2 objets au pixel près.

Concept

Le concept n’est pas complexe. Supposons que j’ai 2 objets, 2 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 si 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 que aucun des pixels ne touche la zone blanche de l’image 2.

Choix de l’ordre des images

Nous avons dit qu’il fallait prendre une image 1, la parcourir et tester ses pixels par rapport à l’image 2. Afin que l’algorithme soit moins lourd, on prendra comme image 1 l’image la plus petite (celle qui contient le moins de pixels).

Complexité

La complexité de cet algorithme dépend directement de la taille de l’image que l’on teste. Plus cette image est grande, plus lourd sera l’algorithme. Nous avons une complexité en O(w*h) avec w et h hauteur et largeur de l’image 1.

C’est assez lourd. Surtout si on doit tester, à chaque frame, plusieurs collisions.

Inconvénients

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

Prenons nos 2 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 la le problème, il ne « déplace » par 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 sautement 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.