“Génération Procédurale de mondes” – L’Algotihme de Perlin

Introduction:

Dans cette contribution je vais vous présenter la technologie de génération procédurale à travers l’algorithme de Perlin. Je commencerai par définir le processus de cette méthode puis je m’intéresserai à l’histoire de ce dernier. Ensuite j’exposerai les secteurs dans lesquels elle prend vie pour prendre conscience de la place des algorithmes et de l’aléatoire dans la génération procédurale.  Après cela, je vous présenterai l’algorithme de Perlin, son fonctionnement et son utilisation.


I)La génération procédurale, qu’est-ce que c’est ?

« Procedural generation is a widely used term in the production of media; it refers to content generated algorithmically rather than manually. Often, this means creating content on the fly rather than prior to distribution. This is often related to computer graphics applications and video game level design. »

« La génération procédurale est un terme largement utilisé dans la production de médias ; il se réfère au contenu généré de manière algorithmique plutôt que manuellement. Souvent, cela signifie créer du contenu à la volée plutôt qu'avant la distribution. Cela est souvent lié aux applications graphiques informatiques et à la conception de niveaux de jeux vidéo. " (Wikipédia)

 

Le terme génération, nous renvoie à la notion de création. Mais là où la création évoque toute une portée artistique, humaine et manuelle, la génération se veut être relative à la conception de contenu (physique comme abstrait) à plus grande échelle. De plus, tout génération de contenue automatisée répondant a un certain nombre de réglé est procédural.

En informatique, la génération procédurale ou modelé procédural est donc la création de contenu numérique à une grande échelle et en grand quantité. De manière automatisée, la génération s’appuie sur un ensemble d’informations et de règles définis par un algorithme.

Image crée de façons procédural.


 

II)  Pourquoi la génération procédurale ?

      Dans les année 80, les jeux de de rôle sur table étaient très répandus. Le plus connu, Donjon et Dragons s’est vendu à plus de deux millions et demi d'exemplaires. Les joueurs, appelé rôlistes, pouvaient passer des heures autour d’une table à jouer à travers des personnages fictifs. Les jeux de rôle donnent au joueur une expérience de jeu unique à chaque partie et chaque joueur. En effet, on peut jouer sans jamais de répétions dans l’histoire, quête, personnage, et monde tous différents.

Alors certains développeurs de jeux ont voulu recréer cette expérience dans les jeux vidéo. C’est alors qu’ils ont dû faire face à un problème, impossible de charger de grandes cartes ou bien rajouter de nombreux monstres. Leurs machines, notamment la capacité en RAM qui a l’époque était très cher, surchargeaient beaucoup trop vite. Mais grâce aux mathématiques, une solution a été apportée : les formes et objets seraient calculés dans le CPU, et un seul fichier à charger dans la RAM.

Un nouveau genre de jeux est apparu : les rogue-like où les joueurs explorent des donjons remplis de monstres et de trésors dont la difficulté s’accroît fortement au fur et à mesure de la progression. Très punitifs, les rogues-like ne permettent pas la sauvegarde et quand un joueur meurt, il perd son personnage et recommence tout depuis le début. Pour éviter l’ennui et renouveler la difficulté, chaque réapparition est sanctionnée par un nouveau donjon où les salles et couleur étaient générés de manière procédural

Le premier jeu utilisant la génération procédurale a donc été Rogue, jeu sorti en 1980. Mais cette technique va surtout être connue aux yeux des gamers avec Diablo en 1996. Pour la première fois, les niveaux ne sont plus en deux dimensions mais bien en 3D isométrique tandis que les statistiques qui caractérisaient les items du jeux (puissance des armes, niveau de protection des armures, potion…) sont, elles aussi, générées de manière procédurale.


 

II)Les effets de la génération procédurale dans différents domaines.

