Algorithmie de collisions de hitboxes

Je discutais récemment avec un de mes étudiants de la gestion de hitboxes dans un jeu vidéo. Le fruit de cet échange m'intéressant, j'ai voulu formaliser tout cela.

L'idée ? Comment aborder les données de hitboxes rectangulaires (AABB) pour simplifier les calculs, ou tout du moins, les rendre plus intuitifs.

Même si j'évoques les différentes approches de hitboxes, ça n'a pas vocation à couvrir pleinement l'état de l'art, ce sont juste les périgrinations d'un informaticien et enseignant curieux.

Petit rappel : une hitbox (ou masque de collision) désigne la zone de l'écran autour d'un élément graphique (par exemple un personnage) qui, si elle se chevauche avec la hitbox d'un autre élément, sera considéré comme en collision.

L'objectif des algos de collision : comment déterminer par le calcul si un élément est en collision avec un autre.

1. Types de hitboxes

Je m'intéresse ici à un espace en 2 dimensions, mais il est facile d'extrapoler cela pour 3 dimensions (un cube au lieu d'un carré, une sphère au lieu d'un cercle, 3 coordonnées au lieu de 2, etc.).

rectangle (axis-aligned bounding boxes ou AABB) : algorithme le plus simple, consistant à substituer à tout objet complexe un rectangle le contenant parfaitement ;
cercle (bounding sphere) : même principe, mais avec un cercle ;
au pixel près (pixel perfect) : précis, mais très coûteux en ressources.

Même si on peut vouloir vérifier la collision entre 2 objects, une grosse partie des collisions peuvent être entre un objet et un simple point, ce qui est notablement plus simple à calculer.

2. Cas complexe : pixel perfect

Je ne souhaite pas développer ce cas aujourd'hui. L'idée est de parcourir chacun des pixels d'un objet et de vérifier s'il existe au moins un pixel de l'autre objet à la même coordonnée.

Le coût d'un tel algorithme étant élevé – $O (n^{2})$ – on préfèrera généralement le précéder d'une première vérification par un test de collision en cercle ou en rectangle. L'idée ? Ne pas avoir à vérifier tous les pixels de l'écran pour connaître les collisions, mais ne vérifier les pixels que des objets suffisamment proches.

3. Cas simple : les cercles

Vérifier si 2 cercles se chevauchent est assez direct. Soit 2 cercles :

cercle A de centre (x_A, y_A) et de rayon r_A
cercle B de centre (x_B, y_B) et de rayon r_B

Vérifier la collision consiste simplement à contrôler si la distance entre leurs centres respectifs est supérieure ou non à la somme de leurs rayons.

Tout d'abord, le calcul de la distance repose sur le théorème de Pythagore :

d = \sqrt{(x_{B} - x_{A})^{2} + (y_{B} - y_{A})^{2}}

Puis la comparaison :

d \geq r_{A} + r_{B}

Cette comparaison me semble très élégante, et c'est cette idée qu'on va tenter de reprendre pour le cas des rectangles.

N. B. : une adaptation de cet algorithme à une ellipse est possible, mais implique des calculs plus complexes impliquant l'angle que je ne développerai pas ici.

4. Cas simple mais lourd : les rectangles

Les rectangles peuvent être définis de manières variées, mais les plus courantes :

coordonnées du coin haut-gauche (x₁, y₁) et du coin bas-droite (x₂, y₂)
coordonnées du coin haut-gauche (x₁, y₁), largeur w et hauteur h

Pas de collision — Cas classiques à gérer dans un algorithme de collision

Collision partielle dans un sens — Cas classiques à gérer dans un algorithme de collision

On peut être tentés alors de contrôler si le côté gauche (puis droit) d'un objet se situe bien entre les 2 côtés de l'autre, et de reproduire les mêmes contrôles avec les coordonées verticales. Prenons les objets A et B :

$x_{1 A} < x_{1 B} < x_{2 A}$
$x_{1 A} < x_{2 B} < x_{2 A}$
$y_{1 A} < y_{1 B} < y_{2 A}$
$y_{1 A} < y_{2 B} < y_{2 A}$

Cela fait déjà 8 contrôles à faire – ce qui sera encore plus lourd à écrire avec du code – et qui ne suffiront même pas à couvrir un cas particulier :

Collision complète : objet entièrement inclu dans l'autre.

Alors certes, ça marcherait si A contient B, mais pas si B contient A. On pourrait ajouter les contrôles suivant (seuls 4 peuvent suffir ici) :

$x_{1 B} < x_{1 A} < x_{2 B}$
$y_{1 B} < y_{1 A} < y_{2 B}$

Mais ça nous amène à un total de 12 contrôles différents, quoique très similaires. Je ne sais pas vous, mais écrire 12 fois la même chose, ça me donne l'impression de perdre mon temps.

5. Simplification des rectangles

En réalité, cette impression de faire 12 fois la même chose est fondée : on vérifie bien 12 fois si un point est situé à l'intérieur d'une zone données. Mais on n'a pas 12 zones différentes ni 12 points et on sent bien qu'il serait possible de factoriser un peu.

Si on reprend l'élégance de la méthode du cercle et qu'on l'applique cette fois-ci au rectangle, on peut définir le rectangle par son point central (x, y) plutôt que par une de ses extrémités, et par sa largeur w et sa hauteur h. On va plus exactement s'intéresser aux équivaleurs du rayon d'un cercle, donc à $\frac{w}{2}$ et $\frac{h}{2}$ .

Il nous suffit alors uniquement de deux contrôles, un pour chaque axe de notre espace (x et y) :

la distance en x entre les centres des objets A et B est-elle inférieure à la somme des « rayons » horizontaux desdits objets (bref, la somme de la moitié de leurs largeurs) ;
de même, la distance en y est-elle inférieure à la somme de la moitié de leurs hauteurs

Comme ce sont des longueurs et distances, il nous suffit de valeurs absolues :

x_{diff} = | x_{B} - x_{A} | \leq | \frac{w_{A}}{2} + \frac{w_{B}}{2} |

y_{diff} = | y_{B} - y_{A} | \leq | \frac{h_{A}}{2} + \frac{h_{B}}{2} |

6. Point d'ancrage

L'unique point servant à définir la position d'un objet est appelé point d'ancrage. Pour diverses raisons généralement liées au positionnement, on peut vouloir définir un point d'ancrage qui n'est pas au centre de notre rectangle. Par exemple, le point d'ancrage d'un personnage sera généralement au niveau de ses pieds plutôt qu'au centre de son corps.

La conséquence est une recomplexification de notre algorithme, mais dont la logique est déjà adaptée et restera inchangée.

Il suffira de détecter si l'objet B est à droite ou à gauche de A pour savoir si on veut utiliser les largeurs à gauche ou à droite des objets, et de suivre la même logique en vertical.

Conclusion

Si la logique mathématique sous-jacente est la même, on voit bien que les 2 approches de calculs de collisions par rectangles n'amènent pas la complexité de la même manière. Je trouve personnellement l'utilisation d'un point d'ancrage centré (inspirée de la méthode des cercles) très intuitive, ce qui facilite la compréhension des calculs, amenant à une facilité de coder cela.

Keep ??? and ??? on!