1. Les heightmaps▲
Le principe de rendu de terrains en trois dimensions intitulé Voxel (que l'on a récemment retrouvé dans des productions ludiques telles que Outcast ou Delta Force) se base sur des heighmaps. Pour simplifier les choses, chaque point du heightmap associe une valeur, une couleur. Cette valeur donne la hauteur du point considéré. Sans aller jusqu'à la réalisation d'un moteur Voxel (peut-être plus tard, qui sait ?), voyons comment générer et afficher un heightmap.
Chaque point de notre heightmap se verra associé une valeur qui correspondra à l'un des 256 couleurs de notre palette. En vous référant à l'article précédent, vous découvrirez l'algorithme en charge de la création de la palette de couleurs. Les couleurs choisies s'étalent dans les tons de bleu, vert et blanc. Le bleu indique les niveaux de basse altitude, le vert les niveaux intermédiaire et le blanc les niveaux de haute altitude.
2. Génération du heightmap▲
Internet recense de nombreux algorithmes de génération aléatoire de reliefs. Certains d'entre eux sont très connus, comme le Perlin Noise, et d'autres bien moins. Nous avons dans notre exemple opté pour un algorithme extrêmement simple dont les résultats se révèlent amplement suffisant pour nos préoccupations. Il s'agit de l'algorithme "diamant".
Notre heightmap se trouve représenté par une grille carrée. Dans le code source, la grille en question se voit incarnée par une structure nommée grid2d possédant une largeur, une hauteur et un tableau de valeurs sur 8 bits (unsigned short int). Nous allons commencer par attribuer une valeur aléatoire entre 0 et 255 aux quatre coins de la grille. Ceci fait, nous calculons la moyenne de ces quatre valeurs puis plaçons le résultat au centre du carré formé par les coins.
Munis de ce nouveau point, nous obtenons une subdivision de la grille en quatre zones carrées. Le but consiste à maintenant calculer la moyenne des quatre sommets des diamants en leurs centres. La création des diamants conduit à une nouvelle subdivision en carrés. Nous recommençons alors pour chaque carré l'algorithme depuis le début.
L'implantantion en langage C de cet algorithme se trouve au sein de la fonction createPlasma() du code source. Le problème de cette méthode de calcul réside dans l'aspect très granuleux du heightmap résultant. Vous pouvez le constater sur l'image numéro un. Pour pallier ce problème, nous effectuons une interpolation bilinéaire sur la grille. L'algorithme d'interpolation bilinéaire aura pour effet de lisser le résultat. Son concept se veut fort simple. Nous créons une nouvelle grille, et pour chaque point de cette grille nous calculons la valeur moyenne des quatre pixels adjacents de l'ancienne grille.
3. Affichage du heightmap▲
Pour exécuter le programme sur un émulateur ou une GameBoy Advance, vous devrez presser la touche Start. De trop nombreuses secondes s'écouleront avant de voir apparaître le heightmap. Notre algorithme se révèle donc fort inefficient, mais ceci nous importe peu. Nous possédons donc une grille de valeurs carrée (qui dans le code source posséde une longueur et une largeur de 256 valeurs pour coller au plus près aux dimensions de l'écran de la machine) et une palette de couleurs. Vous pouvez essayer d'adapater la fonction d'affichage d'une image de l'article précédent pour dessiner notre heightmap à l'écran. Malheureusement, vous constaterez que l'affichage se fait ligne par ligne (ou colonne par colonne) et se révèle de plus très lent.
L'utilisateur distingue nettement les lignes ou colonnes se tracer. En effet, la table des valeurs de notre image se trouvait auparavant compilée sous la forme d'un tableau constant. Le compilateur optimise ce genre de données en les plaçant en ROM. De ce fait, la copie de ces données se réalise très rapidement. Il en va autrement pour notre heightmap. Celui-ci se trouvant en effet calculé lors de l'exécution, le compilateur ne peut procéder à des optimisations dessus. Une solution à ce problème existe, le Direct Memory Access ou DMA.
Cette méthode consiste à demander à la machine d'effectuer elle-même la copie des données. Nous employons pour cela trois registres spéciaux.
#define REG_DMA3CNT *(u32*) 0x40000DC
#define REG_DMA3DAD *(u32*) 0x40000D8
#define REG_DMA3SAD *(u32*) 0x40000D4Le premier resgitre correspond au registre de "commande" du DMA. Lorsque nous changerons sa valeur, nous exécuterons le processus. Le registre REG_DMA3DAD désigne le registre accueillant l'adresse destination des données et le registre REG_DMA3SAD le registre correspondant l'adresse de la source à copier. Le fichier en-tête main.h recèle de nombreuses définitions relatives au DMA et au registre REG_DMA3CNT. Voici la déclaration des deux valeurs que nous emploierons :
#define DMA_32NOW DMA_ENABLE | DMA_TIMEING_IMMEDIATE | DMA_32
#define DMA_16NOW DMA_ENABLE | DMA_TIMEING_IMMEDIATE | DMA_16Ces deux declarations servent à exécuter une copie immédiate de valeurs sur 32 ou 16 bits. Nous pouvons en effet ordonner une copie après délai (après rafraîchissement de l'écran.). Les instructions nécessaires à l'exécution d'une copie en mode DMA sont les suivantes :
REG_DMA3SAD = (u32) source;
REG_DMA3DAD = (u32) destination;
REG_DMA3CNT = quantite | DMA_16NOW;Lors de la définition de la valeur du registre REG_DMA3CNT, nous devons préciser le nombre de données à copier. Notre grille contenant uniquement des données sur 8 bits, et la copie ne pouvant se voir réalisée qu'en mode 16 ou 32 bits, nous devons veiller à copier la moitié de la largeur de la grille pour copier une ligne par exemple. Si notre grille fait 256 cases de large, nous écrirons :
REG_DMA3CNT = 128 | DMA_16NOW;La fonction displayPlasma() fait un usage consequent du Direct Memory Access. Vous constaterez que l'affichage du heightmap s'effectue en quatre fois. Le programme présenté offre la chance de pouvoir déplacer l'écran au dessus du terrain. L'algorithme employé pour la génération du terrain a également pour effet de permettre le rebouclage du terrain sur lui-même. La présence des quatre copies s'explique par le cas le plus défavorable d'affichage, c'est à dire quand le point (0, 0) de la grille se trouve au centre de l'écran de la machine.
4. Rafraîchissement▲
La boucle principale du programme affiche les données, attend la fin du rafraîchissement de l'écran puis gère les appuis sur les touches. La gestion des touches du joueur se verra traité plus tard. Pour savoir si la GBA a terminé de balayer l'écran, nous accédons à un registre spécial dont l'adresse se veut 0x04000004.
Le principe consiste à créer une boucle vide dont la condition d'arrêt définit la valeur du registre correspondant à la fin du balayage. Le listing suivant présente la fonction bouclant pour attendre la fin du balayage de l'écran. Le registre vreg se voit déclaré comme volatile en raison du compilateur. Constatant que vreg, présent dans la condition d'arrêt, ne s'avère jamais modifié au sein de la boucle, le compilateur crée une optimisation en réalisant une simple boucle infinie. Le mot-clé volatile indique au compilateur que le contenu de la variable est susceptible de se voir modifié extérieurement au code local.
void waitForVSync()
{
volatile u16* vreg = (volatile u16*) 0x04000004;
while ( *vreg & (1 << 0));
while (!(*vreg & (1 << 0)));
}5. Téléchargements▲
Vous trouverez le code source du programme de génération de terrains dans l'archive cours3.zip.
Version PDF de l'article (67 Ko).
Liens :