Génération fractale de terrains

Le but de ce projet était de générer des terrains 3D grâce à l'algorithme de diamant-carré. Le projet se découpe en 3 parties. Premièrement appliquer l'algorithme afin d'avoir une carte de hauteur. C'est une image en noir et blanc avec chaque pixel qui représente une certaine hauteur (noir étant la plus basse altitude et blanc étant la plus haute). Deuxièmement, créer une carte avec des couleurs à partir de la carte de hauteur. Troisièmement, créer un fichier .obj (objets 3D) à partir de la carte de hauteur et appliquer sur cet objet 3D, la texture de la carte de couleur.

Algorithmes utilisés

J'ai commencé par utiliser l'algorithme de Diamant-carré. Or durant les tests j'ai remarqué que la génération donnait lieu à des paysages côtiers la plupart du temps. J'ai donc cherché une autre méthode de génération de carte de hauteur et j'ai rapidement trouvé le bruit de Perlin.

Diamant-Carré

Le fonctionnement de cet algorithme est plutôt simple mais comporte une restriction de taille : il utilise une matrice carrée de taille $2^{n}+1$. Il fonctionne ainsi :

- Initialise les quatre coins avec des valeurs aléatoires

- Phase diamant : le centre de chaque carré prend pour valeur la moyenne des 4 coins du carré et cette valeur est plus ou moins variée aléatoirement.

- Phase carré : le centre de chaque diamant (losange) prend pour valeur la moyenne des 4 coins et cette valeur est plus ou moins variée aléatoirement.

- Le pas est divisé par deux et l'algorithme reprend à la phase diamant.

Algorithme est décrit succinctement ici, pour plus de détails il existe une page Wikipédia ici. Le problème de cet algorithme est double : Premièrement, les paysages sont très souvent côtiers. Deuxièmement, les variations des nouveaux points ne sont pas réalistes. Si on regarde dans la nature, les variations d'altitudes sont fortes dans les montagnes (pics etc...) et plus faible à moyenne et basse altitude (plaines, collines). Pour essayer de rendre la génération naturelle j'ai donc augmenté les variations en fonction de la hauteur du point. Pour ce qui est de la génération "côtière" une possibilité serait d'augmenter la grille et de fixer la valeur de plus de points au départ. De plus, j'ai ajouté un paramètre appelé facteur de dénivelé qui permet de rendre la génération plus ou moins accidentée.

Voici quelques exemples de cartes de hauteur grâce à l'algorithme de Diamant-carré. A gauche un facteur de dénivelé faible et à droite, un facteur de dénivelé plus élevé.

Bruit de Perlin

Le bruit de Perlin est une texture procédurale beaucoup utilisée pour ajouter du réalisme dans les générations de mondes ou de textures en informatique. J'ai eu l'idée de l'utiliser en lisant l'article Playing with Perlin Noise: Generating Realistic Archipelagos Cet algorithme a beaucoup de paramètres qui permettent de grandement varier la génération et ce, de manière très précise. Pour l'utiliser, j'ai importé le module noise sur python. J'ai ensuite employé les paramètres suivants pour générer mes cartes :

- shape Un tuple de 2 entiers qui représentent les dimensions de l'image.

- scale Un flottant qui représente l'échelle utilisée. Plus il est élevé, plus on "zoome" sur l'image.

- octaves Un entier qui représente le nombre de couches de détails. Par exemple l'octave 1 serait la forme globale de la montagne, le 2 serait les collines, le 3 serait les gros rochers sur cette montagne et le 4 serait les petits rochers. Plus il y a d'octaves, plus la génération semble détaillée.

- persistence Un flottant qui représente l'impact que les octaves ont sur la forme générale.

- lacunarity Un flottant qui représente la quantité de détails pris en compte pour les octaves.

- seed Un entier qui représente la graine de génération.

- facteur Un flottant qui représente le facteur de dénivelé (un paramètre qui ne fait pas partie de noise, que j'ai ajouté moi-même)

Comme des images valent mieux que des mots, prenons une carte générée grâce aux paramètres suivants (le fonctionnement de hauteur_ocean sera abordé dans la partie couleur) :

shape=(200,200),scale=50,octaves=5, persistence=0.5,lacunarity=2.0,seed=0,hauteur_ocean=0,facteur_denivele=0.10

Sur l'image de gauche, scale a diminué (31) sur celle de droite, scale a augmenté (91)

Sur l'image de gauche, octave a diminué (2) sur celle de droite, octave a augmenté (7)

Sur l'image de gauche, persistence a diminué (0.20) sur celle de droite, persistence a augmenté (0.60)

Sur l'image de gauche, lacunarity a diminué (1.46) sur celle de droite, lacunarity a augmenté (2.28)

Sur l'image de gauche, facteur a diminué (0.04) sur celle de droite, facteur a augmenté (0.15)

Et enfin, si on change la seed à 2 voici le résultat :

Couleurs

Pour gérer les couleurs, j'ai commencé par une méthode très simple : choisir la couleur en fonction de l'altitude. Cependant, cela donnait un effet cartoon mais manquait de détails. J'ai donc ensuite créé une nouvelle version en changeant de méthode pour les terres (l'océan reste cartoonesque). J'ai calculé la couleur en fonction de la "pente" du pixel. Cette pente est relative à ses 8 voisins. J'ai aussi ajouté un paramètre à la création de mes cartes pour varier la hauteur de l'océan. Ce changement affecte uniquement les couleurs et non la carte de hauteur. Voici donc quelques exemples avec les deux méthodes :

