Gestion de trajectoire de tir ou de bille, les virgules fixes mises en pratique

[Bobby Sixkilla]

Gestion de trajectoire de tir ou de bille, les virgules fixes mises en pratique

Auteur : Arcadia et YodaJr feat. Jeffres

INTRODUCTION

Vous avez tous un jour joué à un casse brique, ou à un jeu d'action dans lequel les ennemis vous tiraient dessus. Absorbé dans la peau d'un joueur, vous ne vous êtes jamais posé la question de savoir comment de tels mouvements (la bille du casse brique ou les tirs ennemis) étaient gérés par le programme.

Placé dans la peau du programmeur, on se rend compte que tout n'est pas si simple. Pour arriver à déplacer une bille de manière uniforme, quelque soit l'angle, il faut avoir recours à quelques astuces de programmation. Nous allons vous réveler une de ces astuces.

Avant tout, nous voulons remercier particulièrement 2 membres du forum. Geogeo et Jeffres, puisqu'il s'agit d'eux, ont été inspirateurs de la méthode qui sera décrite ci-dessous. Geogeo avait même d'ailleurs posté une partie d'un code similaire pour la gestion de sa bille d'Arkanoid II devellopé sur son convertisseur euro . Jeffres quand à lui, nous a éclairé sur les formules de trigonométrie et vulgarisé l'utilisation des nombres à virgule fixe.

C'est parti !


THEORIE

Les Bases de trigo

Avant tout chose, il convient de préciser que nous aurons affaire à des petites formules de trigonométrie pour opérer un tel déplacement. Pour les familiers ou non de ces calculs, nous avons décidé de vous faire un petit résumé au travers d'un excellent cours de Jeffres. Merci maitre Jeffres pour ces explications !

Envoyé par Jeffres

En matière de gestion des tirs, je vois deux paramètres plus ou moins distincts à prendre en compte : l’orientation du tir et ses coordonnées à chaque étape de son déplacement. Pour l’instant, je vais me concentrer sur cette dernière question, n’ayant pas encore mis en application la première (étant donné que je ne fais pour l’instant tirer que mon vaisseau, je connais l’angle selon lequel il est orienté).

LA THEORIE

Dans tout ce qui va suivre, il faudra bien avoir en tête les formules de base de trigonométrie, à savoir SOHCAHTOA (ou CAHSOHTOA pour les intimes) :

Dans un triangle rectangle



SOH : sin a = côté opposé / hypoténuse, soit sin a = Y / H
CAH : cos a = côté adjacent / hypoténuse, soit cos a = X / H
TOA : tan a = côté opposé / côté adjacent, soit tan a = Y / X

Bon, plaçons-nous dans le contexte. Dans le mini-projet sur lequel je suis en train de travailler, et comme je l’ai dit plus haut, j’ai un vaisseau qui peut tourner sur lui-même à 360° et capable de ne tirer qu’un seul projectile pour le moment.

Pour les rotations de l’appareil, l’angle varie de 0 à 359 de la façon suivante, avec le vaisseau positionné au centre C :



Je ne fais jamais de modulo 2pi, lorsque l’angle passe à 360 je le remet à 0 (et à 359 lorsqu’il est à –1 bien sûr).

Pour les explications qui vont suivre, nous n’allons considérer que la portion de 0 à 90, dans laquelle s’inscrivent 2 triangles rectangle que voici :



J’espère que cette représentation ne manque pas trop de clarté. Ce qu’il faut voir, c’est que j’ai représenté ici 2 angles a et b selon lesquels le vaisseau est susceptible de s’orienter. Suivant l’angle, la longueur de X et Y varie évidemment, d’où les valeurs Xa, Ya, Xb et Yb correspondant aux angles respectifs. H lui par contre ne change pas, il n’y a qu’à imaginer que chaque triangle s’inscrit dans un cercle pour s’en convaincre. La figure ci-dessous devrait vous aider à y voir plus clair :



Appliquons les formules vues précédemment, nous avons :

| cos(a+b ) = Yb / H, soit Yb = H * cos(a+b )
| sin(a+b ) = Xb / H, soit Xb = H * sin(a+b )

