03 sept. 2007

Exploration de XNA : les décors, seconde partie

Dans le précédent article, nous avons abordé la gestion des décors dans une application XNA sans toutefois aborder tous les types de décors. Nous avons parlé des décors statiques, des décors défilant - et de leur superposition, produisant un effet nommé parralax scrolling - mais nous avons laissé de coté un type de décors pourtant très utilisés dans le monde des jeux vidéos: les décors construits à partir de briques ou tuiles, plus communément appelé en anglais tiled background.

Le code correspondant à cet article peut être téléchargé ici

xna_logo.png [Télécharger Visual C# 2005 Express Edition] [Télécharger XNA Game Studio 1.0 Express Edition] [Télécharger le Service Pack 1 pour VC# 2005 EE] [TorqueX, de GarageGames.com] [XNA Resources] [Forum MSDN XNA Game Studio Express] [GameDev.Net - Plenty of 1s and 0s]

Définition

Qu'est qu'un décors tuilé ? Au contraire d'un décors fait d'une unique image, un décors tuilé est généré en assemblant plusieurs petites images, souvent de forme et de taille identique. Procéder ainsi permet de réduire la mémoire nécessaire à l'exécution d'un jeu. Par exemple, supposons qu'un niveau d'un jeu du type Mario Bros doivent faire 10 écrans de long - taille de l'écran: 640x480. 10 écrans nous donne une image bitmap de 6400x480x24bits, soit un peu plus de 9 MB. 9 MB vous parait bien peu lorsque vous penser à votre PC ou trône 2 GB de mémoire vive. Mais lorsque le premier Mario est sorti sur NES, les cartouches NES n'était pas doté de 9 MB. Etant donné que la puissance CPU disponible ne permettait pas d'utiliser un algorithme de compression puissant comme le JPEG, comment est-ce que Mario a été implémenté ?


Super Mario Bros sur la console NES.

Simplement, en découpant les décors, en regroupant les éléments de décors identique et en reconstruisant la scène au moment du rendu. La technique permet de s'abstraire complètement de la relation taille du niveau / mémoire, et permet donc d'implémenter un niveau virtuellement infini.

Il y a aussi une autre raison pour utiliser des tiles plutôt qu'une image de grande dimension: un temps énorme est gagné au moment de la conception du niveau par l'artiste en charge de le réaliser. Plutôt que de passer un temps fou à peaufiner une énorme image, il peut se concentrer sur les détails des tuiles - et même en créer de nouvelles si le game designer le souhaite.

Aujourd'hui il n'est plus nécessaire de passer par cet artifice pour développer un jeu de plateforme. Le jeu Braid de Jonathan Blow en est un parfait exemple - en schématisant, le décors des différents niveau du jeu sont stocker dans une énorme image; cette technique a été utilisée afin de permettre aux artistes graphiques de donner une atmosphère globale particulière au jeu. Toutefois, même Braid utilise encore des tuiles pour représenter les éléments du décors avec lequel le joueur peut interagir.


Capture d'écran du jeu Braid. Le décors principal est composé d'une image unique.


Capture d'écran du jeu Braid. Les éléments du décors sont des tuiles.

Revenons à nos moutons: j'ai dit "plusieurs petites images, souvent de forme et de taille identique" - ça devrait faire sonner quelque chose dans votre tête. En effet, ça ressemble diablement à une planche de sprite, n'est-ce pas ? Et effectivement, c'en est une, bien qu'on lui réserve un nom particulier dans le cadre de cette utilisation spécifique : il s'agit d'un titleset (en français: ensemble de tuiles). Mais si le tileset est nécessaire pour gérer ce type de décors, elle est loin d'être suffisante car il faut encore déterminer à quelle position mettre quelle tuile.

Encore des métadonnées ?

Vous l'aurez bien évidemment compris sans que j'ai besoin d'en dire plus : encore une fois, nous allons devoir associer à notre titleset un ensemble de métadonnées qui vont décrire avec précision notre décors. Sans celà, comment savoir que telle tuile doit être à telle position ?

Je tiens à le rappeler de nouveau : si dans le cadre du développement de la librairie Pawn j'ai fait personnellement le choix de stocker ces métadonnées dans un fichier XML, rien ne vous oblige à faire de même. Un fichier texte ou binaire fournira le même service, et même si à la longue cela peut se révéler moins pratique il vous est même totalement possible de stocker ces métadonnées à même le code (dans le code associé à cet article, j'ai choisi de stocker ces informations dans un tableau). Un fichier texte ou XML aura l'avantage de pouvoir être édité simplement, sans avoir à modifier le code ou à lancer un compilateur[1] quelconque.

