Je crée mon jeu vidéo E10 : génération procédurale de carte (partie 1)

Posté par . Édité par Benoît Sibaud, palm123, ZeroHeure et tuiu pol. Modéré par Benoît Sibaud. Licence CC by-sa
111
7
mar.
2014
Jeu

«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.

Dans l'épisode 09, 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» (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 !

Sommaire

Exemple de carte finale

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

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, 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, 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 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, 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

Voici la carte de bâtiments associée à la carte du début.

Carte de bâtiments

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é. Ça a l'air simple mais ça ne l'est pas. Sans relief ombré, la carte ressemblerait à ça.

Exemple de carte finale sans relief

Après beaucoup de recherches, j'ai utilisé l'algorithme simple utilisé dans le tutorial de génération de cartes polygonales d'Amit Patel (Red Blog Games). 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 et Relief Shading. 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é 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 comme une fonction (informatique) de Rn 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 (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, ou fBm pour les intimes. Je l'ai nommée plus simplement fractal.

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

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. On utilise une fonction appelée traditionnellement lerp, définie de la manière suivante :

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 :

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 x3 + 3 x2. 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 x5 - 15 x4 + 10 x3. 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

Voici le résultat sur les mêmes valeurs :

linear cubic quintic cosine
linear cubic quintic cosine

Généralement, le polynôme de degré 3 donne des résultats satisfaisants. On garde donc celui-ci :

Bruit à base de valeur

Et avec 10 octaves, on obtient une carte tout à fait convenable (score d'érosion : 0,429078) :

Bruit à base de valeur

Voir l'implémentation du bruit à base de valeur.

Bruit à base de gradient (gradient noise)

Le buit à base de gradient est le vrai bruit de Perlin, décrit dans Making Noise, que Ken Perlin a inventé pour le film 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 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. 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

Le résultat avec 10 octaves n'est pas mal du tout (score d'érosion : 0,433705) :

Bruit à base de gradient

Voir l'implémentation du bruit à base de gradient.

Bruit à base de simplexe (simplex noise)

Le bruit à base de simplexe 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(2n) interpolation pour un bruit à n dimensions. Ceci vient du fait qu'on utilise un hypercube qui a 2n 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. 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 est assez complexe. La difficulté consiste à calculer le triangle dans lequel on se situe. L'idée est d'appliquer une sorte de 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

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

Voir l'implémentation du bruit à base de simplexe.

Bruit à base de cellule (cell noise)

Dernier bruit de la série, le bruit à base de cellule. 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ï). 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 (distance associée à la norme 2), la distance de Manhattan (distance associée à la norme 1) ou la distance de Tchebychev ou Chebyshev (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 c2=1 c3=1 c1=-1, c2=1

Pour la suite, nous prendrons C1=-1 et C2=1. Et nous allons voir l'influence de la distance.

euclidean manhattan chebyshev
euclidean manhattan chebyshev

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

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

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.

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. 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 2k+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

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.

Diamant-Carré (Diamond-Square)

La seconde méthode s'appelle l'algorithme du diamant-carré. 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

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é.

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

Voir l'implémentation de l'algorithme des collines.

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. Voici trois techniques, présentées dans l'article Realtime Procedural Terrain Generation.

É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

On observe le tassement surtout sur les côtes qui ont pris un peu d'embonpoint.

Voir l'implémentation de l'érosion thermique.

É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. 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

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.

É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

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.

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

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

Voir l'implémentation de la transformation en île par les bords.

Par le milieu

La seconde technique, qui m'a été inspirée, consiste à multiplier notre carte par une 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

Voir l'implémentation de la transformation en île par le milieu.

MapMaker

MapMaker est un logiciel que j'ai concocté pour expérimenter toutes ces techniques. Il permet à partir d'un fichier YAML 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 qui a l'avantage d'être facile à générer même s'il n'est pas très optimal. Ensuite, convert est votre ami. Vous pouvez d'ailleurs voir les fichiers correspondant à tous les exemples présentés dans cet épisode 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) qui a tendance à creuser les vallées et que j'ai piqué ailleurs. 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) 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 (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 mais malheureusement, c'est propriétaire. Mais ça permet de faire des choses assez complexes. 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 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. 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 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 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 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 qui, à défaut de fournir beaucoup de code, a un excellent wiki 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 qui vous fera voir du bruit de toutes les couleurs. Le même Red Blog Games fournit également un tutoriel pour la création de cartes polygonales dont j'ai déjà parlé mais qui est un véritable délice.

  • # Merci!

    Posté par . Évalué à 8.

    Merci pour l'article, et merci pour la série "Je crée…", d'ailleurs.

    J'ai toujours trouvé passionnant la génération procédurale de terrain, depuis le jeu The Sentinel sur Amstrad CPC: 10000 niveaux en 3D, générés automatiquement. Le support cassette n'aurait pas pu stocker autant de données de cartes. Les cartes étaient donc générés à partir de leur numéro de niveau (de 0 à 9999). A l'époque je n'en savais rien, mais après des années je me suis renseigné sur les algos de génération procédurale de terrain, et j'ai repensé à ce jeu. L'auteur est interviewé ici.

    • [^] # Re: Merci!

      Posté par . Évalué à 6.

      J'ai oublié d'en parler, mais ces techniques sont encore utilisées de nos jours. Notamment dans Minecraft où les terrains sont générés à base de bruit de Perlin. Et beaucoup d'éditeurs de niveaux pour des jeux modernes ont un module qui permet de générer des terrains à partir des techniques présentées ici. Donc, ces techniques ne sont pas mortes, au contraire. Mais elles ne sont plus intégrées dans les jeux, elles servent justes de base pour éviter de passer trop de temps sur des tâches sans intérêt. Ensuite, une fois la base générée, on peut décorer la carte comme on veut.

  • # lacs et cours d'eau

    Posté par . Évalué à 6.

    Excellent article, vraiment.

    Il y a juste un point qui ne semble pas apparaître ( l'article est très instructif, mais long, donc j'ai dû accélérer "un peu" ma lecture… ) c'est la génération de lacs et de cours d'eau.

    Je suppose qu'il est possible de définir manuellement ou aléatoirement des points de source pour les cours d'eau, et de faire ruisseler le dit cours d'eau en fonction de la pente ( il "suffirait" de regarder toutes les altitudes proches et de générer une érosion plus importante pour le point qui à l'altitude la moins élevée, et ce jusqu'à l'arrivée à un autre point d'eau: océan—niveau 0 --, autre cours d'eau, ou lac ) mais ce qui serait intéressant, ce serait d'être capable de générer des lacs quand le relief forme une cuve.

    Peut-être en simulant une pluie:
    Pour chaque point d'une zone, vérifier s'il est en contact avec un point plus bas non inondé, et si ce n'est pas le cas, inonder. En répétant l'opération N fois, on pourrait ainsi simuler une pluie de force N, j'imagine?
    Du coup, on pourrait imaginer avoir une pluie de force suffisamment élevée pour dépasser le relief sur un point, qui formerait donc une source et génèrerait donc une rivière.

    En fait, je n'ai aucune idée de la complexité de ce type de génération et de son implémentation potentielle, et je me demandais si tu as songé à ce détail lors de tes recherches et implémentations?

    • [^] # Re: lacs et cours d'eau

      Posté par . Évalué à 3.

      La génération de rivière, ça sera pour la partie 2. Et oui, j'y ai déjà réfléchi (ou plutôt, deux de mes étudiants y ont réfléchi) et il existe plusieurs algorithmes possibles. Les plus naïfs ne marchent pas bien en fait, soit parce qu'ils sont beaucoup trop long, soit parce qu'ils ne donnent pas de bons résultats. Du coup, il faudra un peu patienter ;)

      • [^] # Re: lacs et cours d'eau

        Posté par . Évalué à 3.

        C'est un sujet sur lequel je me suis déjà un peu penché, j'ai hâte de voir tes solutions :)

        J'ai d'abord essayé des systèmes réalistes d'écoulement d'eau, mais sans grand succès.
        Finalement, je me suis simplement penché sur un bête A* en utilisant la topologie de la carte comme heuristique, le résultat s'est montré satisfaisant dans le cadre du projet sur lequel je travaille, bien qu'il montrerait très vite ses limites si on cherche à représenter un monde trop réaliste.

        Je me permet quelque questions :

        • Puisque, si j'ai bien compris, tu travaille sur un jeu 2d, comment penses tu représenter visuellement une topologie aussi précise que celle que ton algorithme est capable de générer ?

        • Au final, sous quelle forme vas tu représenter le monde au joueur ? Vas tu granulariser ta carte pour l'afficher sous forme de tuiles, comme la plupart des jeux 2d ?

        • Comptes-tu utiliser des graines différentes pour chaque partie afin de générer des niveaux aléatoires, ou n'est-ce qu'un moyen pour toi d'accélérer et de simplifier le level-design d'un monde unique ?

        Merci encore pour ces séries d'articles, c'est toujours très enrichissant, d'autant plus que c'est des sujets qui me tiennent particulièrement à coeur :)

        • [^] # Re: lacs et cours d'eau

          Posté par . Évalué à 4.

          Finalement, je me suis simplement penché sur un bête A* en utilisant la topologie de la carte comme heuristique, le résultat s'est montré satisfaisant dans le cadre du projet sur lequel je travaille, bien qu'il montrerait très vite ses limites si on cherche à représenter un monde trop réaliste.

          C'est intéressant comme algorithme, j'en ai un qui ressemble un peu. Et sur le côté réaliste, je dirais qu'on est dans un jeu vidéo, donc on peut prendre quelques libertés. Je ne suis pas géographe !

          Puisque, si j'ai bien compris, tu travaille sur un jeu 2d, comment penses tu représenter visuellement une topologie aussi précise que celle que ton algorithme est capable de générer ?
          Au final, sous quelle forme vas tu représenter le monde au joueur ? Vas tu granulariser ta carte pour l'afficher sous forme de tuiles, comme la plupart des jeux 2d ?

          L'idée, pour la suite, c'est de dire qu'un pixel sur la carte d'altitude, c'est une tuile sur la carte finale. J'ai déjà une carte sous forme de tuile (voir l'épisode 7), mais pour l'instant, elle est un peu basique. Le tileset est moisi, les couleurs sont horribles. Je vais donc définir un tileset, puis définir pour chaque case quelle tuile convient le mieux, en fonction de l'altitude, mais pas que.

          Une difficulté, comme tu le dis, c'est de représenter le relief et la pente en vue de dessus. Je pense que c'est hyper difficile, et que ça n'apporte pas grand chose étant donné le niveau de zoom sur le personnage. Mais on peut donner des indices visuels qui permettent, pour certaines situations (comme les zones infranchissables) de suggérer qu'il y a un relief. Et on peut toujours permettre au joueur de voir une grande carte générée par mon programme en l'état actuel pour qu'il voit les reliefs ;)

          Comptes-tu utiliser des graines différentes pour chaque partie afin de générer des niveaux aléatoires, ou n'est-ce qu'un moyen pour toi d'accélérer et de simplifier le level-design d'un monde unique ?

          Je suis clairement dans la deuxième solution. Je veux un monde assez grand et je ne veux pas m'occuper de tous les détails, surtout ceux qui peuvent être délégués à un algorithme. Donc, j'ai écris ces algos pour pouvoir générer des mondes et en choisir un qui me servira pour mon jeu. Dans la partie 2, je montrerai tout ce que je génère en plus pour éviter de me fatiguer ;) Mais clairement, si je devais tout générer, y compris les quêtes et tout ça, ça serait un travail énorme et d'une difficulté largement supérieure à ce que j'ai fait là.

          • [^] # Re: lacs et cours d'eau

            Posté par . Évalué à 2.

            Une difficulté, comme tu le dis, c'est de représenter le relief et la pente en vue de dessus. Je pense que c'est hyper difficile, et que ça n'apporte pas grand chose étant donné le niveau de zoom sur le personnage. Mais on peut donner des indices visuels qui permettent, pour certaines situations (comme les zones infranchissables) de suggérer qu'il y a un relief. Et on peut toujours permettre au joueur de voir une grande carte générée par mon programme en l'état actuel pour qu'il voit les reliefs ;)

            Des tuiles de montagnes en trompe l'oeil sont aussi un excellent moyen de simuler du relief.
            Les vieux RPG 2D l'utilisent beaucoup, comme les montagnes au nord de Link's Awakening.

            Il serait sans doutes très amusant d'essayer de trouver des algorithmes pour placer ce genre de trompe l'oeil dans une carte généré aléatoirement, tout en gardant un résultat cohérent et en prenant en comptes les nombreuses contraintes (positionnement, orientation).

            • [^] # Re: lacs et cours d'eau

              Posté par . Évalué à 2.

              Les vieux RPG 2D l'utilisent beaucoup, comme les montagnes au nord de Link's Awakening.

              Oui mais là, c'est de la fausse vue de dessus. Dans mon jeu, j'ai pris le parti de faire de la vue de dessus vraiment dessus, à la verticale. Du coup, on ne peut pas utiliser ce genre d'astuce pour simuler le relief.

              • [^] # Re: lacs et cours d'eau

                Posté par . Évalué à 2.

                Tu peux peut-être chercher l'inspiration du coté de certains jeux de plateaux, comme Cry Havoc. Le relief est géré de façon assez réaliste (pour un jeu de plateau), il prend en compte l'impact sur les déplacements, les tir, les combats, etc… Le rendu des cartes et la jouabilité sont plutôt réussis, à mon humble avis, n'étant pas un spécialiste de ce type de jeux :

                http://www.cryhavocfan.org/fr/ressourc/cartes.htm

                Sinon, merci pour cette série d'article très intéressante.

                Faut pas gonfler Gérard Lambert quand il répare sa mobylette.

                • [^] # Re: lacs et cours d'eau

                  Posté par . Évalué à 2.

                  Merci pour ces bonnes références ! Effectivement, j'imaginais plutôt ce genre de choses. Ça sera une bonne source d'inspiration le moment venu, le rendu est plus que convenable.

    • [^] # Re: lacs et cours d'eau

      Posté par . Évalué à 1.

      puisqu'on parle d'eau, dans la partie ou tu parle du bruit a base de cellule tu indique que tu a du baisser le niveau de la mer pour avoir un rendu acceptable.
      Du coup ça me fais pensé qu'il pourrait être intéressant d'avoir un système de marées ou certaines zones ne sont accessible qu'a marée base genre le mont st Michel sans cette horrible digue.
      Après pour l'intégrer dans le jeux 2d ça peu être compliqué.

      Un grand merci pour tes articles ils sont super parfois technique mais en restant assez accessible, surtout ne t’arrête pas !

      • [^] # Re: lacs et cours d'eau

        Posté par . Évalué à 2.

        Du coup ça me fais pensé qu'il pourrait être intéressant d'avoir un système de marées ou certaines zones ne sont accessible qu'a marée base genre le mont st Michel sans cette horrible digue.

        Intéressant mais difficile comme tu le supposes par la suite. Parce qu'il faut pouvoir modifier la carte de base sur de grandes zones, ce qui peut être compliqué suivant le format de la carte (en mémoire). Dans mon cas, je n'avais pas prévu ce genre de choses donc ça ne va pas être possible. Mais l'idée est intéressante.

  • # génération semi-aléatoire

    Posté par (page perso) . Évalué à 3. Dernière modification le 07/03/14 à 12:52.

    article très intéressant, même si au-delà de mon niveau technique…

    J'ai essayé de compiler mapmaker, mais ça plante :(

    J'ai bien installé 'yaml-cpp', et lors de la création du makefile de mapmaker, ça me dit bien " found yaml-cpp, version 0.5.1"

    Ensuite quand ça compile j'ai :
    /…/
    [ 13%] Building CXX object lib/CMakeFiles/mm0.dir/colormap.cc.o
    [ 16%] Building CXX object lib/CMakeFiles/mm0.dir/color_ramp.cc.o
    /tmp/mapmaker/src/lib/color_ramp.cc: In member function ‘void mm::color_ramp::add_color_stop(double, const mm::color&)’:
    /tmp/mapmaker/src/lib/color_ramp.cc:45:11: erreur: ‘class std::map’ has no member named ‘emplace’
    make[2]: *** [lib/CMakeFiles/mm0.dir/color_ramp.cc.o] Erreur 1
    make[1]: *** [lib/CMakeFiles/mm0.dir/all] Erreur 2

    ma version de gcc est la 4.7.2 (linux mint, 64 bit)

    D'autre part, à ce que j'ai compris, mapmaker c'est pour gérérer des terrains entièrement aléatoires. Est-ce qu'il y possibilité de créer des terrains bien érodés à partir d'une carte grossière en heighfields, pour qu'elle semble plus réaliste ? Un peu comme celle-ci par exemple : http://www.cartographersguild.com/attachments/regional-world-mapping/12953d1241371054-world-without-name-monde_carte9.png

    J'avais vu world maker et terragen, mais vu que ce n'était pas libre, ça ne m'a pas plus attiré que ça (je ne suis pas contre acheter un tel logiciel, mais je veux savoir ce qu'il y a dedans)

    « I approve of any development that makes it more difficult for governments and criminals to monopolize the use of force. » Eric Raymond

    • [^] # Re: génération semi-aléatoire

      Posté par . Évalué à 6.

      Pour le bug, c'est juste que GCC 4.7.2 ne gère pas C++11 entièrement (la gestion est complète à partir de GCC 4.8.1). Et donc, la fonction emplace qui permet de construire l'élément directement dans la map n'existe pas dans les vieilles versions. Tu peux remplacer la ligne incriminée par (pas testé mais ça doit passer) :

        m_map.insert(std::make_pair(offset, c));

      Pour ta deuxième question, oui on peut. Il suffit d'implémenter un générateur qui lit un fichier contenant une heightmap. Et ensuite, on applique des opérateurs d'érosion (qui sont définit de manière indépendante dans MapMaker). Si la carte est en couleur, ça peut être assez compliqué à lire, généralement les heightmaps sont en dégradé de gris. La carte que tu montres, c'est le résultat que tu veux avoir ou c'est le point de départ ?

      • [^] # Re: génération semi-aléatoire

        Posté par (page perso) . Évalué à 2.

        oui, ça compile, et ensuite il y a d'autres erreurs. J'essayerai sur une autre machine avec ggc 4.8.1 ça sera plus simple.

        Pour la carte, c'était juste un exemple, il y a déjà du travail supplémentaire et la base pourrait être plus simple, mais c'était pour une idée générale.

        « I approve of any development that makes it more difficult for governments and criminals to monopolize the use of force. » Eric Raymond

  • # GNU Radio ?

    Posté par (page perso) . Évalué à 3.

    En vrai, on aimerait bien avoir un graphe d'opérateurs qu'on pourrait manipuler et brancher à travers une interface graphique.

    J'étais confronté à la même problématique (avant de changer de projet), et j'avais fini par découvrir GNU Radio, où l'on retrouve ce genre de "programmation" à coup de nœuds et connecteurs (comme LabView, SimuLink voire les nodes de Blender). On peut trouver un screenshot en bas de la page du HowTo.

    Je ne suis pas sûr que ça puisse s'utiliser comme ça, mais je pense que ça vaut le coup de jeter un coup d'œil.

    Et bien sûr, merci pour cet article très intéressant à lire. Je m'en vais le plussoyer, tiens.

    • [^] # Re: GNU Radio ?

      Posté par . Évalué à 3.

      Oui, ça correspond à ça sauf que là, c'est hyper spécialisé et en regardant vite fait, je ne crois pas que ce soit adaptable à mon cas. C'est dommage parce que ça correspond assez bien à ce que j'aimerais avoir.

      • [^] # Re: GNU Radio ?

        Posté par . Évalué à 2.

        Pure Data + Gem ?

        • [^] # Re: GNU Radio ?

          Posté par . Évalué à 2.

          Pas satisfait non plus. GEM est très orienté OpenGL, mon outil est pour l'instant orienté pixels. Après, Pure Data peut être spécialisé pour des heightmap, de la même manière que GEM a spécialisé Pure Data pour le graphique. Mais est-ce que ça vaut bien le coup par rapport à un développement from scratch ?

      • [^] # Re: GNU Radio ?

        Posté par . Évalué à 2.

        Et directement le système de nodes de blender ? Y fait déjà de la génération procédurale de textures, un certain nombre de bruits sont implémentés de base (perlin, voronoï) et y doit être (je pense) assez facilement extensible (en python).

        • [^] # Re: GNU Radio ?

          Posté par . Évalué à 2.

          Est-ce que ça vaut le coup de devoir lancer Blender pour générer des heightmaps ? Il me semble que détourner un outil tel que Blender pour faire totalement autre chose, c'est contre-productif.

          • [^] # Re: GNU Radio ?

            Posté par . Évalué à 2.

            Ben le système de nodes de blender est justement (entre autre, il est aussi utilisé pour les matériaux et le post-processing) destiné à généré des textures, dont des heightmaps, c'est pas tant que ça « pour faire totalement autre chose », au contraire. Après, c'est une idée en l'air, je me rends pas compte du boulot nécessaire pour que ça puisse faire tout ce que tu veux. En tout cas ça fournit une GUI et un certain nombre de briques de bases pour ce que tu veux faire.

            • [^] # Re: GNU Radio ?

              Posté par . Évalué à 2.

              En tout cas ça fournit une GUI et un certain nombre de briques de bases pour ce que tu veux faire.

              Ce que je veux faire, c'est vite dit. J'ai un jeu à faire ! Donc, j'ai mis ça comme idée si quelqu'un se sent l'envie de le faire. Ou alors, je donnerai ça à des étudiants, juste pour voir ce que ça peut donner.

      • [^] # Re: GNU Radio ?

        Posté par (page perso) . Évalué à 1.

        Ca semble en effet spécialisé, mais au final, je pense que ça traduit plus l'idée du flux de données. Ensuite, c'est probablement possible de l'appliquer à ce que tu veux faire.

        Juste que les données ne sont plus audio, mais des bitmaps. Les opérateurs sont donc 2D…

        Je ne sais pas si c'est possible, mais je serai surpris que ça ne le soit pas. Ensuite, est-ce pratique ou performant, je n'en ai aucune idée.

        • [^] # Re: GNU Radio ?

          Posté par . Évalué à 2.

          Tu as sans doute raison, c'est sans doute possible. Maintenant, je ne suis pas trop partisan d'essayer de faire rentrer un carré dans un rond. Je veux dire par là que ce genre d'interface a l'air finalement assez courante dans plein de domaines différents mais que ça ne justifie pas de réutiliser le même morceau de code pour tout faire. Dans ce cas là, je pense que ça serait plus une contrainte trop importante à gérer qu'une facilité.

          • [^] # Re: GNU Radio ?

            Posté par (page perso) . Évalué à 1.

            OK, pas de soucis. Par contre, j'attends avec impatience les épisodes futurs (et en particulier celui qui parle de ce genre de problématiques).

            • [^] # Re: GNU Radio ?

              Posté par . Évalué à 2.

              J'ai écrit il y a quelques semaines un éditeur de graphes en C++ basé sur SFML 2.1.
              Par contre il utilise boost (je ne pouvais pas l'écrire en C++11).

              Le principe est définir des modèles en (node/anchor) et de pouvoir spécialiser la sortie dans un fichier.

              C'est par ici : https://github.com/bechu/sfml-flow

              • [^] # Re: GNU Radio ?

                Posté par . Évalué à 2.

                C'est pas mal mais est-ce que ça peut se spécialiser ? Je veux dire, est-ce que je peux définir mes propres opérateurs dans les boîtes ?

                Petite remarque en passant, puisque tu utilises Boost, je pense que ça serait une bonne idée d'utiliser boost::any dans pas mal d'endroit dans ton code (notamment à la place de ton type Model::Data) ;)

                • [^] # Re: GNU Radio ?

                  Posté par . Évalué à 2.

                  Si par opérateurs tu entends spécifier les entrées/sorties/paramètres oui, dans le c++ il suffit de les spécifier de la façon suivante :

                      Model& random = ctrl.add("model");
                      random.input<int>("entree");
                      random.parameter<int>("min") = 0;
                      random.parameter<float>("max") = 3;
                      random.output<float>("sortie");
                      random.output<string>("sortie3");
                  

                  On peut éditer la valeur des paramètres sur l'interface (uniquement float/int/string).
                  Je n'ai pas eu le temps de fixer un problème c'est dans la classe widget, j'ai deux listes de sous widgets qui sont concurrentes (une liste brute et une liste triée par type), il faudrait que je m'en occupe !)

                  Bonne remarque pour le Model::Data, en fait j'hésite toujours à inclure boost je trouve que c'est une grosse dépendance (bien que l'on pourrait arguer que ce ne sont que des headers généralement).

                  • [^] # Re: GNU Radio ?

                    Posté par . Évalué à 2.

                    Dans mon cas, les entrées et sorties, ce sont des cartes complètes ! ;)

                    • [^] # Re: GNU Radio ?

                      Posté par . Évalué à 1.

                      En fait le typage des entrées/sorties/paramètres permet juste de vérifier la pertinence des informations lors de l'enregistrement (vérifier que le type de sortie correspond au type d'entrée), mais le programme ne manipule pas d'instance a proprement dit correspondant a chaque ancre.

                      Le principe est de définir une structure virtuelle composé de modèles et d'ancres que l'on peut ensuite sérialiser.

  • # Très instrcutif !

    Posté par . Évalué à 3. Dernière modification le 13/03/14 à 16:54.

    Salut, j'ai trouvé ton article très intéressant et instructif !
    Tu m'as donné envie de recoder des trucs (oui je sais, je dis ça un article sur deux dans ta série de dévelopement de jeux vidéo… mais là promis, j'y crois :))

    Juste queslques précision sur des points que j'ai eu un peu de mal à comprendre :

    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.

    Sans lire le papier "terrain generation" sur lequel tu mets un lien en début d'article, c'était complètement obscur et incompréhensible pour moi.
    Qu'est ce qu'une octave ?
    À quoi corresponds l'amplutide ? la fréquence ?
    Après l'avoir lu, j'ai compris, et je ne suis pas sur de savoir mieux l'expliquer, mais peut etre rapprocher cette phrase du lien ou donner un exemple simple avec 2 ou 3 (ça risque d'être trop long) octaves, en détaillant complètement l'algo et les calculs, pourrait aider.

    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 point P n'étant pas défini, j'ai cru au début à une faute de frappe de ta part, j'ai compris ensuite que je n'avais pas compris ;)
    Mais je pense que cette partie mérite aussi une explication supplémentaire.
    Comme par exemple définir les 4 (ou n, pour un hypercube) points Pi autour de A et Gi le gradient en Pi. Enfin, poser le produit scalaire Gi.(Pi-A) comme dans le papier de Perlin (c'est une suggestion de présentation, bien sur, mais moi ça m'aurait aidé à comprendre beaucoup plus vite)

    Sinon c'est vraiment chouette :)
    Je n'ai pas encore approfondi la partie ombres, mais elle m'intéresse aussi.
    Je vais peut-être reprendre (dès que le soleil repartira…) le code de génération de terrain aléatoire que j'avais tenté décrire en vains lorsque j'étais étudiant.
    la technique que j'avais imaginé à l'époque, et qui ne marchait pas du tout, fonctionnait "dans l'autre sens" de ce que tu décris ici, à savoir créer une map aléatoire, et appliquer des filtres de moyenne et de lissage pour obtenir un résultat.
    Le problème est que pour avoir quelques chose de correct, il faut faire beaucoup d'itérations, et du coup la carte se retrouvait avec un relief très faible.
    Et lorsque j'ai tenté de baisser la fréquence de map carte aléatoire de départ, je voyais clairement apparaitre des artéfact carrés dans mon résultat.
    Il faut dire aussi que mes techniques de lissage étaient basé sur des moyennes polynomiales (linéaires ou quadratiques pour la plupart), pas du tout adaptées :)

    Pour les ombres, comme je faisais du rendu 3d (avec OpenGL), je n'avais pas de soucis particuliers.

    • [^] # Re: Très instrcutif !

      Posté par . Évalué à 4.

      Sans lire le papier "terrain generation" sur lequel tu mets un lien en début d'article, c'était complètement obscur et incompréhensible pour moi.

      En fait, j'aurais pu mieux l'expliquer en montrant plusieurs octaves consécutives. Il existe des exemples en 1D pour bien comprendre, genre (et d'ailleurs, j'ai oublié de mettre ce lien qui explique bien les choses, de manière très visuelle).

      le point P n'étant pas défini, j'ai cru au début à une faute de frappe de ta part, j'ai compris ensuite que je n'avais pas compris ;)

      Heu, il est défini le point P, sur une des images insérées dans le texte, dans la section du bruit à base de valeur. Le point P et le point A se refère à cette image là, pas à la présentation de Perlin. Je n'ai pas les mêmes notations que la présentation de Perlin d'ailleurs, j'ai simplifié.

      • [^] # Re: Très instrcutif !

        Posté par . Évalué à 2.

        Heu, il est défini le point P, sur une des images insérées dans le texte, dans la section du bruit à base de valeur. Le point P et le point A se refère à cette image là, pas à la présentation de Perlin. Je n'ai pas les mêmes notations que la présentation de Perlin d'ailleurs, j'ai simplifié.

        Oups, je n'étais pas remonté jusque là !
        Et du coup, ma tentative d'explication est fausse par rapport à ta notation !
        Dans ce cas, ce qui m'a induit en erreur est la début de la phrase : "Pour le point A"
        J'ai vraiment pensé qu'il s'agissait d'un point final pour lequel on veut une valeur d'altitude.

      • [^] # Re: Très instrcutif !

        Posté par . Évalué à 4.

        En fait, j'aurais pu mieux l'expliquer en montrant plusieurs octaves consécutives. Il existe des exemples en 1D pour bien comprendre, genre là (et d'ailleurs, j'ai oublié de mettre ce lien qui explique bien les choses, de manière très visuelle).

        Ce lien est parfait, merci :)
        Je pense que cela vaut le coup d'éditer la dépêche pour le rajouter !

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.