Carte aléatoire - quel algorithme pour un tracé correct ?

[Harparine]

Salut à tous,

Je poste rarement dans la partie algorithme mais là, je sèche et j'en appelle aux lumières des scientifiques de formation

Depuis deux jours, je m'amuse à essayer de générer une carte aléatoire qui ait l'air crédible. J'ai commencé à expérimenter différentes méthodes de calcul pour voir laquelle a le meilleur résultat.

Tout d'abord, la marche aléatoire ou "marche de l'ivrogne" donne des résultats corrects pour générer des continents à la louche. Avec quelques variables pour "influencer l'aléatoire", j'obtiens une carte d'un monde fantastique assez fun. Ainsi, si plusieurs "ivrognes" partent d'un même point, il y a moins de "trous" au centre de mon continent. De même, des chemins aléatoires très courts partant de points proches permettent de générer des archipels. Le défaut de cette technique est de donner des continents assez "poreux". Un exemple ici.

Ensuite, voulais générer des cartes de régions, en traçant les lignes d'une côte. J'ai découvert que la technique des chemins auto-évitant (le principe du jeu Snake) permettait de produire un résultat sympa. Par contre, j'ai du mal à implémenter un algorithme qui fonctionne (mon chemin fini par s'enfermer, ne trouvant plus de porte de sortie --> mon exemple ici) car je pense que je n'ai pas les outils mathématiques nécessaires. Ma question est donc :

Qui a déjà mis en place un chemin auto-évitant ? ... ou comment effectuer un tracé aléatoire qui ne se touche pas ? --> avis aux challengers, ça peut constituer un bon défi pour la communauté.

Une autre possibilité de génération de carte serait d'assembler des solides pour obtenir une forme de base puis en affiner les contours, de façon aléatoire ou avec des fractales.

De même , je pense tester la génération aléatoire de polygones, dont les côtés seraient rendus de plus en plus irréguliers.

Bref, à vos claviers si vous aimez les défis : qui produira la carte aléatoire la plus convaincante ?

[Gwym]

Bonjour,

Ensuite, voulais générer des cartes de régions, en traçant les lignes d'une côte.

Bon, ce n'est pas du chemin auto-évitant comme demandé, mais du bruit pseudo aléatoire généré à partir de lignes :
http://www.gamasutra.com/view/feature/33...php?page=4

ces lignes

donnent une carte de ce type

De même , je pense tester la génération aléatoire de polygones, dont les côtés seraient rendus de plus en plus irréguliers.

Pour ma part j'utilise un algorithme de génération pseudo aléatoire ("pseudo" = reproductible pour pouvoir reproduire la même carte à vonlonté à partir d'une même graine) proposé dans l'article de gamasutra, avec au lieu des lignes d'initialisation une grille de valeurs qui donne les "grandes lignes" de la carte. En gros c'est simplement de la génération de terrain 3D de type "bruit de perlin", dont je ne prend que 2 dimensions ! Ca date une peu (codé en aout 2009 et plus amélioré depuis), mais voici en gros comment j'avais procédé :

A partir d'une grille prédéfinie manuellement pour dessiner les grandes lignes des planètes à souhait (ici grille de 16 * 32, les valeurs intermédiaires sont calculées linéairement)


Le bruit pseudo aléatoire généré sans la grille (echelle 1:16) :


Le résutat donne ce type de carte (avec des couleurs tout à fait arbitraires fonction de l'altitude pour l'instant, représentant grossièrement eau profonde, eau peu profonde plage et terres intérieures) à l'échelle 1:16 :


A l'échelle 1:1 (un pixel = 1 case dans le jeu) voilà ce que ça donne le détail d'une côte :


(L'inconvénient est qu'on a toujours des côtes assez lisses, il n'y a pas de "falaises", l'avantage est que cette carte de 16384 * 8192 = 134217728 cases ne prend en mémoire que 500 octets environ !!)

[Harparine]

Excellent, merci de l'article. J'aime beaucoup le rendu de ta carte.
Je pense que je vais partir là-dessus, en générant tout de même les figures de base de façon aléatoire plutôt qu'à la main. En fait, j'aime beaucoup l'aléatoire et je cherche à tout faire de façon aléatoire (l'idée de la carte est venue en me penchant sur la génération aléatoire de noms de villes, pour mon site GUNoF --> http://gunof.net/cite_medievale_lieu-dit).
@+ et merci encore !
Harparine

[Roworll]

Si ça t'intéresse, je peux jeter un œil dans les règles du Campaign Law de mon vieux Rolemaster.
De mémoire, ils proposent quelques méthodes pour générer aléatoirement des continents sur une carte hexagonale.
Ça peut toujours servir de base.

En parallèle, l'algo sur lequel j'aimerais mettre la main est celui de Myth Weavers pour leur générateur de donjons.

[Harparine]

Si tu as les règles à portée de main, ça peut toujours donner des idées. Effectivement, le générateur de donjons est vraiment sympa.
@+

[Roworll]

Un petit scan valant mieux que de grandes explications, voici les trois pages correspondantes.

Bon, ça vaut ce que ça vaut, mais pour avoir testé le système, je trouve que c'est une méthode assez viable qui peut, avec quelques ajustements, générer des terrains assez différents.

Bonne lecture.

[Harparine]

Merci beaucoup.
@+

[Delkaes]

Si ça t'intéresse, je peux jeter un œil dans les règles du Campaign Law de mon vieux Rolemaster.
De mémoire, ils proposent quelques méthodes pour générer aléatoirement des continents sur une carte hexagonale.
Ça peut toujours servir de base.

En parallèle, l'algo sur lequel j'aimerais mettre la main est celui de Myth Weavers pour leur générateur de donjons.

J'ai la version windows sur mon pc depuis un moment, voici un lien retrouvé avec petite explication : http://web.archive.org/web/2008020312381...esign.html

Tu as même le code source \o/
Amusez vous bien (h)

EDIT : c'est jamis buck qui a fait ce générateur, myth ne fait que le maintenir sur leur site.