Projet image 2016 : Génération d'un écosystème

De Ensiwiki
Aller à : navigation, rechercher
Project schedule.png
Titre du projet Projet image 2016 : Génération d'un écosystème
Cadre Projets de spécialité
Page principale Projets de spécialité image

Encadrants Thomas Delame Pierre-Luc Manteaux


Étudiants


Introduction

Durant la dernière décennie, les mondes virtuels numériques ont connu une expansion sans précédent. En effet, que ce soit avec la commercialisation à grande échelle imminente de l’Oculus Rift, ou avec le développement de jeux vidéo toujours plus réalistes, il est devenu primordial de pouvoir simuler efficacement des environnements tridimensionnels réalistes.

C’est dans ce cadre précis que s’inscrit notre projet, puisqu’il consiste à générer de manière pseudo-aléatoire un monde tridimensionnel, contenant plusieurs espèces d’animaux et de végétaux qui interagissent dynamiquement et, évidemment, en temps réel de manière à simuler un écosystème.

Le résultat attendu serait donc une île générée à partir d’un ensemble de paramètres initiaux, et possédant une ou plusieurs montagnes, forêts, rivières et plages. Cette île serait peuplée au minimum de deux espèces différentes (une proie et un prédateur), ainsi que d’une espèce de plante comestible.

Le projet de spécialité est pour nous l’occasion de travailler sur un sujet qui nous passionne. En effet, nous l’avons conçu et proposé à nos deux encadrants, Pierre-Luc Manteaux et Thomas Delame.


Objectifs du projet

Le but du projet est d’obtenir un rendu plaisant d’un écosystème dont la dynamique pourra apparaître comme réaliste aux yeux d’un observateur. Il est donc naturel de catégoriser les objectifs en deux sous-ensembles d'objectifs qui convergeront afin d'obtenir la simulation finale.


Objectifs pour la création de la carte

La surface qui nous intéresse sera l’équivalent d’une île de sorte à limiter les problèmes de modélisation et de performances en taille.

Le terrain généré doit être cohérent aux yeux d'un utilisateur. Dit autrement, le paysage généré de l'île doit pouvoir ressembler à un paysage réel.

Cette création de terrain peut se décomposer en deux sous-tâches :

  • La géographie de la carte doit apparaître comme réaliste (les plages devront jouxter la mer, il pourra y avoir des montagnes à l'intérieur de l'île...) ;
  • Les différentes régions devront être décorées en accord avec l'environnement (des carottes ne peuvent pas apparaître au milieu de la mer...)


Objectifs pour les animaux

Les animaux considérés seront pour ce projet des animaux “existants” dans le sens où ce sont des animaux connus (lapins, loups...) et les modèles seront prédéfinis dans des fichiers qui seront importés.

La tâche la plus importante ici est de programmer l’intelligence artificielle de ces animaux. Cette intelligence doit à la fois prendre en compte les autres animaux et l’environnement de sorte à ce que les animaux puissent effectuer des tâches simples (fuite, chasse, reproduction, mort…) pour obtenir un écosystème visuellement plausible.


Génération de terrain

Création de la carte

Géométrie

La première étape est de segmenter la carte afin de définir plusieurs régions homogènes.

Pour effectuer un découpage géométrique qui n'apparaisse pas de manière flagrante aux yeux d'un observateur, une bonne façon de faire est de construire un diagramme de Voronoi. En configurant de manière correcte les seeds de départ, la construction du diagramme permet d'obtenir une subdivision peu ou prou uniforme de la carte selon une géométrie complexe.


Shutter Island Map1.png
Géographie

Une fois la géométrie de la carte définie, il reste maintenant à affecter à chaque cellule du diagramme de Voronoi un environnement (un Biome).

La carte obtenue doit cependant apparaître cohérente. Pour ce faire, on construit les règles de génération de sorte à ce que la carte induite puisse être vue comme celle d'un environnement vraisemblable. Les règles utilisées sont dans les grandes lignes :

  • Les bords de la carte sont de la mer (nous nous sommes limités à une île)
  • Le centre de la carte est préférentiellement de la terre
  • La terre jouxtant la mer est du sable
  • L'intérieur de l'île peut contenir des lacs et des montagnes.

La diagramme précédent devient donc la carte suivante, avec les correspondances couleur suivantes :

  • Bleu foncé : Mer
  • Jaune : Sable
  • Vert : Plaines
  • Bleu clair : Lac
  • Rouge : Montagne
Shutter Island Map2.png
Height Map

Pour la génération de la carte, on ne peut pas, comme dans certaines approches naïves de génération de carte topographique (Height Map) se contenter d'un simple bruit cohérent (Par exemple le bruit de Perlin). En effet, bien que le bruit cohérent permette d'obtenir un relief continu, on ne peut pas contrôler la forme du bruit généré, et donc s'assurer que le relief généré correspond à la carte précédement générée.