Le jeu vidéo étant le domaine où la génération procédurale a servi de nombreuses fois aux développeurs. Le jeu le plus connu pour voir ses fameux effets de cette méthode est Minecraft sortie en 2011 et crée par Markus Persson plus connu sous le pseudo Notch. En effet, tout ce que le joueur voit dans le jeu, depuis le positionnement des arbres, des montagnes et des cavernes, jusqu’à l’apparition des monstres et des ressources qu’il faut miner, s’appuie en fait sur ce processus. Au fur et à mesure que le joueur avance sur le terrain, l’environnement qui l’entoure est automatiquement généré. On peut donc penser que la carte est infinie. Ce n’est pas le cas, un youtubeur, Kurt J.Mac explore Minecraft depuis 4ans à travers une web-série intitulée Far land or Bust avec pour objectif presque impossible à réaliser : atteindre le bord du monde en partant du centre de la carte. Avec plus de Cinq cent épisodes, il a parcouru 2 266 779 blocs soit 2 266 kilomètres si l’on se réfère aux unités de mesure officielles. À son rythme, Kurt va encore devoir marcher plus de 22ans pour arriver a de gigantesques falaises chaotiques, qui marquent la limite du terrain. En effet, si le monde de Minecraft n’est pas infini, sa surface atteint tout de même 3,6 milliards de kilomètres carrés. Dans la version bêta 1.7 utilisée par le youtubeur, la carte ne mesure que 24 000 kilomètres² ce qui donne un trajet total de 12 000 kilomètres en partant du centre.

On peut comparer une carte générée de façon procédurale aux environnements de jeux créés « à la main ». Comme dans les séries comme GTA, Far Cry ou Assassin’s Creed.

 

Dans ces open world, le terrain est divisé en cases plus ou moins grandes contenant un morceau de terrain et des éléments de décor qui ont été modélisés en trois dimensions puis texturés par des artistes. Une fois le jeu lancé, le joueur évolue alors de case en case, appelées en jargon technique des chunks. Dans GTA, les chunks sont très complexes et détaillées mais se trouvent en nombre limité. Dans Minecraft, elles sont simplement créées à la volée par l’ordinateur ce qui permet d’en produire un nombre quasiment infini tout en économisant du temps de développement.

Il est apparu aussi des jeux sur smartphone comme Candy Crush utilisant cette méthode pour créer des niveaux différents à chaque fois.  Ce jeu possédé plus de 3 000 puzzle.

Il n’y a pas que les développeurs de jeux vidéo qui profitent de la génération procédurale. En effet aujourd’hui, beaucoup de studios de films créent des paysages. Elle permet un gain de temps énorme toujours pour la création de terrain, comme les nuages ou bien une forêt.  Plus étonnant, dans le film 300, lors de la scène « This is Sparta ! » les metteurs en scène ont créé la fosse grâce à la génération procédurale. En générant la fosse sur le plan procédural, cela a permet de modifier certains aspects de son apparence, tels que l'épaisseur, la couleur, etc.


 

IV) Les algorithmes

Que ce soit dans les jeux vidéo ou dans les films, la génération procédurale peut être très utile pour la création d’un jeux vidéo ou d’une vidéo, même amateur. Nous avons vu que ce travail est fait grâce à des algorithmes. Ce sont eux qui régissent la manière dont va être produit et/ou reproduit le contenu souhaité.  Mais même si les algorithmes utilisent des formules mathématiques et règles définies par les développeurs, l’aléatoire joue un rôle important.  On peut parler d’ici d’aléatoire contrôlé, car l’aléatoire est synonyme de chaos alors que la procédure est justement la représentation quasi-allégorique de l’organisation. En effet, plus l’algorithme va utiliser des nombres aléatoires, plus la représentation finale sera nulle et donc inexploitable. C’est pourquoi les développeurs à partir de suites de nombres aléatoires mais aussi de formules mathématiques, de règles définies et de contraintes vont donner à leurs création une certaine cohérence.

Bien entendu, il peut arriver que des motifs reviennent souvent et que des bugs apparaissent lors de la génération d’un monde de manière procédurale. Comme sur cette image de Minecraft sur la version alpha du jeu.


 

V)L’Algorithme de Perlin

Dans cette partie nous allons nous intéresser à un des plus répandu des algorithmes de génération procédural. L'algorithme ou bruit de Perlin tire son nom du professeur new-yorkais Kenneth H. Perlin, même s'il est plus communément appelé Ken Perlin. Il est à l’origine du Media Resarch Lab de NYU, l'Université de New York. De plus, il est aujourd'hui directeur du Games for Learning Institute. C'est en 1985 qu'il invente le bruit de Perlin, invention qui est aujourd'hui incontournable dans l'infographie.  Ce processus est bien entendu une génération procédurale qui permet de simuler de façon très réaliste de nombreux éléments de la nature comme l'eau, l'herbe, les nuages, le marbre, le bois, … Mais il est aussi utilisé pour la génération de reliefs et de terrains, la génération d'irrégularités dans la surface de solides et de nombreuses autres applications.

