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

Fvirtman

Nous allons voir maintenant dans ce chapitre comment déterminer une collision au pixel près.

Commentez

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

- Auteur : Fvirtman

- Parution : 26 novembre 2013

- Public visé :

- Licence : Le contenu de cet article est rédigé par Fvirtman et est mis à disposition selon les termes de la Licence Creative Commons Attribution 3.0 non transposé. Les logos Developpez.com, en-tête, pied de page, css, et look & feel de l'article sont Copyright ® 2013 Developpez.com.

Sommaire

- Navigation

- II. Introduction

- III. Utilisation de masques

- III-A. Définition

- III-B. Point sur une image

- III-C. Masques multicolores

- IV. Pixel perfect

- IV-A. Concept

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

- IV-A-2. Complexité

- IV-B. Inconvénients

- Navigation

Navigation

Tutoriel précédent : formes complexes

Sommaire

Tutoriel suivant : gestion des décors

II - Introduction

Nous allons voir maintenant dans ce chapitre comment déterminer une collision au pixel près.

III - Utilisation de masques

L'utilisation des masques va permettre de détecter des collisions sur des zones de formes quelconques.

III-A - 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 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 ».

D'une façon ou d'une autre, vous saurez rapidement, pour un pixel donné, s'il fait partie de Véga, ou du noir autour, soit en comparant la valeur du pixel avec la keycolor, soit en regardant la transparence du pixel.

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

III-B - 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 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.

En premier lieu, testez si votre point est dans la AABB, grâce à l'algorithme « point dans AABB ». Si ce n'est pas le cas, il n'y a pas collision. Si c'est le cas, alors on testera au pixel près.

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.

III-C - 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 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…

Il est possible que Day Of The Tentacle n'utilise pas cette technique, mais plutôt des polygones autour des portes, et qu'on ait affaire à des cas de points dans polygones, je ne sais pas. Quoi qu'il en soit, certains jeux de ce style doivent utiliser des masques multicolores.

IV - Pixel perfect

Le pixel perfect est un algorithme de collision qui va détecter la collision de deux objets au pixel près.

IV-A - Concept

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.

Première optimisation obligatoire, tester s'il y a collisions AABB entre les deux. En effet, ce test est rapide, et élimine tout de suite les cas où les deux images à tester sont loin l'une de l'autre.

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

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

IV-A-2 - 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 la largeur et h la hauteur de l'image 1.

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

IV-B - Inconvénients

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.

Navigation

Tutoriel précédent : formes complexes

Sommaire

Tutoriel suivant : gestion des décors