Bonjour,

Dans le cadre d'un jeu en environnement 3D, je cherche des méthodes pour générer des grottes dans du relief.

Actuellement le choix que nous avons fait c'est de générer un terrain de manière procédurale. Ce terrain est une "heightmap" et n'a donc pas la possibilité d'avoir plusieurs "planchers" les uns sous les autres.
Notre idée c'est de "creuser" (littéralement) le terrain ainsi generé en utilisant un systeme de chemins (grottes) dont le parcours est défini par des courbes de bezier (cela permet d'avoir peu de points de reference en mémoire pour tracer de grandes distances)

Ce choix a été motivé par le fait que des generations de type heightmap ou bezier sont relativement peu couteuses en terme de mémoire et relativement rapides egalement.

Ma requete c'est d'avoir vos avis sur ce choix et les axes pour l'améliorer ou bien le remplacer par une autre méthode plus efficace.

Je rappelle encore que je souhaite juste des idées, des concepts, voire des formules mathématiques, mais pas de code.

Merci par avance.

Romuald

Il me semble que minecraft utilise des "perlin worms".

Si j'etais toi, je ne m'occuperais pas du cout de la generation. Je m'occuperais des proprietes des generateurs. Une fois que tu auras trouve la technique de generation qui fait des carvernes comme tu les aimes, tu pourras te poser la question de comment les generer rapidement.

Le perlin noise est vraiment pas mal pour la génération de grottes, en tout cas avec dans Terraria-like j'ai eu des galleries presque "potables" en vraiment très peu de temps avec ( https://www.dropbox.com/s/kcdra27gy3980vz/Screen23.png?dl=0 , c'est un vieux screen et ça pourrait être bien mieux si j'avais passé plus de temps dessus), et ça doit fonctionner aussi bien en 3D.

Par contre niveau performances je peux pas vraiment dire, un jeu 3D demandant bien plus qu'un jeu 2D.

Le 04 février 2015 à 18:39:11 [notch] a écrit :
Il me semble que minecraft utilise des "perlin worms".

Notch je vais regarder de près ce que c'est.

Le 04 février 2015 à 19:25:53 godrik a écrit :
Si j'etais toi, je ne m'occuperais pas du cout de la generation. Je m'occuperais des proprietes des generateurs. Une fois que tu auras trouve la technique de generation qui fait des carvernes comme tu les aimes, tu pourras te poser la question de comment les generer rapidement.

C'est en effet une bonne méthode mais le truc c'est que je n'ai pas vraiment trouvé de techniques sur le net. Peut etre que mes mots clés n'etaient pas les bons ....

Salut, si je raconte pas de connerie avec des heightmap ont peut pas avoir de cavité qui se retourne sur elle-même, de tunnel ou de grotte vue que ce sont des valeurs d'élévation du terrain donc je croie que faut utilisé des voxel pour faire ça .

romuald, je me rappelle de plein d'algo de generation de labyrinthe. Ce que tu cherches ca a l'air pareil mais en 3d. Un petit coup de google: http://www.astrolog.org/labyrnth/algrithm.htm

Le 04 février 2015 à 22:27:35 godrik a écrit :
romuald, je me rappelle de plein d'algo de generation de labyrinthe. Ce que tu cherches ca a l'air pareil mais en 3d. Un petit coup de google: http://www.astrolog.org/labyrnth/algrithm.htm

