Forums Développement Multimédia

Les formations Mediabox
Les formations Mediabox
EN CHANTIER
Cette page n'est pas terminée et est en cours d'écriture.

(Vous pouvez laisser cette balise le temps de rédiger votre tutoriel. Ainsi les lecteurs seront-ils avertis que le tutoriel n'est pas terminé. Vous pourrez enlever cette balise quand vous aurez fini.)

Les arbres binaires

Par thoutmosis (Legrand), le 05 novembre 2011

Dans le monde de l'informatique, et plus particulièrement dans le monde du jeu vidéo, il arrive que le volume de données que nous ayons à traiter soit trop important.

Que ce soit un immense tableau sur lequel on boucle, un volume de vertices impressionnant ( dans le cas d'une application 3D ) ou même tout simplement une recherche dans un grand dictionnaire, nous avons tous rencontré ce cas de figure.

Mais doit-on toujours subir la loi du nombre ? Ne peut-on pas “tricher” astucieusement ? C'est ce que je me propose de vous montrer dans cet article.

Prérequis

Il est préférable d'être très à l'aise avec l'AS3 car même si ce tutoriel se veut avant tout théorique, il n'en requiert pas moins un certain niveau de maîtrise de l'AS3 quand il s'agit de passer à la pratique.

Lenteur et algorithmie

Flash: état des lieux

Lorsqu'on est flasheur, bien souvent, une opération coûteuse se traduit par un “freeze de la mort” càd que votre processeur va sur travailler et empêcher le rafraîchissement “visuel” de votre application et même accessoirement vous priver du contrôle de votre machine.

Inutile de dire à quel point un tel effet est disgracieux et entraîne nombre de commentaires du genre:

  • Flash c'est de la m..de !!
  • C'est trop lourd
  • C'est pas optimisé etc …

En effet, la plateforme Flash n'est ni la plus rapide, ni la plus optimisée au monde, cependant elle permet quand même de faire pas mal de choses.

Prenons comme exemple Minko, moteur 3D écrit en AS3, flexible, modulaire, rapide édité par la société Aerys. Minko est capable d'afficher quelques millions de polygônes à l'écran tout en les combinant à des lumières dynamiques et en prenant en compte la physique.

A votre avis comment s'y sont pris les gens de chez Aerys pour créer un moteur aussi performant ? Certes, pour ce qui est de dessiner les éléments ils ont utilisé l'accélération matérielle ce qui est d'une grande aide.

Toutefois, dans une scène hyper complexe on ne peut pas se permettre d'envoyer tout les polygones au GPU et lui dire de se débrouiller avec, il faut trier les éléments et déterminer ce qui sont à afficher ou non… Mais comment effectuer un tel tri ?

Un problème simple

Pour ce chapitre nous allons partir d'un problème très simple:

  • Soit une scène de largeur = 100 000 et de hauteur = 100 000.
  • Soit un ensemble de 500 000 objets à afficher répartis équitablement sur la scène.
  • Soit une caméra de largeur = 800 et de hauteur = 600. Cette caméra peut bouger sur l'axe des x et des y, sa position de base est x=0 et y = 0

Déterminer, en prenant en compte la position et les dimensions de la caméra quels sont les objets à afficher.

Si, en soit, le problème est très simple, sa résolution en revanche l'est un peu moins, nous allons pouvoir le constater à l'aide de l'exemple suivant.

La force brute

La première solution qui nous vienne à l'esprit est de stocker dans un tableau ( ou un vector ) tout les objets d'affichage.

Une fois ce tableau construit, on boucle sur chacun de ses éléments et l'on vérifie si l'objet est compris dans la zone de la caméra, si oui on l'affiche, sinon on n'en fait rien. J'ai implémenté pour vous cette solution et vous propose de tester directement le résultat à l'aide de l'exemple ci-dessous.

L"extension Adobe Flash Plugin est nécessaire pour afficher ce contenu. }}

Comme le démontre l'exemple ci-dessus, le temps de tri et d'affichage est relativement important, pour ma part j’atteins un maximum de 35fps sur ma machine ce qui est bien loin des 60fps visés. De plus, cet exemple ne fait rien d'autre que d'afficher les éléments. Imaginez donc sur un vrai jeu avec communication réseau, gestion des collisions et des événements…

Cette solution, bien qu'étant la plus simple en termes d'implémentation, ne peut résoudre efficacement notre problème, nous allons donc nous pencher sur une autre solution, bien plus performante et pas beaucoup plus complexe, j'ai nommé l'arbre binaire.

II Les arbres binaires

Ici le texte du Chapitre 2

Paragraphe 1

Ici le texte du paragraphe 1 du chapitre 2

Paragraphe 2

Ici le texte du paragraphe 2 du chapitre 2

Conclusion

Ici une conclusion.

Les sources

Mais vous pouvez aussi proposer ces téléchargements tout au long du tutoriel, et pas seulement à la fin.

En savoir plus

Ici des liens intéressants en rapport avec cet article, des documentations, d'autres tutoriels, etc