Utilisation de l'algorithme DiamondSquare pour la génération de terrain

L'algorithme DiamondSquare, comme son nom l'indique, se base sur deux phases : la phase du carré et la phase du diamant. Il s'agit d'itérer ces deux 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 trois 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 trois coordonnées sont présentes.

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

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

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

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 complets pour former le diamant. Il faut donc tenir compte du cas particulier des bords :

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:

On obtient donc l'algorithme suivant :

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;
  }
}

Comme vous pouvez le constater, il faut obligatoirement que la matrice ait pour largeur quelque chose 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.

La phase du carré calcule la moyenne des quatre 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 :

• 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).

La phase du diamant calcule la moyenne des quatre 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 :

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

Comme le terrain est aléatoire, la hauteur d'un point doit être choisie 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 pseudoalé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ée 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éatoire 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 :

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 :

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.

III-B-1. Interface▲

III-B-2. Mécanique interne▲

// 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;
}

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'exécutable sera le fichier DiamonSquareIHM obtenu.

Source