De quelle donnée avons nous donc besoin ? Avant de répondre, notons qu'on peut prendre le problème sous deux angles différents :

  • est-ce qu'il y a une tuile à la position (x,y) dans mon écran virtuel, et si oui, laquelle ?
  • ou dois-je dessiner la tuile N ?

Passons rapidement sur le second type de description : il s'agit de dire pour chaque tuile ou est-ce que cette tuile doit être dessinée; bien évidemment, une tuile sera dessinée non pas une mais plusieurs fois, ce qui impose de gérer une liste de positions. Lorsque viens le moment de faire le rendu, il faut parcourir cette liste de position (pour chaque tuile) et ne pas considérer les tuiles qui ne sont pas visibles. Le problème principal de cette méthode est que l'on dépends entièrement du nombre de tuiles différentes et de la taille du niveau. Afin d'être sûr d'avoir considéré toutes les tuiles, il nous faut parcourir l'ensemble de la liste - un algorithme de complexité linéaire dont la rapidité dépends du nombre de tuiles présentes dans le décors, indépendamment de la position de ces tuiles. On voit tout de suite un problème important : si je double la taille du décors, je double le nombre de tuiles, et par conséquent l'algorithme de rendu est deux fois plus lent et ce malgré le fait que le nombre de tuile réellement affiché ne change pas.

Description sous la forme d'un tableau

Le premier cas est beaucoup plus simple : il implique qu'on a la description de chacune des cellules de l'écran virtuel - sous la forme d'un tableau à deux dimension dont chaque cellule représente une tuile (généralement sont index dans le tileset). Par exemple, en supposant que les tuiles sont numérotées de 0 à 4 et que la valeur -1 signifie "pas de tuile à cet emplacement", on obtiendrait quelque chose qui ressemblerait à ceci :

// taille de l'écran virtuel : 5 x 5
-1 -1 -1 -1 -1
 4 -1 -1 -1 -1
-1 -1  2  2 -1
 1  1  3  3  1
 0  0  0  0  0

Pour créer le décors, il suffit de parcourir le tableau, récupérer l'index de la tuile à une position (X,Y), déduire de cette position la position réelle sur l'écran et afficher la tuile correspondante.

On voit immédiatement un avantage a cette méthode : quelque soit le nombre de tuiles possible et la taille de la description, le nombre d'opérations qu'on doit effectuer au final pour faire le rendu ne dépends que de la taille des tuiles et de la taille de l'écran : on reste dans un algorithme dont la complexité est linéaire, mais le nombre d'opérations effectuées est borné.

