Une montagne réalisée à l'aide de l'algorithme du diamant-carré.
Une montagne réalisée à l'aide de l'algorithme du diamant-carré (itérations=4, perturbations=400, lissé).


Si les textures des montagnes dans les jeux vidéos peuvent être crées par des artistes, ce ne sont généralement pas le cas de leurs formes qui peuvent être générées par des algorithmes. En effet, pensez aux jeux où le terrain n'a pas de limite, il faut bien trouver une mthode, un moyen automatique de créer les montagnes sans fins des paysages que vous traversez. Il faut également que cet algorithme créé des montagnes réalistes, naturelles. Le plus simple d'entre eux est celui du diamant-carré. Comment fonctionne t-il ? Une explication pas à pas ci-dessous !

Etape 1: On commence par créer un tableau avec quatre nombres pris au hasard. On a pris ci-dessous des nombres entiers pour que ce soit plus simple mais bien sûr on peut prendre n'importe quel réel avec un signe + ou - ! On obtient ainsi un carré de 2x2.

215 168
384 53


Etape 2: On insère de nouvelles lignes et colonnes entre les nombres pour obtenir, ici, un carré de 3x3
215       168
     
384   53

Etape 3: On va calculer le nombre pour la case vide au centre du carré. Pour cela, on fait la moyenne des nombres qui l'entourent, soit (215+168+384+53)/4=205, et on la perturbe en ajoutant un nombre pris au hasard dans un intervalle, par exemple [-100,100], comme -10. On obtient ainsi la valeur 205-10=195. Les nombres du tableau ci-dessous forment désormais une croix, comme un diamant !
215       168
  195  
384   53


Etape 4: on recommence à faire des carrés de nombres à partir de notre diamant en calculant de la même manière qu'indiqué ci-dessus les nombres pour les cases vides: on fait la moyenne des nombres entourant chaque case vide et on la perturbe. Par exemple pour la case sur la gauche, (215+195+384)/3=264.667, On perturbe un peu avec un nombre pris au hasard dans l'intervalle plus haut pour obtenir 289.
215 232 168
289 195 118
384 242 53

Etapes suivantes: On a désormais un tableau constitué de quatre carrés de quatre nombres et on recommence à partir de l'étape 2, en insérant de nouvelles lignes et colonnes vides entre les nombres que l'on va remplir en refaisant les étapes 3 et 4. On obtient ainsi, à force de répétition, un tableau de nombres de plus en plus grand.
Attribuons maintenant ces nombres aux nœuds d'un quadrillage. Ils désignent alors la hauteur du nœud dans l'espace. Comme par 3 points dans l'espace, il ne peut passer qu'un unique plan, en reliant tous les ensembles de trois nœuds côte à côte par des droites, on obtient ainsi une surface déformée qui ressemble à une montagne pavée de triangles comme dans la simulation ci-dessous.

En faire des montagnes


La simulation ci-dessous est une application de l'algorithme du diamant-carré. Vous pouvez ainsi tester la création de montagnes en appuyant sur le bouton "Redessiner". La case "rotation" permet ou pas de faire tourner le paysage. Certains paramètres sont modifiables et permettent ainsi de mieux comprendre l'algorithme.
  • Nombre d'itérations: nombre de fois où l'algorithme du diamant-carré est répété. Plus il est grand, plus le tableau de nombres est grand et plus le paysage est vaste.
  • Amplitude des perturbations: décide à quel point vous allez perturber les moyennes calculées dans le tableau. Plus elles seront perturbées , plus le paysage aura des pics marqués.
  • Type de perturbations: le choix "Escarpé" fait que la perturbation sera choisie dans un intervalle de nombres [-Amplitude,+Amplitude] comme expliqué plus haut avec [-100,100]. Le paysage sera donc fait de nombreux sommets bien marqués, comme le sont les jeunes montagnes. Mais on peut aussi choisir un paysage plus lisse, comme le sont les vieilles montagnes érodées par le temps, pour un rendu très différent avec moins de pics. Dans ce dernier cas, on peut choisir de prendre une perturbation dans un intervalle de nombres qui se modifie à chaque répétition de l'algorithme comme [-Amplitude,+Amplitude]/(Taille du tableau à la nième répétition).


nombre d'itérations
Amplitude des perturbations: Type de perturbations:

Le code

Vous trouverez ci-dessous le code correspondant à l'algorithme du diamant-carré dans le langage Processing.