Magic Numbers et Jeux Vidéo

Noah CUNEO

Tuteur : François BOUSSION

Introduction

Les Magic Numbers, c'est mal !

Mais nous allons voir que dans certains cas de figure... C'est plutôt ok.

Dans un premier temps, rappelons nous ce qu'est un magic number.

Nous sommes tenté de dire qu'un magic number est une constante. Et bien c'est partiellement vrai...

En réalité, une constante et une valeur nommée et explicite. Comme par exemple PI (3.1415...) ou la constante gravitationelle G (9.81).

Alors qu'un magic number est une valeur qui semble sortir de nulle part, par exemple 0x5f3759df.

Vous devez vous dire que cette valeur que j'ai donné, je la sort de nulle part. Et bien non ! Cette valeur est extrêmement utile dans bien des domaine.

D'abord faisons quelques rappels.

Normaliser un vecteur

La normalisation de vecteur est une notion importante des mathématiques et de l'informatique.

Par exemple, pour le jeu que nous avons réalisé en VISI301, nous avons dû normaliser le vecteur existante entre le centre de l'écran et la souris.

Ce dernier permettant de gérer la trajectoire d'un projectile.

Perception - jeu réalisé en VISI301

Pourquoi le normaliser ? Et bien parce que si nous utilisons le vecteur dont je viens de vous parler, la balle irai plus ou moins vite en fonction de la distance entre la souris et le centre de l'écran.

Voici un rappel de comment nous pouvons normaliser un vecteur :

Exemple tout bête de normalisation de vecteur

Nous avons maintenant un vecteur normalisé. Ainsi, notre balle aura une vitesse constante peut importe la distance de la souris.

Et nous pouvons par ailleurs multiplier notre vecteur par un scalaire pour avoir un contrôle total sur la vitesse du projectile.

On a normalisé un vecteur, c'est bien... Mais n'est ce pas un peu lent comme méthode de calcul ?

Si je vous demande de calculer la racine carré de 2531 de tête vous n'y arriverai certainement pas. Pour notre pc c'est pareil, il ne sort pas ce résultat par magie.

Il existe une multitudes d'algorithmes permettant de trouver cela, nous allons nous intéresser à deux de ces algorithmes.

Méthode de normalisation de vecteur

Dans cette partie, nous allons nous intéresser à deux algorithmes :

- Celui de Newton-Raphson

- Celui de la racine carré inverse rapide

Méthode Newton-Raphson

La méthode de Newton Raphson est une méthode itérative qui permet de trouver une racine par approximation successive.

Cela signifie que la précision de notre résultat dépend uniquement du nombre d'itération appliqué à notre nombre initial.

Avec $x$, le nombre dont on cherche la racine, voici à quoi ressemble la suite nous permettant d'obtenir la racine carré d'un nombre :

$y_{n+1}={\frac {1}{2}}\left(y_{n}+{\frac {x}{y_{n}}}\right)$

Donc par exemple pour trouver la racine de 25 on peut réaliser cette application numérique :

$y_{0}=1\quad {\text{(valeur initiale)}}$

$y_{1}={\frac {1}{2}}\left(y_{0}+{\frac {25}{y_{0}}}\right)={\frac {1}{2}}\left(1+{\frac {25}{1}}\right)={\frac {1}{2}}\times 26=13$

$y_{2}={\frac {1}{2}}\left(y_{1}+{\frac {25}{y_{1}}}\right)={\frac {1}{2}}\left(13+{\frac {25}{13}}\right)={\frac {1}{2}}\times 14.923\approx 7.4615$

$y_{3}={\frac {1}{2}}\left(y_{2}+{\frac {25}{y_{2}}}\right)={\frac {1}{2}}\left(7.4615+{\frac {25}{7.4615}}\right)={\frac {1}{2}}\times 9.985=4.9925$

$y_{4}={\frac {1}{2}}\left(y_{3}+{\frac {25}{y_{3}}}\right)={\frac {1}{2}}\left(4.9925+{\frac {25}{4.9925}}\right)={\frac {1}{2}}\times 5.0001\approx 5.0000$

Comme nous pouvons le voir, cette méthode donne une approximation plutôt pas mal.

Mais cette méthode pose un problème. Pour avoir une bonne approximation, il faut réaliser plusieurs itération donc c'est une opération longue.

Certes cette méthode est considéré comme à 'convergence quadratique', ce qui signifie qu'on obtient un nombre cohérent en très peu d'itération.

Mais encore faut il donner un nombre d'itération au préalable. Et nous ne connaissons pas ce nombre.

Mais ces défaut majeurs ont une solution, cette solution est la prochaine méthode que nous allons voir.

Méthode des carré inverse rapide

La méthode des carré inverse rapide a été inventée pour le moteur de jeu quake III, afin d'optimiser les calculs graphique (dont énormément de normalisation de vecteur).

Cette méthode est très intéressante puisqu'elle se base sur la représentation des flottant en binaire pour se réaliser. C'est le genre d'opération que l'on appelle bitwise.

Voici la méthode pas à pas :

- Nous avons notre nombre $x$, que nous représentons en binaire en tant que flottant (IEEE 754 32bit). C'est à dire avec un signe, un exposant et une mantisse.

- Nous allons maintenant considérer ce flottant, comme si c'était un nombre entier en binaire. Nous appellerons cette variable $xi$

- Nous appliquons maintenant la relation : $i=0x5f3759df-\left({\frac {x_{i}}{2}}\right)$

- Nous considérons maintenant que le résultat i est un flottant.

- Nous trouvons donc le carré inverse : ${\frac {1}{\sqrt {x}}}$

Mais comment cela peut fonctionner ? Faisons d'abord une application numérique sur 25 pour y voir plus clair :

- Nous représentons 25 en IEEE 754 32bit : $01000001110010000000000000000000$

- Nous appliquons la relation vu ci dessous, en lisant notre flottant comme un entier (0x41C80000) : $i=0x5f3759df-\left({\frac {0x41C80000}{2}}\right)$

- Nous lisons notre résultat (0x3F6DDB3F) comme étant un flottant.

- Nous trouvons 0.2, qui est bien le carré inverse de 25 : ${\frac {1}{\sqrt {25}}}$

Après avoir lu l'expression littérale et l'application numérique de cette méthode, vous devez vous demander d'où sort le nombre 0x5f3759df. Et bien c'est un magic number.

Pourquoi ce magic number en particulier ? Et pourquoi cette méthode fonctionne en agissant sur un flottant comme il était entier ?

Pour répondre à ces questions, il faut se pencher sur la représentation binaire d'un flottant.

Les nombres flottants sont représentés de tel sorte :

- 1 bit : le signe du nombre (0 pour positif, 1 pour les négatifs)

- 8 bits : pour l'exposant décalé, on dit qu'il est décalé puisque il faut soustraire 127 à la valeur binaire pour obtenir l'exposant. (qui peut être négatif ducoup)

- 23 bits : la mantisse, c'est à dire la partie significative du nombre.

Par exemple, convertissons le nombre 12.75 en flottant binaire :

- 12.75 se représente en binaire (1100.11). Car 1100 vaut 12. 075 vaut 0.5 + 0.25, donc 1/2 + 1/4. Qui sont les deux premières puissance de 2 négatives/

- On normalise le nombre pour l'avoir en écriture scientifique : 1.10011 * 2^3

- Le signe vaut 0 (nombre positif)

- L'exposant vaut 130, car on a 3 auquel on ajoute le décalage de 127. L'exposant vaut alors 130 en binaire 10000010.

- La mantisse, c'est les nombres après la virgule : 10011...comblé avec des 0.

- On a donc 12.75 = 0 10000010 10011000000000000000000

A l'inverse, on peut obtenir un nombre flottant grâce à cette formule, avec S le signe, M la mantisse, E l'exposant et N le nombre que l'on cherche :

$N=(-1)^{S}\times 1.M\times 2^{(E-127)}$

Donc dans notre méthode des carré inverse rapide, lorsque nous considérons notre flottant comme un entier et qu'on le divise par deux, nous décalons en fait tous les bits à droite.

Ce qui revient à diviser l'exposant par deux, et à modifier la mantisse (en fonction du contenu de l'exposant).

Or, diviser l'exposant par deux en base deux revient à diviser le logarithme de l'exposant par deux. Ce qui est proche de ce que ferait une racine carré.

Nous avons donc une première approximation, qu'en est il du magic number ?

Et bien ce magique number sert en réalité d'affinage à notre première approximation. Il à été trouvé de façon empirique et permet d'avoir une approximation assez précise lorsqu'il est soustrait de notre nombre précédent.

Puis à la fin nous relisons notre nombre en flottant, nous obtenos biens la racine carré inverse.

Quel méthode est la meilleure ?

Faisons un test pour savoir quelle méthode est la plus rapide. Même si nous avons déjà une petite idée après ce que nous avons vu.

En réalisant les deux méthodes sur Python, et en testant le temps d'éxecution des 2 sur plusieurs milliers de valeurs. Nous pouvons obtenir ce graphique.

Benchmark des deux méthodes

(Python étant un langage haut niveau, la lecture bitwise est moins efficace qu'avec un langage bas niveau.) (Un benchmark en C est en préparation quand j'aurais trouvé une librarie graphique pour le C)

Comme nous l'attendions, la méthode des carré inverse rapide est plus... rapide.

Nous serions donc tentés de dire : "Mais dans ce cas, utilisons seulement cette méthode pour calculer des carré inverse !".

Eh bien non. Cette méthode est extrêmement imprécise. Et dans certains cas, la précision est une question de vie ou de mort.

Voyons le problème d'une autre manière.

La méthode des carrés rapide est plus rapide, mais limité. C'est à dire qu'elle s'arrête dès qu'elle a faite son travail.

La méthode de Newton-Raphson est lente, mais peux subir un nombre illimité d'itération qui nous approche à chaque fois de la bonne valeur. Mais encore une fois, on ne connait pas le nombre minimum d'itération nécessaire à avoir une bonne valeur.

Pour palier le problème, les personnes travaillant sur le moteur Quake III on tout simplement décidé qu'ils allaient utiliser la méthode des carré inverse rapide, puis une itération de Newton-Raphson par dessus pour de la précision.

Ainsi, pour une première approximation qui aurait pris plusieurs itération avec Newton-Raphson, et bien nous l'avons en une utilisation des carré inverse rapide.

Cette dernière étant imprécise, nous rajoutons une itération de Newton-Raphson qui nous rapproche grandement de la valeur finale.