Alors des algos de labyrinthes orthogonaux en 3D j'en ai deja codés (j'utilise la methode suivante etendue en 3D [http://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe#Algorithmes_de_construction_de_labyrinthes])
mais je ne sais pas si ca peut coller au niveau rendu.
Bien sur il faudrait etendre le concept tout simplement en se "promenant" dans le sol en 3D et en prenant différents chemins (un peu comme l'algo de generation des arbres dont on a parlé il y a peu)

Le 04 février 2015 à 21:00:13 LEGriffemort a écrit :
Salut, si je raconte pas de connerie avec des heightmap ont peut pas avoir de cavité qui se retourne sur elle-même, de tunnel ou de grotte vue que ce sont des valeurs d'élévation du terrain donc je croie que faut utilisé des voxel pour faire ça .

En effet ce n'est pas possible "juste" en generant la heightmap mais il est possible de "creuser".
Si tu generes une height map ET un labyrinthe en 3D de manière séparées, tu peux les combiner en faisant l'unt moins l'autre pour generer le terrain final.
Je crois (mais pas sur, la je demande vos avis) qu'avec des fonctions de bruits de perlin en 3D, au final tu fais la meme chose : tu generes une surface avec une fonction et tu soustrais avec une autre fonction de bruit qui genere des cavités (perlin worms) : bref la methode reste la meme, on "creuse" virtuellement le sol.
A moins peut etre qu'il existe directement des fonctions fractales 3D qui créent tout d'un coup, mais la c'est trop haut niveau pour moi.

Pour info, LEGriffemort, mon algo de heightmap possède des "bugs" dans certaines conditions (en fonction des parametres) qui me permettent d'avoir des irrégularités dans le terrain comme des falaises (bref des discontinuité dans l'interpolation quoi) et du coup ca rend pas mal.
Avec une heightmap on peut faire pas mal de choses : la seule limite c'est avoir deux points Y pour les memes coordonnées X et Z c'est impossible.

Pour rebondir sur le sujet original, j'ai codé une bibliothèque de generation de bruit cohérent (je crois que mon algo se rapproche d'une somme de "bruits de valeurs", dont les amplitudes et fréquences d'un bruit sont liées à celles des autres. Je ne pense pas que ce soit un bruit de Perlin mais bon ... je ne suis pas un puriste : ca me convient ).

Au final , je génère des heightmaps comme on peut le voir ds la littérature à ce sujet mais je l'ai surtout détournée pour créer des cavités.

Je génère donc une heightmap (avec peu d'octaves car ici ce n'est pas important). Le niveau de hauteur est utilisé pour 3 choses :
- je compare ce niveau avec un seuil : en dessous de ce seuil il y a présence de grotte (sur le plan horizontal X/Y)
- je prend la valeur du niveau pour déterminer la "profondeur moyenne" de la grotte dans le sol (pseudo aleatoire)
- je prend la valeur du niveau également pour déterminer le rayon de la grotte (pseudo aleatoire)

Du coup avec juste une generation de bruit simplex 2 octaves, j'arrive à avoir un tracé en 3D de grottes.

Le 04 février 2015 à 19:36:42 hexabeast a écrit :
Le perlin noise est vraiment pas mal pour la génération de grottes, en tout cas avec dans Terraria-like j'ai eu des galleries presque "potables" en vraiment très peu de temps avec ( https://www.dropbox.com/s/kcdra27gy3980vz/Screen23.png?dl=0 , c'est un vieux screen et ça pourrait être bien mieux si j'avais passé plus de temps dessus), et ça doit fonctionner aussi bien en 3D.

Par contre niveau performances je peux pas vraiment dire, un jeu 3D demandant bien plus qu'un jeu 2D.

Merci pour l'info du coup ca me convient et je vais meme pousser le vice à l'utiliser pour ma generation de terrain ... peut etre ...
Et niveau performances bah c'est une fonction assez simple, j'utilise peu d'octaves (2) donc ca ne prend pas trop de temps...non vraiment c'est un bon choix. Merci encore.

Voici un petit exemple de la génération.

Les grottes ici ont un parcours qui fait des "boucles" ceci est du au seuillage que j'effectue et qui ne prend qu'une certaine "couche" du bruit généré. Mais le rendu pour notre jeu sera suffisant pour le moment. Je verrai si c'est un problème une fois appliqué en 3D.

Les variations de teinte rouge donnent la variation de bruit originale : elle me permet d'effectuer des décisions sur la profondeur et la hauteur de la grotte.

[https://drive.google.com/file/d/0BxBruWUrihIBT1QtVDhYSndNYmF5UjZrZVBldjRnZ0h0eXpr/view?usp=sharing]

Et voici un aperçu avec une octave de plus : Bah la ca ressemble à qq chose.
Le rouge c'est une grotte "profonde" et le vert c'est une grotte proche du niveau de la surface.

[https://drive.google.com/file/d/0BxBruWUrihIBMlNPSUNTS25sVTRDek5BbkhBZ1paYi0yXzBN/view?usp=sharing]

Voici un petit screenshot du réseau de grottes généré par le bruit cohérent
[https://drive.google.com/file/d/0BxBruWUrihIBRTJPNnlBdmtYWGM/view?usp=sharing]

Il faut imaginer que la topologie finale c'est juste la heightmap à laquelle on soustrait ce réseau et hop ça "creuse"

Je relance le sujet de génération de grottes car je bute sur un problème.
Je cherche à améliorer le rendu de grotte (cf post précédent) car ça allait pour un prototype mais le rendu n'est pas top : d'un il me faut 2 bruits 2D pour le générer, et de deux, la "hauteur" de la grotte est toujours la meme (en fait ca me fait des grottes de section "rectangulaires") et ça c'est pas top.

Bref je cherche à générer l'équivalent des perlin worms (voir post précédent le précédent) mais en 3D et c'est la que ça coince.

J'ai codé une méthode de bruit 3D, calée sur la méthode de bruit 2D dont vous pouvez voir les résultats, et cela me donne ça :
[https://drive.google.com/file/d/0BxBruWUrihIBYWhXdzg2cUkxSnc/view?usp=sharing]

En fait c'est logique, le résultat n'est pas un réseau que j'obtiens mais une "nappe" (bon sur l'image on ne voit pas bien sauf au premier plan on voit le coté "nappe 3D" : c'etait difficile de faire un screenshot qui rende bien car l'image que vous voyez tient dans un volume cubique de 6000 cubes unitaires de coté et comme ya du LOD dans l'affichage bref ....)

Pour la 2D, ma technique etait de generer une nappe de bruit 2D et de prendre uniquement le bruit entre 0.45 et 0.55 par exemple (le bruit est normalisé entre 0.0 et 1.0).

Pour la 3D j'ai fait la même mais le résultat me donne ces nappes. J'ai essayé de combiner des bruits en peu au hasard en tâtonnant pour voir si je pouvais arriver à un résultat mais pour le moment je bute.

J'espère avoir été clair dans ma requête.
si vous voulez des éclaircissements, des détails, je suis dispo.
Si vous aviez des conseils, je suis preneur.

Merci par avance.

Comme je ne vois pas de réponse sur mon problème de grotte avec bruit 3D et que je ne m'en sors pas, je suis retourné au mode "bruit 2D".

Je génère donc un bruit 2D sur le plan "latitude-longitude" et un deuxième bruit 2D pour faire l'altitude de la grotte. Avec ces deux bruits j'ai donc le sol de mes grottes : reste à générer aléatoirement la hauteur de la grotte.

Un aperçu d'ensemble (avec des couleurs chatoyantes)
[https://drive.google.com/open?id=0BxBruWUrihIBMHZfalZZSmZlWGM]
Les discontinuités viennent du fait qu'il y a du LOD donc parfois certains chunks n'apparaissent pas quand ils sont loin mais en s'approchant les détails s'affichent et la continuité est là)

Ici un morceau de la grotte de près (certains puristes devraient reconnaître la texture utilisée)
[https://drive.google.com/open?id=0BxBruWUrihIBS2xBdXBlNGNEWDg]
Là sur l'image ça donne un coté assez "cylindrique", ou plutôt disons "homogène" quant a la section de la grotte mais j'ai parfois des rendus moins bien surtout quand il y a une variation forte sur l'axe de l'altitude.

Je relance ma question : quelles méthodes utilisez vous pour générer des grottes en 3D : merci par avance.

Voici les liens autorisés sans connexion :
[https://drive.google.com/file/d/0BxBruWUrihIBMHZfalZZSmZlWGM/view?usp=sharing]
et
[https://drive.google.com/file/d/0BxBruWUrihIBS2xBdXBlNGNEWDg/view?usp=sharing]

Merci pour l'info.

Mais en fait, on ne dirait pas tellement une grotte, c'est une grotte en négatif

oui bien sur
Le but c'est quand meme de voir le tracé complet

Sur quel point tu bloques avec le bruit en 3D ? Avec du simplex ou perlin noise tu dois obtenir ce genre de résultat :

Pas forcément réaliste pour des grottes mais il y a moyen de s'arranger par la suite. Ce que tu appelle l'effet de nappe à mon avis vient du fait que tu place la tolérance trop haut. Si 0.5 te donne de bons résultats en 2D, ça ne sera pas forcément pareil en 3D. Fais attention aussi il me semble que le simplex est normalisé de -1 à 1.

Ok juste pour info mon bruit est normalisé sur [0-1] mais ça revient au meme.

Sinon le résultat que tu donnes est exactement ce que j'ai et mon problème est que je n'arrive pas à "m'arranger par la suite" comme tu dis. Je suis preneur de conseils la dessus.
J'essaye de jouer sur la période du bruit et la tolérance du seuil pour "affiner" ces grottes mais au final ca ne me convient pas.

[HS] quel est ton environnement de rendu que tu utilises ?

C'est une image piquée sur internet. Sinon j'utilise BlitzBasic et j'ai joué un peu avec le simplex noise + marching cubes, ça donne ça par exemple :

Pour générer des tunnels avec des chambres plus grandes, regarde ce lien : http://ephenationopengl.blogspot.fr/2012_05_01_archive.html

En plus du premier seuil, il rajoute un second seuil limite. En gros il fait un cube seulement si le seuil est compris entre 0.45 et 0.55, à priori ça fonctionne.