URL: https://linuxfr.org/news/je-cree-mon-jeu-video-e10-generation-procedurale-de-carte-partie-1 Title: Je crée mon jeu vidéo E10 : génération procédurale de carte (partie 1) Authors: rewind Benoît Sibaud, palm123, ZeroHeure et tuiu pol Date: 2014年03月03日T18:07:53+01:00 License: CC By-SA Tags: gamedev, carte, bruit et érosion Score: 112 «Je crée mon jeu vidéo» est une série d'articles sur la création d'un jeu vidéo, depuis la feuille blanche jusqu'au résultat final. On y parlera de tout : de la technique, du contenu, de la joie de voir bouger des sprites, de la lassitude du développement solitaire, etc. Vous pourrez suivre cette série grâce au [tag gamedev](http://linuxfr.org/tags/gamedev/public). Dans l'[épisode 09](http://linuxfr.org/news/je-cree-mon-jeu-video-e09-techniques-de-c-11-appliquees-au-systeme-a-entites), on a vu comment C++11 procurait des constructions bien pensées qu'on pouvait utiliser dans les systèmes à entités. Cette fois, on attaque dans le dur à travers un double épisode qui va nous permettre de générer une carte pour du RPG. Dans la première partie, on va voir comment générer une «[carte d'altitude](http://en.wikipedia.org/wiki/Heightmap)» (_heightmap_). On va passer en revue plein de techniques qui permettent d'arriver à ce résultat. Avec tout plein d'images pour illustrer. Attention les yeux ! ---- [Akagoria, la revanche de Kalista](http://www.akagoria.org/) [Le tag gamedev](http://linuxfr.org/tags/gamedev/public) [MapMaker](https://github.com/jube/mapmaker) ---- ![Exemple de carte finale](http://www.akagoria.org/img/E10/final_map_shaded.png) # Généralités sur les cartes d'altitude Une carte d'altitude est une image en niveaux de gris qui indique la hauteur d'une surface virtuelle représentant un terrain de jeu. Généralement, le noir indique une altitude basse et le blanc indique une altitude haute. En pratique, on utilise une matrice où chaque case de la matrice représente un pixel de la carte. La matrice contient généralement un flottant, normalisé entre 0 et 1, ou entre -1 et 1. Chez moi, ça sera entre 0 et 1. Les cartes en niveaux de gris, c'est marrant mais pour vous en mettre vraiment plein les yeux, je vais plutôt générer des cartes en couleur en utilisant le gradient suivant (0 à gauche, 1 à droite, le niveau de la mer étant à 0,5) : ![Un gradient pour les cartes d'altitude](http://www.akagoria.org/img/E10/ramp.png) Trouver un gradient correct est assez difficile. Et ce n'est pas mon sens du graphisme inné qui m'aide beaucoup. J'ai [récupéré ce gradient sur un site](http://www.blitzbasic.com/codearcs/codearcs.php?code=2415), j'aurais pu en choisir d'autres mais je les trouvais moins jolis. Si vous avez des talents pour améliorer ce gradient, n'hésitez pas à apporter votre aide. L'idéal quand on génère ce genre de carte, c'est de pouvoir l'affiner à l'envie. En pratique, on essaie de générer un [terrain fractal](http://fr.wikipedia.org/wiki/Terrain_fractal), c'est-à-dire un terrain qui présente un comportement fractal. Affiner le terrain (en pratique, avoir une carte de plus grande taille) ne va pas changer la physionomie générale du terrain, juste sa précision. Ensuite, une fois que le processus de génération est en place, on cherche à avoir des cartes intéressantes, c'est-à-dire avec du relief mais qu'on puisse jouer. Pour cela, on va définir deux scores pour nos cartes, le score d'érosion et le score de jouabilité. Ces deux définitions sont issues de l'article [Realtime Procedural Terrain Generation](http://oddlabs.com/download/terrain_generation.pdf) de Jacob Olsen, écrit en 2004. C'est un excellent article qui m'a beaucoup servi, notamment pour les algorithmes d'érosion décrits plus loin. ## Comment mesurer l'importance du relief ? Pour mesurer le relief, on utilise le __score d'érosion__. Le principe est, pour chaque case, de calculer la pente maximale, c'est-à-dire la différence d'altitude en valeur absolue, par rapport aux voisins. On ne considère que les voisins parallèles aux axes, c'est-à-dire les voisins du haut, de droite, du bas et de gauche. Ensuite, on calcule la moyenne de ces pentes et l'écart-type, puis enfin, le [coefficient de variation](http://fr.wikipedia.org/wiki/Coefficient_de_variation), c'est-à-dire le rapport entre l'écart-type et la moyenne. C'est ce coefficient de variation qu'on appelle score d'érosion. Un score d'érosion de 0 indique une carte plate. Plus le score est élevé, plus il y a de relief. En pratique, dès qu'on atteint 1, on constate des cartes avec pas mal de relief. Tout au long de cet article, j'essaierai de donner les scores d'érosion des différentes cartes générées pour vous donner un ordre d'idée. Par exemple, pour la carte du début, le score d'érosion est de 0,970156. On constate qu'elle présente pas mal de relief, avec de grands plateaux qui permettent de délimiter des zones intéressantes. ## Comment mesurer la pertinence d'une carte ? Pour mesurer la pertinence d'une carte, c'est-à-dire sa jouabilité, l'idée est de regarder si les unités peuvent se déplacer et les bâtiments peuvent être placés sans encombre. En effet, on va considérer qu'une pente trop importante ne permet pas aux unités de passer ou aux bâtiments d'être placés. En plus, on considère qu'une unité a une certaine taille, de même que les bâtiments. En pratique, on va d'abord calculer une carte binaire qui indique les cases qui ont une pente inférieure à _Tu_, la pente maximale franchissable par les unités, puis on va enlever de cette carte binaire toutes les cases qui ne peuvent pas contenir un carré de côté _Nu_, la taille des unités. Enfin, on calcule la plus grande zone connectée dans cette carte ce qui donne une _carte d'unités_. Pour la suite, on a pris _Nu=1_. Ensuite, on fait de même avec les bâtiments, on prend une pente _Tb_ maximum (généralement inférieure à _Tu_ parce qu'un bâtiment supporte moins bien la pente) et une taille _Nb_ (généralement supérieure à _Nu_ parce qu'un bâtiment prend plus de place qu'une unité) et on calcule la carte binaire de la même manière, sauf pour la plus grande zone connectée (les bâtiments ne se déplacent pas). Enfin, on garde dans cette deuxième carte les zones accessibles dans la carte d'unité, ce qui donne la _carte de bâtiments_. Pour la suite, on a pris _Nb=9_. Pour calculer le __score de jouabilité__, on va calculer la proportion de cases accessibles dans la carte d'unités, ainsi que la proportion de cases disponibles dans la carte de bâtiments. Et on va les multiplier par le score d'érosion pour obtenir le score de jouabilité. On comprend alors qu'une carte plate donnera des cartes d'unités et de bâtiments excellente mais un score d'érosion nul. Inversement, si on a trop de pente partout, on aura des cartes d'unités et de bâtiments mauvaises, voire très mauvaises, mais un score d'érosion excellent. Dans les deux cas, le score de jouabilité est mauvais. Il faut donc trouver un compromis entre les deux. Voici la carte d'unités associée à la carte de début. ![Carte d'unités](http://www.akagoria.org/img/E10/unit3.png) Voici la carte de bâtiments associée à la carte du début. ![Carte de bâtiments](http://www.akagoria.org/img/E10/building3.png) Le score de jouabilité pour cette carte est de 0,233147. Avec un score d'unité de 0,834806 (ce qui signifie que 83% des terres émergées sont accessibles aux unités (NdM : capables de voler ou d'y accéder par la mer, les terrains n'étant pas forcément tous accessibles uniquement par la terre) et un score de bâtiment de 0,287874 (ce qui signifie qu'on peut placer des bâtiments sur 28% des terres émergées), on a une carte tout à fait jouable. ## Comment afficher une carte avec du relief ? Avant de continuer, il faut expliquer que les cartes que je vais présenter sont représentées avec un [relief ombré](http://en.wikipedia.org/wiki/Cartographic_relief_depiction#Shaded_relief). Ça a l'air simple mais ça ne l'est pas. Sans relief ombré, la carte ressemblerait à ça. ![Exemple de carte finale sans relief](http://www.akagoria.org/img/E10/final_map.png) Après beaucoup de recherches, j'ai utilisé l'[algorithme simple](https://github.com/amitp/mapgen2/blob/master/mapgen2.as#L849) utilisé dans le [tutorial de génération de cartes polygonales d'Amit Patel (Red Blog Games)](http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/). J'ai juste modifié un peu les couleurs. Plutôt que d'utiliser du gris, j'ai utilisé un jaune très léger pour le côté soleil et un violet très sombre pour le côté ombre. J'ai aussi conservé la convention de la lumière venant du nord-ouest (ce qui est impossible en réalité mais aide à discerner les trous des bosses). Pourquoi est-ce difficile d'avoir un bon relief ombré ? Parce que sur les cartes réelles, cet ombrage est fait à la main, c'est un art en tant que tel chez les cartographes. Il existe des algorithmes pour le faire automatiquement mais il est difficile de les trouver écrits de manière claire, et leur résultat est souvent moins bon que les tracés à la main. Dans ma longue route à la recherche d'informations, voici quelques liens intéressants sur lesquels je suis tombé. Tout d'abord, deux sites avec plein d'informations : [Shaded Relief](http://www.shadedrelief.com/) et [Relief Shading](http://www.reliefshading.com/). On y voit plein d'exemples de cartes ombrées à la main. On a également accès à tout un tas d'articles sur les techniques à utiliser, dont beaucoup utilisent le logiciel propriétaire de traitement d'image leader du marché. Pour les allergiques au logiciel propriétaire, Wikipédia francophone propose [un tutoriel pour créer un relief ombré](http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Atelier_graphique/Didacticiels_cartographiques/Cr%C3%A9er_un_relief_ombr%C3%A9) avec des outils libres. Cette petite digression étant finie, passons aux choses sérieuses. # Bruit cohérent Une carte d'altitude est par nature constituée de bruit cohérent. On peut [définir le bruit cohérent](http://libnoise.sourceforge.net/coherentnoise/index.html) comme une fonction (informatique) de R^n dans R avec les propriétés suivantes : - les mêmes valeurs d'entrée produisent la même valeur de sortie - un petit changement dans les valeurs d'entrée produit un petit changement dans la valeur de sortie - un gros changement dans les valeurs d'entrée produit un changement aléatoire dans la valeur de sortie Dans notre cas, nous voulons produire une carte en deux dimensions (n=2), donc nous nous intéresserons uniquement aux techniques pour produire du bruit en deux dimensions. Beaucoup de ces techniques s'adaptent à des dimensions supérieures. Parmi les algorithmes de génération de bruit qu'on rencontre souvent, il y a deux grandes classes d'algorithmes : - les générateurs à base de [bruit de Perlin](http://en.wikipedia.org/wiki/Perlin_noise) (au sens large) - les générateurs à base de placement de point ## Bruit de Perlin Dans la catégorie bruit de Perlin, je classe toute une série de bruits qui ne sont généralement pas mis sous ce vocable mais qui utilisent globalement une même procédure. Le vrai bruit de Perlin utilise le bruit à base de gradient, comme on le verra par la suite. La procédure dont je parle est parfois appelée [fractional brownian motion](http://en.wikipedia.org/wiki/Fractional_Brownian_motion), ou fBm pour les intimes. Je l'ai nommée plus simplement [`fractal`](https://github.com/jube/mapmaker/blob/master/src/lib/fractal.cc). Elle consiste, à partir d'une fonction de bruit «simple» à combiner plusieurs _octaves_ de différentes _amplitudes_ et de différentes _fréquences_. Plus précisément, pour chaque octave supplémentaire, on divise par deux l'amplitude, on multiplie par deux la fréquence, et on additionne toutes ces octaves. On peut appliquer cette technique à plusieurs types de bruit que nous allons détailler. ### Bruit à base de valeur (value noise) Le principe du [bruit à base de valeur](http://en.wikipedia.org/wiki/Value_noise) est simple. On génère une grille dont les coordonnées entières contiennent une valeur aléatoire fixe. Ensuite, pour un point (x,y), on regarde dans quelle case de la grille se trouve le point (éventuellement en répétant la grille de valeurs), puis on détermine les coordonnées (rx,ry) de ce point dans la case (c'est-à-dire qu'on enlève la partie entière de chaque coordonnée). ![Grille](http://www.akagoria.org/img/E10/grid.png) Ensuite, on effectue plusieurs interpolations avec les quatre points situés aux coins de la case de la grille correspondante. On fait d'abord une interpolation entre la valeur en A et la valeur en B avec comme coefficient rx, puis entre la valeur en D et la valeur en C avec la valeur rx, puis enfin entre les deux valeurs obtenues avec la valeur ry. Comment interpoler deux valeurs ? Généralement, on utilise une [interpolation linéaire](http://fr.wikipedia.org/wiki/Interpolation_lin%C3%A9aire). On utilise une fonction appelée traditionnellement `lerp`, définie de la manière suivante : ```c double lerp(double v0, double v1, double t) { return v0*(1-t)+v1*t; } ``` Pour _t=0_, on aura _v0_ et pour _t=1_, on aura _v1_. Et entre les deux, on aura une valeur intermédaire. Mais dans le cas de bruit, ça ne donne pas de beaux résultats. On va donc lisser la courbe d'interpolation et utiliser une fonction qu'on va appliquer à t : ```c double lerp(double v0, double v1, double t) { t = g(t); return v0*(1-t)+v1*t; } ``` On va choisir la fonction g pour qu'elle ait de bonnes propriétés. En particulier, si on ne veut pas d'angles, on va plutôt choisir une fonction dont la dérivée en 0 et en 1 est nulle. Si on prend une fonction polynômiale alors, on tombe sur un polynôme de degré 3 : -2 x^3 + 3 x^2. Si on veut en plus que la dérivée seconde soit nulle en 0 et en 1, on tombe sur un polynôme de degré 5 : 6 x^5 - 15 x^4 + 10 x^3. On peut aussi choisir une fonction trigonométrique comme (1 - cos(pi * x)) * 0.5 mais cette fonction se rapproche beaucoup de notre polynôme de degré 3. Voici l'ensemble de ces fonctions dessinées sur un même graphe : ![Interpolations](http://www.akagoria.org/img/E10/curve.png) Voici le résultat sur les mêmes valeurs : linear|cubic|quintic|cosine ------|-----|-------|------ ![linear](http://www.akagoria.org/img/E10/mini_value_linear.png)|![cubic](http://www.akagoria.org/img/E10/mini_value_cubic.png)|![quintic](http://www.akagoria.org/img/E10/mini_value_quintic.png)|![cosine](http://www.akagoria.org/img/E10/mini_value_cosine.png) Généralement, le polynôme de degré 3 donne des résultats satisfaisants. On garde donc celui-ci : ![Bruit à base de valeur](http://www.akagoria.org/img/E10/value_noise.png) Et avec 10 octaves, on obtient une carte tout à fait convenable (score d'érosion : 0,429078) : ![Bruit à base de valeur](http://www.akagoria.org/img/E10/value_noise_with_fractal.png) Voir l'[implémentation du bruit à base de valeur](https://github.com/jube/mapmaker/blob/master/src/lib/value_noise.cc). ### Bruit à base de gradient (gradient noise) Le [buit à base de gradient](http://en.wikipedia.org/wiki/Gradient_noise) est le vrai bruit de Perlin, décrit dans [Making Noise](http://www.noisemachine.com/talk1/), que [Ken Perlin](http://en.wikipedia.org/wiki/Ken_Perlin) a inventé pour le [film Tron](http://fr.wikipedia.org/wiki/Tron) et qu'il a par la suite décrit en 1985. C'est une amélioration du bruit à base de valeur. L'idée au départ n'est pas de créer des cartes d'altitude mais des textures. Et de manière générale, on peut appliquer beaucoup des techniques vues ici pour créer des [textures procédurales](http://libnoise.sourceforge.net/examples/textures/index.html) assez bluffantes. Mais revenons à notre bruit à base de gradient. Par rapport au bruit à base de valeur, on ne définit pas des valeurs (aux coordonnées entières de la grille) mais des vecteurs, également appelés gradients. Ensuite, pour déterminer une valeur aux quatre coins de la case, on calcule un [produit scalaire](http://fr.wikipedia.org/wiki/Produit_scalaire). Pour le point A, on calcule le produit scalaire entre le gradient défini au point A et le vecteur PA. Et pareil pour les trois autres. Enfin, on interpole ces quatre valeurs comme pour le bruit à base de valeurs. Le résultat est meilleur qu'avec le bruit à base de valeur, où on distinguait bien les contributions des quatre coins. Maintenant, on a des formes plus variées : ![Bruit à base de gradient](http://www.akagoria.org/img/E10/gradient_noise.png) Le résultat avec 10 octaves n'est pas mal du tout (score d'érosion : 0,433705) : ![Bruit à base de gradient](http://www.akagoria.org/img/E10/gradient_noise_with_fractal.png) Voir l'[implémentation du bruit à base de gradient](https://github.com/jube/mapmaker/blob/master/src/lib/gradient_noise.cc). ### Bruit à base de simplexe (simplex noise) Le [bruit à base de simplexe](http://en.wikipedia.org/wiki/Simplex_noise) est une évolution du bruit à base de gradient et proposé par le même Ken Perlin. Le problème du bruit à base de gradient est qu'il requiert O(2^n) interpolation pour un bruit à n dimensions. Ceci vient du fait qu'on utilise un [hypercube](http://fr.wikipedia.org/wiki/Hypercube) qui a 2^n sommets. Pour avoir moins de points, on va utiliser un objet à n dimensions qui possède le moins de points possible : c'est ce qu'on appelle un [simplexe](http://fr.wikipedia.org/wiki/Simplexe). En dimension 2, c'est un triangle. En dimension 3, c'est un tétraèdre. Et ainsi de suite. De manière générale, c'est un objet à n+1 points. Ensuite, l'[implémentation proposé par Ken Perlin](http://www.csee.umbc.edu/~olano/s2002c36/ch02.pdf) est assez complexe. La difficulté consiste à calculer le triangle dans lequel on se situe. L'idée est d'appliquer une sorte de [transvection](http://fr.wikipedia.org/wiki/Transvection) qui va transformer nos triangles en demi-carrés. De cette manière, savoir si on est dans le demi-carré du dessus ou du dessous revient à savoir si _rx_ est plus grand ou plus petit que _ry_. Dernière subtilité, c'est qu'on ne va pas avoir d'interpolations, ni de gradients tirés au hasard. Chaque coin va apporter une contribution qu'on va ajouter les unes aux autres. Ceci est fait pour accélérer la génération. Au final, le résultat est plutôt convaincant : ![Bruit à base de simplexe](http://www.akagoria.org/img/E10/simplex_noise.png) Et avec 10 octaves, on observe des artefacts obliques. Je ne sais pas si c'est une erreur dans l'implémentation, mais ça se pourrait parce que ce type de bruit est supposé donner de bons résultats (score d'érosion : 0,452591) : ![Bruit à base de simplexe](http://www.akagoria.org/img/E10/simplex_noise_with_fractal.png) Voir l'[implémentation du bruit à base de simplexe](https://github.com/jube/mapmaker/blob/master/src/lib/simplex_noise.cc). ### Bruit à base de cellule (cell noise) Dernier bruit de la série, le [bruit à base de cellule](http://en.wikipedia.org/wiki/Worley_noise). Il porte aussi le nom de bruit de Worley (du nom de son inventeur, Steven Worley) ou de bruit de Voronoï (parce que visuellement, on observe un [diagramme de Voronoï](http://fr.wikipedia.org/wiki/Diagramme_de_Vorono%C3%AF)). L'algorithme général est bien différent de ce qu'on a pu voir jusqu'ici. L'idée est de générer n points _Qi_ dans l'espace, puis pour un point P, on définit les fonctions _Fi_ qui représentent la distance au i-ème point le plus proche parmi _Qi_. Ensuite, le bruit est défini par la somme _C1_ * _F1(P)_ + _C2_ * _F2(P)_ + ... + _Cn_ * _Fn(P)_ où les _Ci_ sont des constantes prédéfinies. Suivant les constantes qu'on choisit et la fonction utilisée pour la distance, on obtient des résultats assez différents les uns des autres. On a le choix entre prendre la [distance euclidienne](http://fr.wikipedia.org/wiki/Distance_euclidienne) (distance associée à la norme 2), la [distance de Manhattan](http://fr.wikipedia.org/wiki/Distance_de_Manhattan) (distance associée à la norme 1) ou la [distance de Tchebychev ou Chebyshev](http://fr.wikipedia.org/wiki/Distance_de_Tchebychev) (distance associée à la norme _infini_). Examinons d'abord quelques ensembles de constantes classiques. On va utiliser dans ce cas une représentation en niveau de gris, parce que la représentation en couleurs ne rend pas bien. Le choix le plus logique est _C1=1_ et tout le reste à zéro, c'est là qu'on distingue le mieux le diagramme de Voronoï. Et en fait, on prend plutôt _C1=-1_ histoire d'avoir des bosses plutôt que des creux. On peut ensuite penser à _C2=1_ et tout le reste à zéro, ou _C3=1_ et tout le reste à zéro, et on voit apparaître des formes assez originales. Mais en fait, on obtient de bons résultats avec _C1=-1_ et _C2=1_ où on a l'impression d'avoir des collines les unes à côtés des autres. La distance utilisée est la distance euclidienne. _C1=-1_|_C2=1_|_C3=1_|_C1=-1_, _C2=1_ ------|------|------|--------------- ![c1=-1](http://www.akagoria.org/img/E10/mini_cell_c1.png)|![c2=1](http://www.akagoria.org/img/E10/mini_cell_c2.png)|![c3=1](http://www.akagoria.org/img/E10/mini_cell_c3.png)|![c1=-1, c2=1](http://www.akagoria.org/img/E10/mini_cell_euclidean.png) Pour la suite, nous prendrons _C1=-1_ et _C2=1_. Et nous allons voir l'influence de la distance. euclidean|manhattan|chebyshev ---------|---------|--------- ![euclidean](http://www.akagoria.org/img/E10/mini_cell_euclidean.png)|![manhattan](http://www.akagoria.org/img/E10/mini_cell_manhattan.png)|![chebyshev](http://www.akagoria.org/img/E10/mini_cell_chebyshev.png) On constate que les distances de Manhattan et de Tchebychev produisent des formes très géométriques, avec des artefacts horizontaux et verticaux très présents. Si on représente la combinaison gagnante en grand, ça donne : ![Bruit à base de cellule](http://www.akagoria.org/img/E10/cell_noise.png) Et on peut évidemment appliquer une fractale (score d'érosion : 0,386916). À noter que pour ces deux cartes, j'ai placé le niveau de l'eau à 0,1 plutôt que 0,5, et j'ai ajusté l'échelle présentée au début, sinon la majorité de la carte est sous l'eau. ![Bruit à base de cellule](http://www.akagoria.org/img/E10/cell_noise_with_fractal.png) Il faut faire attention à l'implémentation pour que la fractale marche bien et ne donne pas des trucs horribles. Il faut en fait répéter nos points à l'infini de manière virtuelle de manière à avoir une continuité dans le bruit, sinon les discontinuités apparaissent et on n'a pas un bruit cohérent. La conséquence, c'est que notre texture peut se répéter également (le haut joint avec le bas et la gauche joint avec la droite) et ça se voit assez clairement. Voir l'[implémentation du bruit à base de cellule](https://github.com/jube/mapmaker/blob/master/src/lib/cell_noise.cc). ## Méthodes à base de placement de point Voilà pour les méthodes à base de bruit de Perlin. Passons maintenant aux [méthodes à base de placement de point](http://www.gameprogrammer.com/fractal.html). Il y en a deux, et la seconde est une amélioration de la première. La particularité de ces méthodes est qu'elles génèrent des cartes de tailles 2^k+1. Pour avoir des tailles arbitraires, on génère une carte plus grande de la bonne taille et on prend une sous-partie de ce qui a été généré. ### Déplacement du point médian (Midpoint displacement) La première méthode s'appelle le déplacement du point médian. Elle est assez simple à décrire. On part d'un carré pour lequel on a défini quatre valeurs aux coins. Puis, on fait la moyenne des quatre coins, à laquelle on ajoute une petite variation proportionnelle au côté du carré, et cela définit la valeur du centre du carré. Reste alors à compléter les quatre carrés par quatre points, chaque point étant entre deux points du carré initial pour lesquels on va faire la moyenne et ajouter à nouveau une petite variation. Puis on recommence récursivement sur ces quatre carrés jusqu'à arriver à un pixel. On obtient ce genre de carte (score d'érosion : 0,385764) ![midpoint displacement](http://www.akagoria.org/img/E10/midpoint_displacement.png) Le résultat montre des artefacts horizontaux et verticaux bien visibles. C'est la raison d'être de la méthode suivante. Voir l'[implémentation du déplacement du point médian](https://github.com/jube/mapmaker/blob/master/src/lib/midpoint_displacement.cc). ### Diamant-Carré (Diamond-Square) La seconde méthode s'appelle l'[algorithme du diamant-carré](http://en.wikipedia.org/wiki/Diamond-square_algorithm). Elle ressemble à la précédente mais elle est partagée en deux phases : la phase diamant et la phase carré. Pendant la phase diamant, on procède comme précédemment, on fait la moyenne des quatre coins, à laquelle on ajoute une petite variation proportionnelle au côté du carré, et cela définit la valeur du centre du carré. Puis on passe à la phase carré pour définir les quatre derniers points. La différence par rapport à précédemment, c'est qu'on utilise pas seulement les points du carré initial mais aussi les points des centres des carrés adjacents. La phase diamant a créé des diamants et chacun des points restants est donc au centre d'un de ces diamants, donc on utilise les quatre coins du diamant pour recréer des carrés en faisant la moyenne, à laquelle on ajoute une petite variation proportionnelle au côté du carré. Ainsi, on a partagé notre carré initial en quatre carrés et on peut appliquer la même méthode récursivement. Et voici le résultat (score d'érosion : 0,382071) ![diamond square](http://www.akagoria.org/img/E10/diamond_square.png) L'impression visuelle est bien meilleure. Les artefacts ont complètement disparu. Cette carte servira de base pour la section suivante de cet épisode. Voir l'[implémentation de l'algorithme diamant-carré](https://github.com/jube/mapmaker/blob/master/src/lib/diamond_square.cc). ## Autres méthodes À côté de toutes les méthodes décrites précédemment et qui sont assez standard, il existe d'autres méthodes qu'on arrive à débusquer au hasard de la navigation. En voici une qui construit [une carte à base collines](http://www.stuffwithstuff.com/robot-frog/3d/hills/hill.html). L'idée est de générer des collines, c'est-à-dire des demi-sphères de manière aléatoire. On les accumule et ça donne des formes assez sympas même s'il y a des artefacts visibles (score d'érosion : 0,480934). ![hills](http://www.akagoria.org/img/E10/hills.png) Voir l'[implémentation de l'algorithme des collines](https://github.com/jube/mapmaker/blob/master/src/lib/hills.cc). # Modification de la carte Maintenant qu'on a de jolies cartes, on va les modifier. En effet, ces cartes rendent bien mais elles n'ont pas forcément les bonnes caractéristiques. En particulier, aucune des cartes présentées précédemment n'a un score de bâtiments non-nul, ce qui signifie qu'elles ont toutes des pentes beaucoup trop importantes. Si on veut qu'elles s'approchent d'un relief réel ou qu'elles soient plus lisses, on peut appliquer divers filtres que je vais vous présenter. ## Érosion Pour rendre une carte plus réaliste, la première technique est de simuler de l'[érosion](http://fr.wikipedia.org/wiki/%C3%89rosion). Voici trois techniques, présentées dans l'article [Realtime Procedural Terrain Generation](http://oddlabs.com/download/terrain_generation.pdf). ### Érosion thermique La première technique permet de simuler une érosion thermique. L'érosion thermique est celle qui provoque des éboulements. À cause de l'action des températures, le sol va se fissurer, puis s'effriter puis s'effondrer et va glisser si la pente le permet. On simule cette érosion de la manière suivante : pour toutes les cases, on regarde si la pente est supérieure à une limite fixée, puis si c'est le cas, on enlève une fraction de matière de la case qui va s'accumuler sur les cases adjacentes les moins élevées. On répète ce processus un certain nombre de fois et voilà ce qu'on obtient (score d'érosion : 0,475935). ![Érosion thermique](http://www.akagoria.org/img/E10/thermal_erosion.png) On observe le tassement surtout sur les côtes qui ont pris un peu d'embonpoint. Voir l'[implémentation de l'érosion thermique](https://github.com/jube/mapmaker/blob/master/src/lib/thermal_erosion.cc). ### Érosion hydraulique La seconde technique permet de simuler une érosion hydraulique. L'érosion hydraulique est dûe à l'action de la pluie et du phénomène de [sédimentation](http://fr.wikipedia.org/wiki/S%C3%A9dimentation). On le simule avec quatre étapes. Première étape, de l'eau tombe du ciel uniformément sur le terrain. Deuxième étape, une partie du matériel présent sur le terrain se dissout dans l'eau. Troisième étape, l'eau ruisselle sur les pentes. Quatrième étape, l'eau s'évapore et le matériel qu'elle transportait se dépose au sol. De la même manière qu'avant, on répète ce processus un certain nombre de fois et voilà ce qu'on obtient (score d'érosion : 0,446365). ![Érosion thermique](http://www.akagoria.org/img/E10/hydraulic_erosion.png) Malgré un temps de calcul bien plus élevé que pour l'érosion thermique, les différences sont assez imperceptibles visuellement. L'article montre qu'en fait, l'érosion thermique aplanit les zones à peu près plates et renforce les pentes, ce qui accroît le score d'érosion. Voir l'[implémentation de l'érosion hydraulique](https://github.com/jube/mapmaker/blob/master/src/lib/hydraulic_erosion.cc). ### Érosion rapide On a donc une technique rapide mais qui aplanit les pentes, et une technique lente qui renforce les pentes. Et on aimerait bien un mélange, c'est-à-dire une technique rapide qui renforce les pentes. Pour ça, un nouvel algorithme, appelé _fast erosion_, a été développé par l'auteur de l'article. Il reprend le principe de l'érosion thermique mais plutôt que de considérer des éboulements quand la pente est forte, il considère des éboulements quand la pente est faible. Et le résultat est conforme à celui qui était voulu. Voici le résultat (score d'érosion : 1,271748). ![Érosion rapide](http://www.akagoria.org/img/E10/fast_erosion.png) On constate bien que le résultat diffère vraiment de l'original. On voit bien de grandes zones planes apparaître. Et pour la première fois depuis le début, on a un score de bâtiment non nul sans être démentiel (score de bâtiment : 0,032020). Voir l'[implémentation de l'érosion rapide](https://github.com/jube/mapmaker/blob/master/src/lib/fast_erosion.cc). ## Transformation en île Une des caractéristiques voulues pour un jeu vidéo est que l'univers de jeu doit être limité. Et pour cela, la méthode la plus courante, en particulier dans les RPG, est de jouer sur une île. Jusqu'à présent, notre terrain n'était pas une île. Nous allons voir deux techniques pour transformer un terrain quelconque en île. ### Par les bords La première technique, que j'ai imaginée moi-même (pour une fois), consiste à replier les bords de la carte. Mais pas n'importe comment. Si on applique un facteur linéaire en fonction de la distance au bord, on obtient des côtes droites. Sans compter que ça peut créer une discontinuité là où on a commencé à appliquer le repliement. J'ai donc essayé plusieurs fonctions. ![Bord de cartes](http://www.akagoria.org/img/E10/sides.png) J'ai commencé par la racine carré qui donnait des résultats plutôt satisfaisants mais on observait toujours cette discontinuité à la limite du repliement. Il me fallait donc une fonction qui ait une dérivée nulle en 1 (ce n'est pas obligatoire en 0, puisque c'est le bord de la carte donc la discontinuité ne se voit pas). Et là, on pense de suite à une fonction trigonométrique et en l'occurrence, sinus qui présente le bon profil. Le résultat commençait à devenir intéressant même si on observait des côtes droites. Cela vient du fait que la pente de la courbe sinus est supérieure à 1, ce qui fait que de petits changements sur la carte d'origine sont complètement occultés. L'idéal est donc d'avoir une pente inférieure à 1 mais un truc genre sinus. Et donc, j'ai combiné le sinus et la racine carrée pour obtenir le résultat que je souhaitais. ![Îlification](http://www.akagoria.org/img/E10/islandize.png) Voir l'[implémentation de la transformation en île par les bords](https://github.com/jube/mapmaker/blob/master/src/lib/islandize.cc). ### Par le milieu La seconde technique, qui m'a été [inspirée](http://www.stuffwithstuff.com/robot-frog/3d/hills/island.html), consiste à multiplier notre carte par une [fonction gaussienne en deux dimensions](http://fr.wikipedia.org/wiki/Fonction_gaussienne#Fonction_gaussienne_en_deux_dimensions), la fameuse cloche. Simple, efficace, on peut également régler l'écartement pour ajuster l'île comme on le souhaite. Le principal inconvénient est que ça force quand même les îles à avoir une forme... de cloche. ![Gaussification](http://www.akagoria.org/img/E10/gaussize.png) Voir l'[implémentation de la transformation en île par le milieu](https://github.com/jube/mapmaker/blob/master/src/lib/gaussize.cc). # MapMaker [MapMaker](https://github.com/jube/mapmaker) est un logiciel que j'ai concocté pour expérimenter toutes ces techniques. Il permet à partir d'un [fichier YAML](https://github.com/jube/mapmaker/blob/master/doc/mapmaker_refcard.md) de décrire un pipeline d'algorithmes, en partant d'un générateur puis en appliquant des modificateurs et enfin éventuellement un finaliseur. ## Actuellement Actuellement, toutes les techniques décrites ici ont été implémentées et fonctionnent (enfin, j'espère). MapMaker produit des fichiers au [format portable pixmap](http://fr.wikipedia.org/wiki/Portable_pixmap) qui a l'avantage d'être facile à générer même s'il n'est pas très optimal. Ensuite, [convert](http://www.imagemagick.org/script/convert.php) est votre ami. Vous pouvez d'ailleurs [voir les fichiers correspondant à tous les exemples présentés dans cet épisode](http://www.akagoria.org/img/E10/) si vous voulez une idée de comment ça se présente en vrai. Pour la carte du tout début, j'ai commencé par la carte issue du diamant-carré. Puis j'ai appliqué une érosion rapide, puis un léger [aplatissement (flatten)](https://github.com/jube/mapmaker/blob/master/src/lib/flatten.cc) qui a tendance à creuser les vallées et que j'ai [piqué ailleurs](http://www.stuffwithstuff.com/robot-frog/3d/hills/flatten.html). Ensuite, j'ai appliqué un peu d'érosion thermique, histoire de créer des passages entre les plateaux créé par l'érosion rapide. Puis un petit [lissage (smooth)](https://github.com/jube/mapmaker/blob/master/src/lib/smooth.cc) qui est le lissage trivial que l'on fait en traitement d'image. Enfin, j'ai transformé mon terrain en île, en utilisant l'algorithme par les bords. Bon, on peut sans doute faire mieux, et j'ai tâtonné pour arriver à ce résultat, mais ça me convient. Je n'ai pas cherché à optimiser la vitesse de génération ou la taille des cartes. Quand on manipule des cartes de 512x512, composé de `double`, ça fait la carte à 2Mio. On peut considérer que c'est beaucoup, ou que c'est peu, suivant le contexte. Pour avoir un ordre d'idée, en utilisant mon laptop de développement (Dell latitude E5530), voici quelques chiffres pour la génération de la carte du début. Pour le temps de génération : generator: 'diamond-square' size: 513 x 513 duration: 43 ms modifier: 'fast-erosion' duration: 1064 ms modifier: 'flatten' duration: 21 ms modifier: 'thermal-erosion' duration: 19 ms modifier: 'smooth' duration: 6 ms modifier: 'islandize' duration: 11 ms Ce qui est tout à fait raisonnable. Valgrind me dit que j'utilise un peu moins de 158Mio de mémoire (en cumulé). Là en revanche, ça pourrait être mieux. Sur la même carte mais en version 8193x8193, c'est-à-dire 256 fois plus grande : generator: 'diamond-square' size: 8193 x 8193 duration: 8772 ms modifier: 'fast-erosion' duration: 324826 ms modifier: 'flatten' duration: 5662 ms modifier: 'thermal-erosion' duration: 5691 ms modifier: 'smooth' duration: 1920 ms modifier: 'islandize' duration: 3143 ms Il faudrait faire plus de tests mais ça a l'air de passer à l'échelle de manière linéaire. Je n'ai pas fait de Valgrind mais je pense que en mémoire ça passe à l'échelle également de manière linéaire, ce qui nous ferait dans les 40Gio (en cumulé). Bon d'accord, pour la prochaine version, je vais m'occuper de cet aspect. ## Possibilités Les possibilités d'extension sont nombreuses. Je ne sais pas si je vais les implémenter, mais je les mets ici pour mémoire. Tout d'abord, on peut expérimenter des bruits plus récents, tel que le [wavelet noise](http://en.wikipedia.org/wiki/Wavelet_noise) (qui a quand même l'air assez difficile à implémenter). On peut aussi expérimenter des méthodes alternatives de génération ou de modification si on a beaucoup d'idées. La limite la plus visible, c'est le pipeline. En vrai, on aimerait bien avoir un graphe d'opérateurs qu'on pourrait manipuler et brancher à travers une interface graphique. Et bien, bonne nouvelle, ce genre d'outil existe ! Ça s'appelle [World Machine](http://www.world-machine.com/) mais malheureusement, c'est propriétaire. Mais ça permet de [faire des choses assez complexes](http://unigine.com/articles/131016-procedural-content-generation2/#terrain_base). Je dois avouer que je n'ai pas les capacités pour faire ce genre de choses, je suis parfaitement inexpérimenté en interface graphique, mais, il existe des [tutoriaux pour Qt5](http://qt-project.org/doc/qt-5/qtwidgets-graphicsview-diagramscene-example.html) qui pourraient servir de base. Bon, mais c'est bien gentil ces cartes d'altitude, mais pour l'instant, ce n'est pas très exploitable en l'état. C'est l'objet de la deuxième partie de cet épisode : voir comment transformer une carte d'altitude en un truc jouable. Et du coup, je pourrai remplacer ma vieille île toute pas belle en quelque chose de plus joli. Mais ça, ça sera la prochaine fois (et ça sera sans doute moins long) ! # Pour aller plus loin Pour finir, voici quelques liens pour ceux qui veulent aller plus loin. Tout d'abord, je ne saurais trop vous conseiller d'aller voir la [libnoise](http://libnoise.sourceforge.net/). La bibliothèque en elle-même est un peu vieille et l'implémentation est faite pour du bruit 3D, ce qui n'est pas toujours adapté pour du bruit 2D (ça complexifie et ça alourdit les calculs). Mais les [tutoriaux](http://libnoise.sourceforge.net/tutorials/index.html) sont très pédagogiques pour bien comprendre ce qu'est le bruit cohérent. De même que l'[exemple d'une planète complète](http://libnoise.sourceforge.net/examples/complexplanet/index.html) construite avec de multiples générateurs et modificateurs. Pour ceux qui ne maîtrisent pas la langue de la perfide albion, il y a [le tutoriel de Jérémy Cochoy](http://cochoy-jeremy.developpez.com/tutoriels/2d/introduction-bruit-perlin/) qui est très bien fait. Il décortique le bruit de Perlin mais aussi le bruit à base de simplexe. C'est très progressif, il y a beaucoup d'illustrations, bref, un bon point d'entrée. Notons aussi le [projet Fractal Terrain Generation sur Google code](https://code.google.com/p/fractalterraingeneration/) qui, à défaut de fournir beaucoup de code, a un [excellent wiki](https://code.google.com/p/fractalterraingeneration/w/list) avec des explications sur comment implémenter divers types de bruit ainsi que les méthodes à base de placement de point. Enfin, pour tout savoir sur la notion de bruit, il y a toujours le [tutoriel du Red Blog Games](http://www.redblobgames.com/articles/noise/introduction.html) qui vous fera voir du [bruit de toutes les couleurs](http://fr.wikipedia.org/wiki/Bruits_color%C3%A9s). Le même Red Blog Games fournit également un [tutoriel pour la création de cartes polygonales](http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/) dont j'ai déjà parlé mais qui est un véritable délice.

AltStyle によって変換されたページ (->オリジナル) /