Théorie des collisions : Sprites enrichis

Fvirtman

Jusqu'à présent, nous avons considéré les sprites (petits objets animés) comme une simple image, ou un simple ensemble d'images. Cependant, rien n'interdit, en se faisant son propre éditeur de sprites, de pouvoir rajouter des informations directement dans les images pour aider au calcul de collision, ou même à l'affichage.

Commentez

- Titre : Théorie des collisions : Sprites enrichis

- Auteur : Fvirtman

- Parution : 27 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. Point chaud et point d'action

- III-A. Le point chaud

- III-A-1. Problème

- III-A-2. Insertion du point chaud

- III-A-3. Blit sur le point chaud

- III-B. Le point d'action

- IV. Sous-AABB

- IV-A. Définition

- IV-A-1. Collision

- IV-A-2. Première optimisation

- IV-A-3. Deuxième optimisation

- IV-B. Davantage de sémantique

- Navigation

Navigation

Tutoriel précédent : partitionnement de l'espace

Sommaire

Tutoriel suivant : les collisions dans les jeux

II - Introduction

Jusqu'à présent, nous avons considéré les sprites (petits objets animés) comme une simple image, ou un simple ensemble d'images. Cependant, rien n'interdit, en se faisant son propre éditeur de sprites, de pouvoir rajouter des informations directement dans les images pour aider au calcul de collision, ou même à l'affichage.

Ce sera donc le graphiste qui rajoutera des informations qui nous seront fort utiles.

Voyons ici quelques concepts d'informations qu'on pourrait rajouter aux images.

III - Point chaud et point d'action

Ici, nous allons parler du point chaud et du point d'action. Ce sont des concepts qui simplifient bien la vie dans certains cas.
Le vieux logiciel de création Klick & Play utilisait ces concepts.

III-A - Le point chaud

Le point chaud ne concerne pas directement les collisions, mais il peut être utile d'en parler.

Regardons ensemble l'image suivante :

Vous avez reconnu ce cher Dhalsim, fakir combattant assez élastique dirons-nous. Quand il donne un coup, il a une très grande portée ! Nous voyons ici deux images, l'une où Dhalsim ne donne pas de coup, et une où il donne un coup de pied bien tendu.
En bleu, j'ai dessiné les boîtes englobantes, elles ne sont pas de la même largeur. Cela va poser problème.

III-A-1 - Problème

Imaginons que vous vouliez faire une animation de Dhalsim qui donne un coup de pied. Vous avez ces deux images, ci-dessus, et vous voulez faire l'animation.

Vous blittez donc tour à tour chaque image, un blit colle l'image à la position x,y de telle sorte que le coin supérieur gauche de l'image blittée soit aux coordonnées (x,y).

Conséquence immédiate : vous aurez un Dhalsim qui va vivement partir à droite quand il donnera un coup de pied, parce que dans une image, sa tête est à côté du coin supérieur gauche, et dans l'autre, elle est loin. L'animation va être complètement ratée.

La seule solution est de blitter la première image à une position (x,y), et de blitter la seconde à une position (x2,y) avec x2 < x, et de bien calculer x2 de façon à ce que le corps de Dhalsim reste au même endroit.

C'est extrêmement contraignant, surtout s'il faut faire ça avec chaque image.
Et pourtant, si on veut une belle animation, il faut calculer un x2 correct.

III-A-2 - Insertion du point chaud

Pour pallier ce problème, nous allons dire au graphiste que nous souhaitons des informations supplémentaires, et qu'il nous les donnera graphiquement.
Regardez les points rouges que j'ai mis au pied de Dhalsim dans chaque cas. Imaginez maintenant qu'on ait une fonction de blit qui affiche le personnage non pas en considérant que l'ancrage est en haut à gauche, mais qu'il est au niveau de ce point rouge.
Autrement dit, le point rouge est les coordonnées (x,y) du blit, et Dhalsim se dessine autour.

Le problème est donc résolu : l'animation sera convenable.

Ce point rouge, c'est le point chaud. Il faudra définir un point chaud pour chaque image pour notre cas.

À vous de programmer un éditeur qui permet au graphiste de définir un point chaud pour chaque image à blitter.
Vous savez, il y a deux possibilités de gérer les sprites : soit un sprite par surface, soit une planche de sprites sur la même surface et un blit partiel.
Dans le premier cas, chaque surface devra avoir un point chaud. Dans le deuxième, il y aura autant de points chauds que d'images dans la planche.

Un point chaud, c'est juste les coordonnées (x,y) locales à l'image. Dans la première image, on aura par exemple le point chaud qui a comme coordonnées (45,100), et dans la deuxième, il a comme coordonnées (167,100).

Ces coordonnées ne seront pas entrées à la main par le graphiste, mais en un clic : le graphiste a son image sur l'écran, il clique sur l'option « mettre point chaud » puis il clique sur son image entre les pieds de Dhalsim, et l'éditeur stocke les coordonnées de souris relatives à l'image, tout simplement. Cela reste donc visuel. C'est la machine qui fait les calculs.

Notez qu'un point chaud aux coordonnées (0,0) est un point chaud en haut à gauche, donc ça nous ramène au cas du blit normal !

III-A-3 - Blit sur le point chaud

Les bibliothèques graphiques ne gèrent pas les points chauds. Elles fournissent une fonction « Blit » (SDL_BlitSurface par exemple) qui va blitter de telle sorte que le point (x,y) passé soit le coin supérieur gauche de l'image.

Pour créer une fonction « BlitAuPointChaud », il suffit de faire deux soustractions.
Soit une fonction :

void Blit(Image Source,Image Destination,int x,int y);

La fonction BlitAuPointChaud s'implémente ainsi :

void BlitAuPointChaud(Image Source,Image Destination,int x,int y,int xpointchaud,ypointchaud)
{
Blit(Source,Destination,x-xpointchaud,y-ypointchaud);
}

Pour les utilisateurs de SDL, nous aurons :

void BlitAuPointChaud(SDL_Surface* Source,SDL_Surface* Destination,int x,int y)
{
SDL_Rect R;
R.x = x - xpointchaud;
R.y = y - ypointchaud;
SDL_BlitSurface(source,NULL,destination,&R);
}

III-B - Le point d'action

Le point d'action est un autre point que le graphiste peut mettre pour nous aider. Regardons le dessin suivant :

On peut voir ici plusieurs images de Ken donnant un coup. Regardez, j'ai placé à chaque fois un point violet à l'endroit du potentiel point d'impact.

L'idée est simple : c'est encore le graphiste qui va définir le « point d'action » pour chaque image ou le personnage donne un coup.
Et en tant que programmeur, je vais dire « si le personnage donne un coup, alors je regarde si le point d'action touche l'adversaire. Si c'est le cas, il se prend le coup, et seulement dans ce cas-là ».

Vous voyez, si Ken donne un coup de poing, seul le poing est dangereux. Si l'adversaire est derrière contre sa jambe, il n'a pas à se prendre le coup.

L'idée du point d'action permettra de tester une collision avec un simple algorithme du « Point dans AABB » !
Le graphiste rajoute là une information extrêmement enrichissante et qui simplifie la vie du programmeur.

Le point d'action est également les coordonnées (x,y) relatives à l'image.
Si on veut savoir où se trouve le point d'impact sur l'écran, il suffit de faire l'opération suivante :

xpointimpact = (xpositionperso - xpointchaud) + xpointactionypointimpact = (ypositionperso - ypointchaud) + ypointaction

On testera ensuite le point (xpointimpact,ypointimpact) dans l'algorithme « point dans AABB ».

La difficulté de cette collision ne vient donc pas des fonctions utilisées, qui sont simples, mais de la conception d'un éditeur permettant de définir un point chaud et un point d'action pour chaque image.

Évidemment, le point d'action n'a de sens que si un coup est porté, et pas si le personnage est en attente. Alors on peut mettre un point d'action bidon, ou pas de point d'action du tout pour les autres images, et le considérer uniquement si le personnage est dans un statut offensif. À vous de définir tout ça selon vos besoins.

IV - Sous-AABB

La notion de sous-AABB (ou Sub AABB, qu'on notera SAABB) va permettre des collisions plus fines, et pas tellement plus calculatoires. Cependant, tout comme les points chauds et points d'action, les informations de SAABB devront être fournies avec les sprites au programmeur, grâce à un éditeur créé pour l'occasion.

IV-A - Définition

Regardons ensemble l'image suivante :

Nous voyons Ken dans plusieurs positions. Cependant, vous pouvez constater que j'ai rajouté des AABB autour de lui, dans chaque image. Ce sont les SAABB. J'en ai rajouté seulement quelques-unes, mais qui permettent d'approximer la forme correctement.

IV-A-1 - Collision

Nous avons vu qu'un algorithme de collision dans ce cas-là peut être simplement un algorithme de « Point dans AABB ». Si nous considérons la AABB globale de l'image cible, vous restez trop approximatif dans notre cas : vous pouvez frapper l'air au-dessus de l'épaule de Ken…

Pour un algorithme plus fin, on appellera plusieurs fois l'algorithme « Point dans AABB » dans chacune des SAABB. Si le point testé touche une seule SAABB, alors il y a collision.

IV-A-2 - Première optimisation

Si on veut tester la collision d'un point dans le personnage, avant de tester chaque SAABB, on testera d'abord la AABB entière, celle de l'image.
Si on ne touche pas cette AABB, inutile d'aller plus loin : il n'y a pas collision.
Sinon, on teste chacune des SAABB.

IV-A-3 - Deuxième optimisation

Nous pouvons considérer les SAABB en hiérarchie. Par exemple, vous voyez la première image, il y a plusieurs SAABB bleues côte à côte. Soit on les teste une par une, soit on teste d'abord la AABB de l'ensemble des boîtes bleues. Si on ne touche pas cette dernière, inutile de tester chacune des SAABB internes…

IV-B - Davantage de sémantique

Vous savez, dans Street Fighter 2 ou autres jeux de combat, un personnage souffrira différemment s'il prend un coup dans la tête, dans le corps, ou dans les jambes.

Regardez le dessin ci-dessus : j'ai fait exprès de dessiner en bleu les boîtes correspondant aux jambes, en jaune celles de la tête, en vert celles du torse, en violet celles des bras.
Si le graphiste respecte bien un tel codage de SAABB, alors on pourra détecter, lors d'une collision, dans quelle couleur de SAABB tape le point d'action de l'autre joueur.

Cela nous permettra de savoir immédiatement si on a tapé dans la tête, dans le torse, les pieds…

C'est ce qu'on appelle rajouter de la sémantique directement au niveau des sprites.

Au lieu d'avoir une suite d'images sans données, on aura une banque de sprites, qui contiendra des images, mais aussi plein d'informations pour chaque image, informations qui auront été rentrées graphiquement à la souris avec un éditeur, et qui faciliteront énormément le travail des programmeurs.

Cette partie nécessite donc un travail en amont au niveau de la création des sprites pour être utilisable.
N'oubliez pas que les boîtes de jeux se programment souvent leurs propres éditeurs, leurs propres outils, en fonction de leurs besoins.

L'idée est de donner graphiquement le maximum de sémantique au niveau des images elles-mêmes, pour simplifier la tâche du programmeur par la suite.

Navigation

Tutoriel précédent : partitionnement de l'espace

Sommaire

Tutoriel suivant : les collisions dans les jeux