1. Introduction

L'algorithme DiamondSquare permet de générer des terrains de manière aléatoire. Il est relativement simple et ne nécessite pas des heures d'étude pour le comprendre. La version vue est celle de base, on peut y ajouter des améliorations comme l'insertion de détails lors de zoom, ...

Pour notre projet, nous allons utiliser le langage C++ et la bibliothèque OpenGL. Nous supposons cela acquis, du moins les bases, car le projet ne nécessite pas de connaissances approfondies. L'Interface est développée sous QT4 et est donc compatible Linux/Windows.

Le tutoriel va s'articuler autour de 2 parties : l'explication de l'algorithme en général puis l'explication de l'implémentation en C++.

2. Explication de l'algorithme

2.1. Une petite explication

L'algorithme DiamondSquare, comme son nom l'indique, se base sur 2 phases : la phase du carré et la phase du diamant. Il s'agit d'itérer ces 2 phases jusqu'à calculer tous les points de la matrice représentant le terrain 3D.

En effet, la largeur de la matrice représente les abscisses, la longueur les ordonnées et enfin chaque "case" de la matrice représente la hauteur relative du point dont on vient de décrire les 3 composantes pour le situer dans un repère : pour accéder à une case de la matrice on fait tab[x][y] = z; ce qui indique que les 3 coordonnées sont présentes.

Pour mieux comprendre le fonctionnement, je propose d'étudier un exemple.

2.2. Un exemple

Prenons un exemple simple pour expliquer l'algorithme. Soit une matrice 5X5 :

Image non disponible

La phase du carré consiste à élever le centre du carré d'une valeur aléatoire (le point en rouge) :

Image non disponible

La phase du diamant consiste à élever le centre de chaque losange formé par le centre et les coins du carré précédent d'une valeur aléatoire (les points en bleu). On peut constater déjà qu'on se retrouve confronté à un problème : il n'y a pas quatre points complet pour former le diamant. Il faut donc tenir compte du cas particulier des bords :

Image non disponible

On réitère avec les carrés obtenus(vert),puis les diamants(orange) et ainsi de suite jusqu'à parcourir l'ensemble de la matrice:

Image non disponible

On obtient donc l'algorithme suivant :

 
Sélectionnez

espace = Largeur;
tant que espace > 1 faire
{
  espace = espace / 2;
 
  pour chaque carre de largeur espace faire
  {
    etape du carre;
  }
 
  pour chaque diamant de largeur espace faire
  {
    etape du diamant;
  }
}
		

2.3. Prérequis

Comme vous pouvez le constater, il faut obligatoirement que la matrice ait pour largeur quelquechose du type 2^n+1, sinon le calcul du centre serait faux, et l'algorithme ne marcherait pas.

En effet, on divise par 2 la largeur d'un carré ou d'un diamant à chaque étape ce qui explique le 2^n. De plus, on choisit le centre et pour que ce centre soit déterminé, il faut que l'on ait le même écart à "gauche" et à "droite" du centre. Cela n'est possible qu'avec une largeur impaire, d'où le 2^n+1.

2.4. Phase du carré

La phase du carré calcule la moyenne des 4 points formant le carré. Lors de cette phase, on est positionné sur le centre ayant pour coordonnées (x, y). Sur un carré (a, b, c, d), on retrouve les coordonnées suivantes :

Image non disponible
  • a = (x-espace, y-espace)
  • b = (x-espace, y+espace)
  • c = (x+espace, y+espace)
  • d = (x+espace, y-espace)

Mais il faut faire attention aux limites de la matrice. Il faut tester les coins du carré pour que leurs coordonnées soient comprises entre 0 et largeurMatrice-1).

2.5. Phase du diamant

La phase du diamant calcule la moyenne des 4 points formant le losange (représentant le diamant). on est positionné sur le centre qui a pour coordonnées : (x, y). Sur un diamant (a, b, c, d), on retrouve les coordonnées suivantes :

Image non disponible
  • a = (x-espace, y)
  • b = (x, y+espace)
  • c = (x+espace, y)
  • d = (x, y-espace)

Il faut encore faire attention aux limites de la matrice !

2.6. hauteur pseudo aléatoire

Comme le terrain est aléatoire, la hauteur d'un point doit être choisit au hasard. Néanmoins, pour ne pas avoir n'importe quoi, il faut quand même contrôler sa valeur. On parle alors de hauteur pseudo aléatoire car cela n'est pas totalement dû au hasard.

Tout d'abord, la hauteur d'un point est calculée en fonction de la moyenne de la hauteur des points que l'algorithme a utilisé pour l'obtenir.

