Discussion :

[Romuald_78]

Bonjour,

je recherche une méthode (algorithme, méthodologie, ...) pour arriver à générer des cours d'eau sur un relief.

J'ai codé une bibliothèque qui génère un bruit fractal pour le terrain : j'ai donc une topologie accidentée (montagnes vallées etc...) et la dessus je voulais rajouter des rivières.

Cette fonction de génération de terrain prend en paramètre les coords X et Y et ressort Z (sans s'occuper de ce qu'il y a sur X-1/X+1/Y-1.... c'est tout l'interet de ces generateurs de bruit coherent.

Je cherche donc un moyen similaire pour obtenir un tracé (cours d'eau) mais sans devoir interpoler/itérer sur un terrain existant : je voudrai juste avoir une fonction simple et à temps constant qui serait du type isRiver(x,y,z) en utilisant si possible du bruit de perlin (vu que j'ai deja la lib de prete) ou bien une autre méthode de calcul mais sans interpolation quelconque.

Le probleme avec les rivières c'est que par définition, on part d'un point et on "descend" la topologie. Mais peut etre que mon cours d'eau que je dois afficher depend d'une source située très loin et que je n'ai pas affichée/traitée. Ca m'embete d'itérer comme ca sur une grande distance pour afficher une petite portion de carte.

Merci par avance pour votre aide la dessus.

Romuald.

[yahiko]

L'algo le plus simple c'est de partir de tes sommets (hauteur max), puis de tracer ton cours d'eau de proche en proche en empruntant la pente locale minimale (de signe négatif évidemment)

EDIT : Désolé, je n'avais pas lu ton message entièrement.
Pour forcer ta rivière à se jeter dans la mer, une technique consiste appliquer l'algorithme A* sur ta topologie.

[Romuald_78]

Ouais mais du coup en faisant ca, je suis obligé de connaitre le point de source et d'itérer le tracé jusqu'à la zone que je veux afficher :je m'explique :

J'ai une carte generee par du bruit de perlin : par définition cette carte peut etre infinie : disons qu'elle a la taille d'un carré de 1 million de point de coté. Si je veux afficher juste une zone de la carte (un carré de 100 sur 100 quelque part) et bien avec l'algo de bruit, c'est rapide je genere chaque hauteur avec ma fonction de bruit Z = bruit(X,Y).
Mais pour savoir si il y a de l'eau en X/Y, il va falloir que je cherche les sources alentours et que je genere le terrain jusqu'à la zone à afficher. Et peut etre que le seul cours d'eau qui passe dans ma zone possède une source qui se situe à 10000 pixels de là : ce n'est pas envisageable de générer tout ca : moi je genere ma carte à la volée

En fait je cherche à savoir si il existe des méthodes mathématiques (ou autres) qui mle permettraient de generer des cours d'eau sans avoir à generer toute la map et itérer le tracé de l'eau.

Merci qd meme pour ton intervention.

[kolodz]

Ta problématique est que si tu génère qu'une partie de ta carte, tu ne sais pas si la génération "juste à côté" déclenché la création d'une rivière dans la zone que tu traite actuellement.

Il n'y a pas 300 solutions à ce problème :

Soit tu gère ces parties à l'avance. Sachant que tu peux limité la génération à une cuvette. Car si tu as un pique de hauteur ton cour d'eau ne le passera pas. (Sauf si tu gère l'accumulation d'eau)

Soit tu interdit la génération de rivière dans les nouvelles zones générées si celle-ci débouche sur la modification d'une partie existante de ta carte. (Cela se traduit par des zones interdite de spawn, utilisant la une propagation de l'interdiction par rapport au bord existant) Cela implique que les rivières relativement longues seront forcément créé vers des zones qui n'existe pas encore. (Il faudra aussi prendre en compte la prolongation des rivières en fonction des bords).
Si tu as un génération carte qui ne crée que très peu de cuvette, tu risque de te trouve avec beaucoup de zone interdit.

Pour des raisons de performance, une fois ton cour d'eau généré, tu devrait attaché la propriété "cour d'eau" à chaque case. Cela évitera beaucoup de calcul lors de l'affichage.
D'ailleurs, c'est ce que fait Minecraft pour la gestion de l'eau.


Cordialement,
Patrick Kolodziejczyk.

[Romuald_78]

Et si on applique un bruit de perlin, on peut récupérer les vecteurs des gradients de chaque point : vu que ce sont les dérivées du bruit (donc la "pente" du terrain en fait), ne pourrait-on pas utiliser ces informations pour le parcours de l'eau qui coule sur le terrain !?

[yahiko]

Si tu t'en tiens à une seule itération du bruit de Perlin, ça reste une éventualité (à tester cependant).

Si tu appliques plusieurs octaves pour générer ton terrain, ça risque par contre d'être difficile.

[Romuald_78]

Meme avec plusieurs octaves, il faudra sommer autant de pentes qu'il y a d'octaves pour en faire la resultante non ? Je me trompe ?
Du coup je vais réfléchir sur cette solution voir si j'arrive à obtenir un résultat satisfaisant.