Or, d’après d’autres formules de trigonométrie détestées de tout élève :

cos(a+b ) = cos a * cos b – sin a * sin b
et sin(a+b ) = cos a * sin b + sin a * cos b

On obtient donc :

| Yb = H * (cos a * cos b – sin a * sin b )
| Xb = H * (cos a * sin b + sin a * cos b )

Ce qui si on développe donne :

1)
| Yb = H * cos a * cos b – H * sin a * sin b
| Xb = H * cos a * sin b + H * sin a * cos b

Or, en considérant le triangle ne comportant que l’angle a, on a aussi :

| Ya = H * cos a
| Xa = H * sin a

Donc, en remplaçant les termes dans l’expression 1) par leur équivalent , elle devient :

2)
| Yb = Ya * cos b – Xa * sin b
| Xb = Ya * sin b + Xa * cos b

Cette formule permet de déterminer les nouvelles coordonnées d’un point après une rotation d’angle b, et ce sans connaître l’angle qu’il forme avec l’axe des Y.


LA PRATIQUE

A) Position initiale du tir

Passons maintenant à une application plus concrète de ces formules et considérons le moment où le joueur appuie sur la touche de tir de la GBA.

Quelle est la première chose à faire ? Bien évidemment de positionner le sprite du projectile juste devant le canon du vaisseau (dont le sprite est de forme carrée).

Pour cela, nous allons prendre pour base le moment où le vaisseau pointe vers le haut (angle 0), la raison principale en est qu’il est très facile de positionner le tir dans ce cas. Si on se réfère aux explications précédentes, nous constatons donc que partir de cet état équivaut à prendre un angle a égal à 0. Dans ce cas, Ya = H (car cos 0 = 1) et Xa = 0 (car sin 0 = 0).

L’expression 2) devient donc :

3)
| Yb = H * cos b
| Xb = H * sin b

Bien sûr beaucoup me diront qu’il n’était pas nécessaire de passer par l’expression 2 pour arriver à cette conclusion, mais cela me permet au passage de vous montrer que l’on retombe bien sur nos pattes puisque l’on retrouve exactement les formules de bases.

Grâce à l’expression 3) ainsi obtenue, nous pouvons donc déterminer la position que prendra le sprite sur un cercle de rayon H, de même centre C que le centre du sprite du vaisseau, et ce simplement à partir de l’angle de rotation du vaisseau (puisque naturellement le tir part dans la direction que pointe le vaisseau).

Mais ce n’est pas fini, pour l’instant nous obtenons une valeur comprise entre -H et H pour Xb et Yb, ce qui ne suffit bien sûr pas à les positionner sur un écran de résolution 240*160. Si nous l’affichons maintenant, il tournera autour du coin haut-gauche de l’écran, il faut donc tout simplement rajouter les coordonnées du vaisseau à celles du projectile pour se rapprocher d’une solution acceptable.

On a donc :

| Yb = Y_vaisseau - H * cos b // "-" car pour monter à l’écran il faut soustraire
| Xb = X_vaisseau + H * sin b

Encore une dernière étape et nous y serons enfin.

X_vaisseau et Y_vaisseau correspondent au pixel haut-gauche du sprite du vaisseau, or Xb et Yb sont censés avoir leur origine en son centre. Nous devons donc y ajouter la moitié de la largeur du vaisseau.
De même, il faut considérer le sprite du projectile par rapport à son centre, et non pas par rapport à son pixel haut-gauche sinon il aura l’air décalé vers la droite et le bas. Il ne reste donc plus qu’à retrancher la moitié de la largeur du tir, ce qui donne :

| Yb = (Y_vaisseau + largeur_vaisseau/2 - largeur_tir/2) - H * cos b
| Xb = (X_vaisseau + largeur_vaisseau/2 - largeur_tir/2) + H * sin b

Ouf, nous avons enfin notre formule finale. Mais ne crions pas victoire trop vite, parce que ça fera bien rire les vaisseaux ennemis si vous tirez et que votre projectile fait du sur place. Amenons-le donc à se mouvoir.

B ) Déplacement du tir