On s'inspire cependant de la technique de génération de bruit cohérent que l'on contrôle à l'aide de la carte. (Un lecteur peu familier avec les techniques de génération est invité à se renseigner sur la génération de bruit de Perlin afin de comprendre la suite de cette sous-section).

Dans la construction des octaves constituant le bruit, on va contrôler les valeurs du bruits tirées ainsi que l'interpolation sur chaque octave à l'aide de la carte. Par exemple, si le position d'un point au sein d'une octave est dans la mer, sa valeur sera tirée dans une plage de valeurs négatives, alors que si c'est un point correspondant à une plaine, on s'assurera que sa valeur est positive (et petite). On contrôle ensuite la fonction d'interpolation sur l'octave pareillement en fonction de biomes pour prendre en compte leur étendue géographique. Par exemple, une montagne aura une influence très locale, alors qu'une plaine pourra éventuellement s'étendre.

Octave 1 :

Shutter Island Heighttree1.png

Octave 2 :

Shutter Island Heighttree2.png

...

Ceci nous permet d'obtenir un bruit cohérent et en accord avec la carte sous-jacente. Les résultats de ce calcul de Height Map peuvent être visibles dans les captures d'écran de la partie Rendu.

Rendu du terrain

Rendu primaire

Cette première version de l'île correspond à une élévation simple de la carte selon les hauteurs diagrammes de Voronoi triangularisés de manière grossière.

Le plan orange délimite le niveau de la mer.

Shutter Island Primal map.png
Tessellation et Levels of Details

La "Tessellation", ou "maillage" dans la langue de Vercingétorix, consiste en la construction d'un ensemble de triangle pour représenter le contour d'un objet tridimensionnel. Cette étape est particulièrement importante dans le monde de l'informatique graphique car les principales primitives graphiques permettent d'afficher des triangles (aussi bien sous OpenGL que sous CUDA).

La dernière version d'OpenGl, à savoir OpenGL4, apporte de multiples améliorations et extensions, dont les "Tessellation Shaders". Ces derniers permettent de déporter le calcul du maillage d'un objet en trois dimensions vers la carte graphique (GPU). Cela permet de gagner en performance, et les primitives offertes permettent de "déléguer" ledit calcul à un algorithme inclus dans OpenGL4.

Ainsi, grâce à l'implémentation de "Tessellation Shaders", notre maillage est raffiné (chaque triangle issu de la triangulation primaire du diagramme de Voronoi est subdivisé en plusieurs dizaines, voire centaines, de triangles). Cela permet d'obtenir une carte tridimensionnelle infiniment plus détaillée, et de lui appliquer une carte des hauteurs échantillonnée avec une grande précision. Le monde tridimensionnel généré tend vers le réalisme par le biais de la topographie détaillée obtenue par le biais du raffinement du maillage.

Ci-dessous, on peut voir le raffinement du maillage par incrémentation du coefficient de "Tessellation". Plus ce coefficient est important, plus les triangles initiaux sont subdivisés, et plus la carte gagne en détails.

Shutter Island Tessellation Factor.gif