Je m'aperçois que j'ai oublié de parler de quelque chose d'important : cette notion d'écran virtuel. Il s'agit tout simplement d'une image (réelle ou non; dans la plupart des cas, on évitera d'utiliser une image réelle pour reconstruire le décors afin de limiter la consommation mémoire; on préfèrera donc utiliser quelques expressions mathématiques simples pour faire le travail) dont la taille est un multiple de la taille d'une tuile. Si la taille en x de ma tuile est tx et que je souhaite que mon niveau ait la longueur de 200 tuiles, alors mon écran virtuel aura une taille en x égale à 200*tx. Seule une partie de cet écran virtuel sera visible à un moment donné et par conséquent il n'est pas nécessaire d'en avoir la représentation complète en mémoire. La position de la tuile (X,Y) (coordonnées décors) à l'écran dépends de plusieurs facteurs :

  • le défilement courant
  • la position de la tuile dans la description du décors
  • et la taille de la tuile

On peut bien évidemment y rajouter le zoom et la rotation si besoin[2].

Les mathématiques utilisées sont extrêmement simples:

// taille d'une tuile = (tw, th) en pixels
// défilement = (sx, sy) en pixels
// position de la tuile dans le décors = (dx, dy)
// position de la tuile sur l'écran réel = (x,y)
x = tw * dx - sx y = th * dy - sy

Puisque le défilement n'est pas nécessairement un multiple de la taille de la tuile (ce qui provoquerait un défilement trop saccadé), il nous faut afficher toutes les tuiles qui sont totalement ou partiellement visibles. On peut trouver directement ces tuiles dans le tableau en utilisant la formule inverse, qui va nous donner (dx,dy) en fonction de (sx,sy), (tw,th) et des coordonnées écran ((0,0), (w,h))

dx_min = sx / tw
dx_max = (sx + w) / tw
dy_min = sy / th dy_max = (sy + h) / th

Une fois ces coordonnées calculées, dessiner le décors reviens à itérer dans la tableau à partir de ces coordonnées:

for (int dy = dy_min; dy < dy_max; ++dy)
{
  for (int dx = dx_min; dx < dx_max; ++dx)
  {
    x = tw * dx - sx;
    y = th * dy - sy;
    DrawTileAtPos(dx, dy, x, y);
  }
}

Implémentation

Oui, parce que discuter c'est bien, mais faire quelque chose c'est tellement mieux. Vous trouverez dans l'archive associés un programme Ex_BackgroundTiled qui, une fois compilé avec XNA Game Studio Express, vous montrera un décors construit à base de tuiles. Pour naviguer dans le décors, utilisez les touches fléchées de votre clavier.

Pour le code d'exemple, j'ai choisi d'utiliser le tileset suivant[3] :

tileset
Tileset "Cute World" de Lost Garden

Deux méthodes sont importantes :

  • GetTileCoordinates() renvoie les coordonnées d'une tuile dans le tileset en fonction de son index. Ce type de calcul a déjà été discuté dans un précédent article.
  • DrawBackground() est la méthode qui effectue le rendu du décors. La description du décors est stockée dans le tableau à deux dimensions backgroundDescription[,]. On calcule les coordonnées décors de la partie du background qui sera affichée puis on lance le rendu.

On notera que nous sommes ici dans un cas un peu particulier - mais qui arrive très régulièrement. En fait, les tuiles de la planche doivent être utilisées non pas en considérant toute la tuile mais seulement en en considérant une partie : le bas de la tuile. Par conséquent, Un peu de math supplémentaire sont nécessaires pour correctement déterminer la partie du décors à afficher. De plus, puisque seul le bas est important, l'empilement de deux tuiles suppose que je vais voir le bas de la tuile du dessous, et que la tuile du dessus va recouvrir le haut de la tuile de dessous. Par conséquent, cela signifie qu'il y a un ordre de dessin. Si je dessine la tuile du dessus en premier, je vais en cacher une partie lorsque je vais dessiner la tuile du dessous. Je dois donc dessiner les tuiles en montant du bas vers le haut pour éviter les problèmes de recouvrement.

Dans la plupart des cas, ce n'est pas nécessaire de procéder ainsi. Si on reprend l'exemple de Mario Bros, le jeu utilise des tuiles rectangulaires vues de coté (et non pas en vue simili-3D comme les tuiles que j'ai utilisé). Par conséquent, on peut dessiner les tuiles dans n'importe quel ordre sans que cela n'ai un quelconque impact sur le rendu.


Exemple: le programme Ex_BackgroundTiled

Code source

Le code source de ce programme est disponible en téléchargement. L'archive contient aussi une version plus ancienne de la librairie Pawn (mais pas si ancienne que ça). Cette version ne supporte pas les décors à tuiles, mais supporte par contre les deux types de décors présentés dans l'article précédent.

A noter que l'archive en question est d'une taille plus importante que les archives précédente. Elle contient l'ensemble du code source des différents programmes décrits dans la série, le code source de la librairie Pawn ainsi que les données associés à chacun des programmes (et pour certain, il y a même plus de données que nécessaire - c'est notamment le cas pour le programme Ex_SpriteAnimated (le nouveau nom du programme ReinerAnim présenté dans un article précédent) qui contient toutes les animations du barbare - soit 64 animations.

Le prochain article s'intéressera aux interactions entre les sprites et le décors. Sur ce, à bientôt !

Notes

[1] au sens premier du terme: c'est à dire un programme qui transforme un fichier donné dans un format spécifique vers un autre format de fichier; en l'espèce, si on fournit une description de décors à un programme chargé de transformer cette description en un fichier binaire, alors ce programme est un compilateur

[2] je reviendrait sur ces améliorations dans un article à paraitre

[3] la version présentée ici a été redimensionnée pour cause de mise en page du blog, et la couche alpha (transparence) a disparu lors de ce processus. Elle est présente dans la version utilisée par le programme d'exemple.

Commentaires

1. Le dimanche, septembre 16 2007, 01:08 par toys3D

Excellent.

tuto de tres bonnes qualites qui vulgarisent enfin la creation de jeux....
et en FR!!
je suis impatient de connaitre la suite.

merci

2. Le lundi, septembre 17 2007, 15:31 par Stéphane

Enfin des explications claires et en Français !
(Entièrement d'accord avec Toys3D)
Ce site est désormais mon site de référence sur XNA et j'attends avec beaucoup d'impatience la suite... :)
J'aimerais beaucoup qu'il y ait un chapitre sur l'animation fluide de textes qui défilent dans tous les sens (comme on pouvait le voir dans certaines démos des années 90).
En tout cas, un grand bravo et merci pour cet excellent site

3. Le mardi, septembre 18 2007, 23:13 par Emmanuel Deloget

Merci!

A force de me complimenter, je vais avoir besoin d'une nouvelle paire de chaussures :)

4. Le mercredi, septembre 19 2007, 15:44 par Stéphane

Juste pour information, je ne suis vraiment pas du style à complimenter facilement, mais je sais reconnaître la qualité lorsqu'elle se présente et sincèrement, ton site est à ce jour le meilleur tutoriel sur XNA en Français (sans conteste possible).
La preuve... je viens tous les jours pour vérifier si il n'y a pas eu un nouvel article !!!

5. Le samedi, septembre 13 2008, 17:38 par fffff &quot;Le Courageux&quot;

pas de news depuis 1an

clair

ca c'est un site top !

6. Le mercredi, septembre 17 2008, 00:30 par Emmanuel Deloget

Je précise que je ne sponsorise pas l'achat de cerveaux pour les personnes qui n'ont même pas le courage de signer leurs imbécilités.

7. Le jeudi, septembre 18 2008, 10:27 par aitina

Bonjour tout le monde

Un grand bravo pour vos tutos et surtout continuez....nous n'avons absolument rien en français sur le Net...un véritable désastre...

Je suis obligé de décortiquer chaque routine sur les exemples donnés dans le Creator Club.

Vous devriez creer un magazine sur le sujet car il ya quelques (1987)années j'ai programmé une simple fenetre (quatre pages de codes) en asm 68000 (Atari)grace à ces revues...dont les sujets se suivaient de mois en mois.

Avec la construction de jeux ou meme d'applications(2d ou 3d)de differents niveaux et toute la technique qui va avec vous avez de quoi ecrire pour plusieurs années..

Je vous remercie pour vos explications sur XNA .

Cordialement

8. Le vendredi, décembre 25 2009, 23:56 par efd

mdr la vieille console a la poubelle

9. Le dimanche, décembre 27 2009, 09:34 par Emmanuel Deloget

L'alcool tue.

Ajouter un commentaire

Les commentaires peuvent être formatés en utilisant une syntaxe wiki simplifiée.

Fil des commentaires de ce billet