Pas d’inquiétude à avoir, après avoir franchi tous les obstacles précédents, ce qui suit est une partie de plaisir.

Au fond, en quoi consiste en général un déplacement dans un jeu ? A incrémenter ou décrémenter légèrement les coordonnées des sprites tout simplement à intervalle de temps régulier. Notre tir suivant une trajectoire parfaitement rectiligne et gardant une vitesse constante, il suffit donc de définir un déplacement pour chaque axe lors de la pression sur le bouton de tir.

Lorsque la touche de tir est pressée, en plus de déterminer ses coordonnées de départ, nous devons donc également calculer ce déplacement.

Reprenons la figure 1 :



Le tir part du vaisseau et se déplace le long de l’hypoténuse. Imaginons que nous souhaitions qu’il parcourt une distance d à chaque cycle. A partir de cette distance et de l’angle b qui lui ne change pas (puisque le tir garde toujours la même orientation), il est donc aisé de déterminer le déplacement sur les axes X et Y qui leurs correspondent. Cela par les formules de base :
| depY = d * cos b
| depX = d * sin b

A chaque fois que nous voudrons déplacer notre sprite, nous ferons donc :

Y = Y + depY
X = X + depX

Ce qui nous interesse dans cet exposé

Pour ce que nous cherchons à faire, deux formules sont particulièrement intéressantes.

Y = Y + depY
X = X + depX

avec 

depY = d * cos b
depX = d * sin b

X et Y sont les coordonnées de la bille. A chaque tour, nous leurs ajoutons une valeur de déplacement : depX et depY. Ces deux valeurs sont primordiales, ce sont elles qui en fait conditionnent la trajectoire et la vitesse relative. Ces deux valeurs de déplacement sont calculées en fonction de 3 paramètres : le cosinus et le sinus de l'angle de trajectoire et la vitesse d

A partir de ce point, on peut bien sûr arreter ici et faire bouger notre projectile en laissant le GBA calculer à chaque angle le sinus et le cosinus correspondant. MAIS (car il y a un mais) je pense que c'est un fait connu que le GBA n'est vraiment pas fait pour ce genre de calculs . Manipuler les nombres a virgule flottantes (float) peut s'avérer désastreux pour les performance d'une machine. Ce qui nous interesse c'est de faire un jeu et quand on programme un jeu, on recherche toujours à épargner des temps de calculs. alors on fait quoi ? On laisse tomber ? NON, heureusement il y a une solution : Les nombres précalculés en virgule fixes.