via l'altitude

via la pente

Carte 3D

Pour la gestion des cartes en 3D j'ai utilisé le format OBJ. Pour les cartes, j'ai découpé le fichier en 3 parties:

- Les coordonnées de points.
- Les coordonnées de texture (entre 0 et 1)
- Les faces du maillage

Les coordonnées de points (v) en x et y sont les mêmes que pour l'image mais en z ce sont les valeurs des pixels sur la carte de hauteur. ex : v x z y
Les coordonnées de texture (vt) en x et y sont calculées ainsi : x_img/X et y_img/Y avec x_img et y_img les positions dans l'image et X et Y les dimensions de l'image. Il n'y a pas de coordonnées en z. ex : vt x y
Les faces du maillage (f) sont représentées par un ensemble de points formant un carré ABCD. ex : f A/A B/B C/C D/D
Comment visualiser les fichiers OBJ sur blender ?
- Lancer Blender et créer un nouveau projet (général)
- Supprimer le cube d'origine (cliquer dessus et presser la touche x)
- importer le fichier obj et faire un copier-glisser de carte_couleur

- Sélectionner l'objet map (en haut à droite) et ne pas hésiter à dézoomer pour voir la carte 3D.
- Aller dans l’onglet material properties (sphère avec des triangles rouges)
Puis sélectionner les mêmes paramètres que sur l'image suivante (les points rouges indiquent ce qu'il faut changer).
Vous pouvez choisir le visuel que vous préférez entre "closest" et "cubic".

Puis en haut à droite sélectionner Viewport Shading pour voir la texture.

Diamant-Carré

exemple sans shaders (ciel et lumière) :

exemple avec shaders :

Bruit de Perlin

exemple sans shaders (ciel et lumière) :

exemple avec shaders :

Rivières

C'est en lisant cet article que j'ai eu l'idée d'ajouter des rivières à la génération. Or contrairement à cet article, ma carte n'est pas faite de polygones différents les uns des autres. J'ai donc pensé à un autre algorithme qui fonctionne ainsi :
1- L'algorithme parcourt chaque pixel de la carte, chaque pixel a une certaine probabilité de devenir un début de rivière.
2- Si une rivière est commencée, alors l'algorithme regarde tous les voisins du pixel sur lequel le pointeur est positionné (au début le pointeur est sur le pixel "source" qui est bleu).
3- L'algorithme choisit ensuite le pixel le plus bas, place le pointeur dessus et le colore en bleu.
4- L’algorithme continue ainsi jusqu’à ce qu'il arrive à la hauteur de l'océan ou qu'il n'y ait pas de pixel plus bas.
5- La rivière est tracée en entier, l'algorithme continue de parcourir les pixels de la carte.

Or cet algorithme peut être amélioré notamment en simulant une érosion si aucun pixel plus bas n'est trouvé parmi les voisins. Dans ce cas, on prend le plus bas des pixels possibles (sauf celui du pointeur) et on diminue sa hauteur de 1 et on reprend à l'étape 2.

Je me suis alors heurté à un bug que je n'ai pas encore réussi à fixer. Certaines rivières s'arrêtent toutes seules en plein milieu d'une pente sans aucune raison apparente. Sur l'exemple qui suit, la première image est une vision globale et la suivante est une vision plus proche. Nous pouvons constater que la rivière devrait suivre la flèche bleue, or ce n'est pas le cas.

Si ce bug est fixé, mes objectifs seront les suivants :
- Lorsqu'une rivière B croise une rivière A, la rivière B continue à côté de la A de manière à donner une rivière plus large.
- Faire en sorte de remplir des bassins et créer des lacs.

Code

J'ai réalisé ce projet sous python 3.8 avec les modules suivants : random, PIL, noise, numpy et tkinter.
Le code est entièrement disponible sur GitHub ici. Voici l'interface graphique du générateur :

Et voici comment est structuré le projet :
Les flèches noires symbolisent l'importation de fonctions et les vertes la création de fichier
map_3D.py n'est pas utile à l'interface mais j'ai développé les fonctions de map_3D dans le but de générer un fichier obj et sa texture sans interface.

Sources & inspirations

Polygonal Map Generation for Games
Generating fantasy maps
Azgaar, un générateur de carte
Un rapide tutoriel blender pour ajouter un ciel