On y ajoute une valeur aléatoire (supposée pure), à laquelle on applique un coefficient de lissage pour ne pas avoir un terrain en dents de scie. De plus, on multiplie à cette valeur alétoire pure, l'espace entre le point cible et les points sources, afin de garder la cohérence du terrain. Voici donc la formule pour obtenir la hauteur :

 
Sélectionnez

hauteur = moyenne() + random() * espace * lissage
		

Le coefficient de lissage est fractionnaire et donc inférieur à 1. Plus la valeur est élevée, moins le terrain sera lisse :

Image non disponible
Lissage à 0.1
Image non disponible
Lissage à 0.5
Image non disponible
Lissage à 0.9

3. Explication du code source

3.1. Architecture Générale

Le but de l'application est d'interfacer la classe générant le terrain avec une interface. L'interface est faite en QT. Voici la liste des classes :

  • CDiamondSquare : classe effectuant la génération du terrain
  • DiamondSquareWidget : classe représentant le composant effectuant l'affichage du terrain. Elle hérite de QGLWidget
  • DiamondSquareApp : classe héritant de Ui::MyDialog qui représente l'interface

3.2. Explication de la classe CDiamondSquare

3.2.1. Interface

L'utilisateur ne dispose que du constructeur, de la génération, du changement de mode et de la méthode effectuant l'affichage du terrain. L'objectif de cette organisation est de ne pas compliquer l'utilisation de la classe.

L'ordre d'utilisation de la classe est imposé :

  1. Appel du constructeur
  2. Appel de la méthode Generate
  3. Appel de la méthode Draw

La méthode ChangeMode est appelée pour permettre de passer du mode filaire au mode rempli et vice-versa.

3.2.2. Mécanique interne

Nous allons expliquer la méthode Generate plus en détails. Elle fait appel à 5 méthodes qui sont cachées à l'utilisateur :

  • Randomize qui génère un nombre aléatoire
  • SquareStep qui effectue le calcul de la moyenne pour la phase du carré
  • DiamondStep qui effectue le calcul de la moyenne pour la phase du diamant
  • Init qui reserve la mémoire pour la matrice représentant le terrain
  • SetColor qui applique la couleur en se basant sur la hauteur du point

Voici la partie importante de la méthode qui correspond à à l'algorithme général vu précédemment:

 
Sélectionnez

// Indice de bout de matrice
unsigned int unSpacing = m_unSize - 1;
 
while (unSpacing > 1) 
{ 
  int unHalfSpacing = unSpacing / 2;
 
  // Etape du carré
  for (unsigned int unI = unHalfSpacing; unI < m_unSize; unI += unSpacing) 
  { 
    for (unsigned int unJ = unHalfSpacing; unJ < m_unSize ; unJ += unSpacing ) 
    { 
      m_vectPoints[unI][unJ] = SquareStep(unI, unJ, unHalfSpacing ) + Randomize() * unSpacing * m_fVariability; 
    } 
  } 
 
  // Etape du diamant
  for (unsigned int unI = 0; unI < m_unSize; unI += unHalfSpacing) 
  { 
    unsigned int unJStart = ((unI/unHalfSpacing) % 2 == 0 ) ? unHalfSpacing : 0; 
 
    for (unsigned int unJ = unJStart; unJ < m_unSize ; unJ += unSpacing ) 
    { 
      m_vectPoints[unI][unJ] = DiamondStep(unI, unJ, unHalfSpacing ) + Randomize() * unSpacing *  m_fVariability;
    } 
  } 
 
  // Adaptation de l'écart 
  unSpacing = unHalfSpacing;
} 
		  

3.3. Code source

Le code source disponible est compilé sous linux avec QT en version 4.3. QT étant multiplateforme, il est possible de compiler le code sous Windows mais je n'ai pas modifié le makefile en conséquence.

J'ai ajouté le doxyfile permettant de générer la documentation "doxygen" de la classe CDiamondSquare.

Pour compiler le code source, il faut se positionner dans le répertoire DiamondSquareIHM, exécuter la commande qmake puis la commande make. L'executable sera le fichier DiamonSquareIHM obtenu.

Source

4. Capture d'écran

Voici une capture d'écran de l'IHM obtenu au lancé, avec les paramètres par défaut :

Image non disponible

5. Conclusion

En conclusion, l'algorithme DiamondSquare n'est pas très difficile à mettre en oeuvre mais il faut etre un minimum rigoureux car des erreurs d'étourderies sont vites arrivées.

Il est évident que des améliorations peuvent être apportées en jouant sur les détails et les calculs. Par exemple, si une zone est affichée, on ne calcule que cette zone, ... Mais cela, je vous laisse le découvrir par vous même. Bonne prog !

6. Remerciements

Je tiens à remercier FearYourSelf, Laurent Gomila, Nico-Pyright, Farscape et mon professeur de mathématique qui m'a fait découvrir cet algorithme : Adib Rahmouni.