Un autre avantage des "Tessellation Shaders" est qu'ils permettent de gérer le "Level of Details" (Niveau de Détails) sur le GPU. En quelques mots, la gestion du "LoD" consiste à adapter le raffinement du maillage d'un objet tridimensionnel en fonction de la distance à la "caméra" (le point de l'espace à partir duquel la scène est dessinée et rendue) de ce dernier.

Un exemple sera sûrement plus parlant. Considérons le lapin ci-dessous, ou plutôt les différents rendus de ce même lapin.

Shutter Island LoD.jpg

Selon le degré de raffinement (en d'autres termes le nombre de triangles du maillage) utilisé lors du dessin du dit léporidé, il est plus ou moins détaillé. L'idée centrale est d'utiliser la version très détaillée lorsque notre petit mangeur de carottes est au premier plan de la scène, et la version "cubique" (ou Picassienne) lorsqu'il est en arrière-plan. Cela n'aura que peu d'impact pour l'utilisateur, qui, vraisemblablement, ne focalisera pas son attention sur un détail de l'arrière-plan. Néanmoins, un maillage moins détaillé implique un temps de calcul moindre (ici, on passe de presque 70000 triangles à à peine 80...), ce qui augmente la fluidité et la rapidité d'exécution du programme (objectif "60FPS").

On peut voir l'impact de la gestion du "LoD" sur le monde tridimensionnel généré : plus on se rapproche du "cratère" (un lac en devenir), plus ce dernier est détaillé et lissé.

Shutter Island Tessellation.gif
Texturisation

Malgré le fait que la résolution ait été augmentée par la Tessellation, la frontière des biomes est toujours définie par le diagramme de Voronoi.

Il faut donc visuellement cacher ces lignes droites qui limitent les diagrammes de Voronoi au niveau du rendu en effectuant un mélange (blending) de textures de sorte à avoir des transitions continues d'un biome à l'autre.

Pour ce faire, on calcule, en plus de la Height Map une Texture Map. Celle-ci contient les informations nécessaires au blending de texture en chaque point sous la forme d'un ensemble de coefficients qui indiquera en un ensemble de points échantillonnés quelle proportion de quelle texture appliquer.

Shutter Island Texture.png
Ajout de l'eau

Un point important pour le réalisme de la carte est la gestion des biomes aqueux.


  • Ajout de la mer

La mer est simplement définie par un plan texturé à côte 0. Outre la simplicité d'implémentation, cela donne aux boids un critère pour connaître la présence de la mer puisque cette dernière n'est visible que lorsque la côte du terrain devient négative.

  • Ajout des lacs

L'ajout des lacs passe par le calcul des composantes connexes parmi l'ensemble des biomes de type Lac. Ensuite, pour chaque composante connexe, on calcule la hauteur moyenne du lac, ce qui permet, à l'aide de l'information de la taille des cellules de Voronoi sous-jacentes, d'ajouter un lac aux bonnes dimensions.


Shutter Island Lake.png



Shutter Island Water.png
Rendu final du terrain

L'ajout d'une skybox à la carte obtenue tout au long des différentes transformations précédemment décrites aboutit au rendu suivant :


Shutter Island Skybox.png

Gestion du comportement des animaux

Simulation par boids

La gestion de la faune et la flore a été réalisée en utilisant des boids. Un boid est un agent autonome conscient de son environnement qui se déplace à l'aide de forces qui lui sont appliquées.

Voici un exemple de boid pour le déplacement de groupe :

IslandGeneratorSpeboidsMove.gif


Afin d'améliorer le comportement des boids un automate d'état a été ajouté ainsi que des variables d'état telles que la faim, la soif et la fatigue. L'automate suivant est une version simplifiée de l'automate implémenté.

IslandGeneratorAutomata.png

Choix des boids

Afin de peupler le monde plusieurs types de boids ont été créés :

  • Des boids qui se déplacent : le loup et le lapin
  • Des boids immobiles : l'arbre et la carotte.


Boid Loup
Boid Lapin


Boid arbre
Boid carotte

Les arbres et les carottes ont été implémentés en utilisant des boids afin de pouvoir gérer pour chaque entité une zone de séparation différente. Ainsi un animal reste éloigné d'un arbre comme il le serait avec un autre animal afin de ne pas lui rentrer dedans.

Comportement des boids

Voici une liste non exhaustives de comportements associé aux différents boids :

Déplacement de groupe
Contournement d'obstacle


Un lapin mange une carotte
Les lapins fuient les loups


Un loup attaque un groupe de lapins
Boire près d'un lac

Rendu en temps réel

Optimisations réalisées :

  • Parallélisation du calcul de la position des boids
  • Envoi simultané des données à la carte graphique
  • Parcours des boids à l'aide de d'une grille

Il est possible d'afficher plus 1000 boids simultanément à 60 fps (test réalisé sur une machine à l'Ensimag en E303).

Interaction des animaux avec le monde

Les animaux obéissent selon différents comportements comme par exemple :

  • Se situer à la bonne altitude
  • Connaître la position des lacs pour y boire et ne pas rentrer dedans
  • Ne pas sortir des terres

Conclusion

Nous nous sommes réellement investi dans ce projet qui s'est au final révélé être passionnant. Le rendu final est conforme à l'objectif que nous nous étions fixé. C'est un projet qui nous a beaucoup plu et dont nous avons beaucoup appris. Nous comptons poursuivre sa réalisation sur notre temps libre. Le travail reste ouvert aux lecteurs intéressés qui peuvent suivre l'avancement sur le github du projet.

Bibliographie

Génération d'environnement

Création de la carte

Polygonal Map Generation for Games, Red Blob Games

Cet article propose une bonne introduction au problème de génération de carte. Même si l'exemple proposé peut sembler relativement simple, il permet de bien en comprendre les enjeux.

Boids

Référence sur les boids

The Nature of Code - Chapter 6, Daniel Shiffman

Ce chapitre tiré de The Nature of Code constitue une excellente introduction à la programmation de boids.

Automate d'états

Finite state machines

Une technique pour complexifier le comportement des boids est de les munir d'un automate d'état.

OpenGL

Tessellation

Tessellation based Terrain Rendering

Ce rapport de master contient une très bonne présentation du principe de tessellation en OpenGL4, et fourni qui plus est un code fonctionnel.

Credits

Meshes

Les meshes suivants ont été récupérés :