Nous allons essayer de comprendre son principe et son fonctionnement :

La première étape de l'algorithme consiste à former une fonction de bruit, c'est-à-dire une fonction f:N→R qui, à une valeur donnée, associe une valeur qui semble aléatoire. Il est important de remarquer que ce bruit pourra donc être reproduit, pour une même valeur. C'est très important, car si l'on souhaite par exemple l'utiliser pour générer une image, celle-ci ne doit pas systématiquement changer à chaque génération.

Calque ou Bruit 2D

Cette image, en niveaux de gris dont la nuance représente la hauteur à chaque position du terrain, s’appelle du Bruit tellement cela ne ressemble à rien. Cependant avec un viewer de terrain, ce bruit pourrait donner cela :

 

Nous allons ensuite choisir certains points régulièrement espacés dans le calque pour prendre des valeurs aléatoires associées. Toutes les positions entre ces points choisis seront interpolées (linéairement ou autrement). L'interpolation est « une opération mathématique permettant de construire une courbe à partir des données d'un nombre fini de points ». En d'autres termes, c'est un processus qui consiste à définir une fonction continue prenant certaines valeurs en certains points, et ce selon certains critères que l'on choisit de s'imposer.

On voit déjà apparaître l'un des paramètres de l'algorithme : le caractère régulièrement espacé des points choisis. Ce paramètre est noté fréquence.

Choisir une fréquence de 2 signifie que vous prendrez 9 points sur votre calque aléatoire pour commencer les interpolations. En effet, vous coupez un segment en 2 parties, vous avez donc 3 points (le premier, celui du milieu et le dernier). Et comme nous nous plaçons en deux dimensions, nous avons 3x3 valeurs à prendre. Une fois que tout le calque aura été interpolé entre ces valeurs, nous allons créer un autre calque avec d'autres interpolations, plus fines.

Chaque nouveau calque sera créé exactement de la même manière que le premier, à la différence près que nous prendrons une fréquence située un octave au dessus de la fréquence associée au calque précédent. Il faut donc connaître la fréquence de chacun des calques et la fréquence de départ. La fréquence d'un calque étant la fréquence du calque précédent x la fréquence de départ.

Ainsi, avec une fréquence de départ de 2, le premier calque aura une fréquence de 2, le second aura 4, le troisième aura 8, puis 16, 32 ... et ainsi de suite. Nous voyons ici apparaître un autre paramètre de notre algorithme : le nombre de calques à utiliser. Ce paramètre est en fait un nombre d'octaves à utiliser.

Notez qu'il n'est pas nécessaire que toutes les valeurs choisies aléatoirement sur un calque le soient aussi sur le suivant. L'essentiel étant que les calques correspondent à des interpolations de plus en plus fines, même s'ils ne correspondent pas aux même valeurs aléatoires choisies.

Et la partie astucieuse de l'algorithme consiste à additionner tous ces calques de manière pondérée, de sorte à ce que les calques interpolés finement influent moins que ceux interpolés grossièrement. C'est justement cette pondération qui permet de générer des montagnes, des vallées ...


VI) Implémentation

       Tout d’abord, il faut crée le calque aléatoire. Pour cela, deux boucles, un générateur de nombre aléatoire et une structure de donnée.

struct calque *random;

random = init_calque(taille,1);

for (i=0; i<taille; i++)

    for (j=0; j<taille; j++)

           random->v[i][j]=aleatoire(256);

Maintenant le remplissage des calques. Chaque calque agira sur le calque aléatoire avec sa propre fréquence, qui changera d’un octave à l’autre.

for (n=0; n<octaves; n  ){

  for(i=0; i<taille; i++)

    for(j=0; j<taille; j++) {

      a = valeur_interpolee(i, j, f_courante, random);

      mes_calques[n]->v[i][j]=a;

    }

  f_courante*=frequence;

}