Le principe est simple dans notre cas. On va calculer les valeurs des sinus et des cosinus de tous les angles possibles (nous verrons plus loin qu'il nen faut "que" 256), seules éléments de calculs à faire intervenir des nombres à virgule. Nous irons chercher ces valeurs précalculées quand nous en auront besoin au travers d'un tableau. Ainsi, il n'y aura jamais besoin de calculer un cosinus ou un cosinus.

Mais la certains se disent deja : "Oui mais cosinus x fait 0.654 alors même si on a pas besoin de faire le calcul pour le trouver, il faut quand même le multiplier a la vitesse pour obtenir un deplacement !"
Pas si vite jeunes gens, je n'ai pas tout dit.

En effet, tout le monde le sait, le cosinus ou le sinus d'un angle se situe entre 0 et 1. Il est donc par conséquent composé de nombres à virgule ? C'est la que le principe des virgule fixe (fixed point) fait son entrée. Nous allons convertir tous les nombres à virgule en entier.... en les multipliant par un grand nombre.


Le principe des nombres à virgule fixe

Alors la attention, le but de ce cours et de démontrer un exemple concret de l'utilisation de nombres à virgule fixe. il ne s'agit en aucun cas de faire un cours sur le sujet. Aussi, nous nous concentrerons dans cette démonstration à vulgariser au maximum le principe, et de la maniere suivante :

Imaginez que vous ne travaillez qu'avec des nombres entier. Mais on vous donne comme variables à manipuler des nombres à decimale. Chaque fois que vous ferez un calcul, vous perdrez de la précision...
Un exemple : je veux additionner deux nombres, 10.2 et 14.4.

Valeur entière : 10.2 + 14.4 = 10 + 14 = 24
Valeur reelle : 10.2 + 14.4 = 24.6
Valeur arrondie du resultat : 25

On se rends compte que le résultat peut diverger suivant que nous arrondissont avant de faire les calculs ou pas. La solution pour eviter cela aurait été de faire une chose bien simple, rendre entier les nombres en les multipliant pas un facteur commun. Prenons 10, afin de faire dans la simplicité :

10.2 x 10 = 102
14.4 x 10 = 144
donc : 102 + 144 = 246
Divisons par 10 le resultat : 246 : 10 = 24.6
Soit en entier arrondis 25 !

Voila un des principes des nombres à virgule fixe. il s'agit de faire des calculs avec des nombre volontairement gonflés, et d'en extraire le résultat à la fin. Certes, ce genre de système n'est pas d'une précision extraordinaire, mais pour un jeu, c'est largement suffisant et le temps de calcul épargné plus qu'interessant .

Vous n'etes pas convaincu ? J'ai un autre exemple dans le même genre, et la vous vous direz : "Ouais, effectivement, les fixed point -car c'est plus classe en anglais- sont quelque choses qui marqueront ma vie de programmeur desormais" .
Imaginez une boucle dans laquelle je dois additionner 20 fois une même valeur, prenons 5.4
En arrondi, 5.4 donne 5. donc 5 x 10 = 50. En virgule fixe, nous l'aurions fait passer à 54 (en considerant que nous prenons comme convention de multiplier par 10 !).
Donc 54 x 10 = 540. On repasse en réel (on divise par 10 donc) et nous obtenons 54. Dans la realité, 5.4 x 10 donnent vraiment 54. (CQFD)


Remplir un tableau de cosinus

Nous voulons déplacer notre bille dans tous les sens possibles. Ce qui veut dire que nous devons considérer un cercle entier. Dans un cercle, il y a 360 degrés (soit 360 angles d'un degré). Cela fait beaucoup, d'autant plus que 360 dépasse la valeur d'une variable de type "short" (u8). Si nous voulons limiter un peu les angles et nous en tenir à des valeurs "informatiques", 256 angles sera un bon compromis. En gros, notre cercle aura donc non pas 360 degrés, mais 256 angles (chaque angle faisant 1.4 degrés, mais ça on s'en fout un peu )

Détaillons un peu le cercle. En trigo classique, un demi cercle represente Pi, et donc 180 degrés. Dans notre cercle, il representera 128 (128 quoi ?, je sais pas moi, 128 trucs...). 1/4 de cercle, doit 90 degrés, represente lui pi/2 et 64 trucs. Vous voyez, on s'y retrouve.

Pour remplir le tableau, il suffit donc de calculer le cosinus de chaques multiple de 1.4 degrés (finalement on s'en fout pas tant que ça ), nous aurons nos 256 valeurs correspondant au cercle complet.

Nous savons également que le cosinus d'un angle est égal au sinus de ce même angle plus 1/4 de tour (90°). Donc on peut combiner les 2 tableaux de valeurs cos et sin en un seul, il suffira pour obtenir les valeurs de sinus d'effectuer un décalage de 90° (64 dans notre convention) pour obtenir au final qu'un seul tableau qui contiendra les 256 valeurs des cosinus + les valeurs des sinus décalées de 64, soit 320 valeurs.


PRATIQUE

En application des notions expliquées dans le post précedent, nous pouvons donc établir le code suivant, qui repésente le plus gros point du programme. Pour mettre cela en pratique, nous vous fournissons la source d'une démo dans laquelle vous pourrez retrouver cette partie de code...

Le Code complet

#define Tbl_pcos(x)  Tbl_cos[x]        // Définition du tableau de cosinus
#define Tbl_psin(x)  Tbl_cos[x+64]     // Définition du tableau des sinus



// *************
// Les variables
// *************

const s8 Tbl_cos [320] = 
{127, 126, 126, 126, ..., 12, 9, 6, 3, 0};

u8 vitesse = 2;            // La vitesse de la bille
int angle = 32;             // l'angle de la trajectoire
s16 pos_x = 128;               // Position X de la bille
s16 pos_y = 68;                 // Position X de la bille
s16 pos_x_fixed = 16384;       // Coordonnée de X en virgule fixe
s16 pos_y_fixed = 8704;   // Coordonnée de Y en virgule fixe
u16 dep_x,dep_y; // La valeur des déplacement de la bille actualisées à chaque tour



// *******************
// Fonction principale
// *******************

void deplacement_bille()
  {

     dep_x = (Tbl_pcos (angle_tir) * (vitesse << 7)) >> 7;
     dep_y = (Tbl_psin (angle_tir) * (vitesse << 7)) >> 7;

     pos_x_fixed += dep_x;
     pos_y_fixed += dep_y;

     pos_x = pos_x_fixed >> 7;
     pos_y = pos_y_fixed >> 7;

  }

Explication du code

#define Tbl_pcos(x)  Tbl_cos[x]        // Défnition du tableau de cosinus
#define Tbl_psin(x)  Tbl_cos[x+64]     // Définition du tableau des sinus

Les definitions de constantes qui faciliterons pas mal la lecture du code. Ces deux definitions vont en faite permettre au programme d'aller piocher les valeurs de cosinus et de sinus d'en angle dans un seul et unique tableau, en l'occurence Tbl_cos

const s8 Tbl_cos [320] = 
{127, 126, 126, 126, ..., 12, 9, 6, 3, 0};

Le fameux tableau de 320 valeurs de résultat de cos/sin...
A noter que ces valeurs sont déja converties en virgule fixe

u8 vitesse = 2;            // La vitesse de la bille
int angle = 32;             // l'angle de la trajectoire
s16 pos_x = 128;                 // Position X de la bille
s16 pos_y = 68;                 // Position X de la bille
s16 pos_x_fixed = 16384;       // Coordonnée de X en virgule fixe
s16 pos_y_fixed = 8704;   // Coordonnée de Y en virgule fixe
u16 dep_x,dep_y;   // La valeur des déplacement de la bille actualisées à chaque tour

Il faut un minimum de variables....
Bien sûr, les valeurs de pos_x et pos_y ont étés prises au pif, c'est pour l'exemple... tout le monde avait compris j'espère . Remarquez les valeurs des fixed correspondants (résultats de la multiplication par 128)

dep_x = (Tbl_pcos (angle_tir) * (vitesse << 7)) >> 7;
dep_y = (Tbl_psin (angle_tir) * (vitesse << 7)) >> 7;

Le calcul du déplacement.
Il s'agit ni plus ni moins des formules depY = d * cos b et depX = d * sin b mises en pratique. Pour les cosinus et sinus, pas besoin de faire un dessin .

<< et >> sont des décalages de bit, on les utilise plutot que la division et la multiplication, car au niveau traitement, c'est plus rapide . Et comme pour notre application nous voulons pour la transformation en virgule fixe des multiplications/divisions par 128 (car nous travaillons toujours avec des multiples de puissances de 2) et que pour multiplier/diviser par 128, il suffit d'effectuer un décalage de 7 bits avec ces symboles respectif : << >>

Admettez ce fait ou suivez ce ce lien pour comprendre ) :

Alors donc pour revenir à l'explication du code. Chaque << 7 équivaut donc à * 128 et chaque >> 7 équivaut à / 128

vitesse est en fait le d de la formule. vitesse << 7 est la conversion de la vitesse en virgule fixe. Même si elle est toujours entière, pour les calculs avec des nombres à virgule fixe, tout doit être au même niveau, il faut donc passer le tout en virgule fixe, ce qui revient donc à multiplier (<<7) par 128 tout ce qui n'a pas encore été converti. .

Alors les plus observateurs vont remarquer que l'on multiplie vitesse par 128, pour rediviser ensuite l'ensemble par 128. Cela peut sembler idiot...et ça l'est. On peut simplifier à ce niveau et cela va marcher sans problème. Seulement, j'ai laissé la formule dans sa forme "complexe" pour mettre en évidence le fait que la vitesse également peut être également en nombre à virgule fixe.
Par exemple, avec le systeme actuel, nous avons des choix de vitesses fixes

vitesse : 1 equivaut (1 << 7) soit 128
vitesse : 2 equivaut (2 << 7) soit 256
vitesse : 3 equivaut (3 << 7) soit 384
etc...

Mais si on veut par exemple mettre une vitesse plus précise encore, genre 1.5. Avec notre système, il suffira de remplacer le vitesse << 7 par 192 . Et oui, 1.5 x 128 = 192. Pas bête hein ?

Evidemment, la variable vitesse n'a plus lieu d'être, à moins qu'elle serve à déclarer directement la vitesse en nombre à virgule fixe (comme c'est la cas dans mon 1942).On peut même imaginer un tableau de vitesse si on souhaite s'y retrouver dans les différents degrés. Genre une vitesse comprise entre 1 et 2, avec une précision au 5ème pourrait ressembler à cela :

const char tab_vitesse[6] =  {128, 154, 180, 205, 230, 256};

Il serait donc plus aisé de gérer les vitesse avec une petite variable allant de 1 à 6. Le code ressemblerait à cela :

// declarations des variables
const char tab_vitesse[6] =  {128, 154, 180, 205, 230, 256};  // Mon tableau de vitesse en nombre à virgule fixe
vitesse = 3; // Variable de la vitesse modulaire allant de 0 à 5 

// Calcul du déplacement de la bille
dep_x = (Tbl_pcos (angle_tir) * tab_vitesse[vitresse]) >> 7;
dep_y = (Tbl_psin (angle_tir) * tab_vitesse[vitresse]) >> 7;

Alors....pigé ?!


EXEMPLES ET SOURCES

Voici un exemple que je qualifierais de parfait parce qu'il reprends les éléments expliqués ci-dessus (c'est un peu normal puisque les éléments en question étaient extraits de ce code).

Le programme se contente de faire rebondir une boule qui pourrait être un tir d'avion ou une bille de casse brique. Vous pouvez jouer sur l'angle et la vitesse et constater ainsi qu'elle avance uniformement quelque soit l'angle.

Mine de rien, ce type de déplacement rends un projet plus professionnel, je pense même que les professionnels déplacent leurs objets de cette manière. Les sources sont commentées, et pour ce qui est des affichages de sprites ou de fonds, et bien il faut HAM (et oui, c'est comme ça ).

Bullet_Final.zip

[Bobby Sixkilla]

Yoda, t'as encore la démo et les sources?

[Arcadia]

Envoyé par Bobby Sixkilla

Yoda, t'as encore la démo et les sources?

Moi je les ai encore, les voici .

Les sources et la démo originale se trouvent dans le Bullet_Final.zip.

J'ai retrouvé aussi une démo un peu plus parlante du principe. Un avion fixe au centre de l'écran "visait" en permanence le joueur. C'est pas grand chose mais bon, ça donne une bonne idée du système pour un débutant qui se lancerait dans la prog de ce genre de jeu.

@++


PS : Merci d'avoir ressorti ce tuto Bobby

[omg]

Envoyé par Rystan

Moi je les ai encore, les voici .
Les sources et la démo originale se trouvent dans le Bullet_Final.zip.
J'avais fais aussi une démo un peu plus poussée du principe également. Un avion fixe au centre de l'écran "visait" en parmanence le joueur. C'est une démo un peu plus parlante directement inspirée du code original...
@++
PS : Merci d'avoir ressorti ce tuto Bobby

Merci Bobby pour le tuto et merci Arc... Rystan pour le supplement

[Bobby Sixkilla]

Envoyé par Rystan

Moi je les ai encore, les voici .

Merci! Ca manquait au tuto.

Envoyé par Rystan

PS : Merci d'avoir ressorti ce tuto Bobby

Merci à toi de réapparaître.

Envoyé par omg

Merci Bobby pour le tuto

Merci omg pour les remerciements.

[Yodajr]

Désolé bobby, j'avais pas vu ta question, fallait relancer

Ce tuto a demandé beaucoup de temps (hein rystan ), merci à vous de le sortir de l'oubli