Le traitement effectué par ces boucles imbriquées consiste à aller récupérer les valeurs de chacune des positions du calque en cours de traitement. Ces valeurs viennent d'une interpolation. L'interpolation dépend du calque aléatoire (c'est lui qui contient les valeurs de base), de la fréquence f_courante (pour déterminer quelles valeurs du calque aléatoire nous allons prendre) et de la position (i,j) en cours.

 

L’interpolation des valeurs. Nous devons choisir certaines valeurs sur le calque aléatoire, puis interpoler entre ces valeurs. La fréquence va découper notre calque en plusieurs parties. Tout d'abord, il faut déterminer dans quelle partie le point (i,j) est situé, puis récupérer les valeurs du calque aléatoire aux positions qui délimitent cette partie, puis interpoler entre ces valeurs.

La détermination des bornes entourant le point recherché se fait par division entière en fonction de la taille d'un intervalle.

int valeur_interpolee(int i, int j, int frequence, struct calque *r){

  /* déterminations des bornes */

  int borne1x, borne1y, borne2x, borne2y, q;

  float pas;

  pas = (float)r->taille/frequence;

 

  q = (float)i/pas;

  borne1x = q*pas;

  borne2x = (q 1)*pas;

 

  if(borne2x >= r->taille)

    borne2x = r->taille-1;

 

  q = (float)j/pas;

  borne1y = q*pas;

  borne2y = (q 1)*pas;

 

  if(borne2y >= r->taille)

    borne2y = r->taille-1;

 

  /* récupérations des valeurs aléatoires aux bornes */

  int b00,b01,b10,b11;

  b00 = r->v[borne1x][borne1y];

  b01 = r->v[borne1x][borne2y];

  b10 = r->v[borne2x][borne1y];

  b11 = r->v[borne2x][borne2y];

 

  int v1  = interpolate(b00, b01, borne2y-borne1y, j-borne1y);

  int v2  = interpolate(b10, b11, borne2y-borne1y, j-borne1y);

  int fin = interpolate(v1, v2, borne2x-borne1x , i-borne1x);

  return fin;

}

Et voici la fonction interpolate qui effectue une interpolation non linéaire :

int interpolate(int y1, int y2, int n, int delta){

    if (n==0)

                       return y1;

    if (n==1)

                        return y2;

  

    float a = (float)delta/n;

    float v1 = 3*pow(1-a, 2) - 2*pow(1-a,3);

   float v2 = 3*pow(a, 2)   - 2*pow(a, 3);

   return y1*v1   y2*v2;

 }

 

Une fois que tous les calques ont été déterminés, il nous reste à les ajouter en tenant

compte de la persistance de chacun. C'est à ce moment là que peuvent surgir les incohérences. Si jamais l'addition finale dépasse 255, nous aurons droit à une aberration. Voici un exemple :

Les valeurs supérieures 255 repassent à 0 lorsqu'elles sont enregistrées. C'est la raison pour laquelle il faut surveiller les valeurs obtenues et les corriger si besoin est.

 

/* calcul de la somme de toutes les persistances, pour ramener les valeurs dans un intervalle acceptable */

sum_persistances = 0;

for (i=0; i<octaves; i++)

  sum_persistances =mes_calques[i]->persistance;

/* ajout des calques successifs */

for (i=0; i<taille; i++)

  for (j=0; j<taille; j++){

    for (n=0; n<octaves; n++)

      c->v[i][j] =mes_calques[n]->v[i][j]*mes_calques[n]->persistance;

    /* normalisation */

    c->v[i][j] =  c->v[i][j] / sum_persistances;

  }

 

La variable sum_persistances permet d'obtenir une moyenne de tous les calques, pondérés par leur persistance. Ceci garantit des valeurs correctes. Ça a aussi l'avantage et rehausser les niveaux si les persistances sont trop basses. Mais attention, espace discret oblige, en rehaussant des petites valeurs, on perd en précision et on peut obtenir des résultats comme celui là:

 

Et voici un résultat que l’algorithme de Perlin peut aboutir.


Source :

https://fr.wikipedia.org/wiki/G%C3%A9n%C3%A9ration_proc%C3%A9durale

https://fr.wikipedia.org/

http://indius.org/dossiers/generation-procedurale-jeu-video/

https://www.developpez.net/forums/d1562443/applications/developpement-2d-3d-jeux/debat-aleatoire-generation-procedurale/

http://cochoy-jeremy.developpez.com/tutoriels/2d/introduction-bruit-perlin/

http://www.numerama.com/sciences/133517-la-generation-procedurale-ou-comment-le-jeu-video-devient-infini.html

http://khayyam.developpez.com/articles/algo/perlin/

https://www.youtube.com/watch?v=yle2LScFdWs

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *