Discussions apparemment similaires...
Discussion : Auteur Réponses : Affichages : Dernier message
  Quel module ou language pour interface animée html starmindfr 20 1 151 05-13-2013 06:36 PM
Dernier message: Xenos
  Algorithme pour créer un personnage avec des caractéristiques équitables. Stromae 25 4 402 09-03-2010 01:03 AM
Dernier message: Argorate
  Recherche d'une idée d'algorithme pour traitement d'une chaine Kishan 6 919 06-10-2009 08:59 PM
Dernier message: MdE

Poster une réponse 
 
Note de cette discussion :
  • Moyenne : 0 (0 vote(s))
  • 1
  • 2
  • 3
  • 4
  • 5
Carte aléatoire - quel algorithme pour un tracé correct ?
Auteur Message
Harparine Hors ligne
Senior Member
****

Messages : 474
Inscription : Mar 2007
Message : #1
Carte aléatoire - quel algorithme pour un tracé correct ?
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 2

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 ?

07-04-2010 01:01 PM
Visiter le site internet de cet utilisateur Trouver tous les messages de cet utilisateur Citer ce message dans une réponse
Gwym Hors ligne
Member
***

Messages : 59
Inscription : Mar 2009
Message : #2
Carte aléatoire - quel algorithme pour un tracé correct ? (Ce message a été modifié le : 07-04-2010 04:46 PM par Gwym.)
Bonjour,

(07-04-2010 01:01 PM)Harparine a écrit :  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
[Image: infinite5.gif]
donnent une carte de ce type
[Image: infinite6.gif]

(07-04-2010 01:01 PM)Harparine a écrit :  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)
[Image: yh_mapgen_test_grid.png]

Le bruit pseudo aléatoire généré sans la grille (echelle 1:16) :
[Image: yh_mapgen_test_noise.png]

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 :
[Image: yh_mapgen_test_1-16_low.png]

A l'échelle 1:1 (un pixel = 1 case dans le jeu) voilà ce que ça donne le détail d'une côte :
[Image: yh_mapgen_test_1-16.jpg]

(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 !!)
07-04-2010 04:33 PM
Trouver tous les messages de cet utilisateur Citer ce message dans une réponse
Harparine Hors ligne
Senior Member
****

Messages : 474
Inscription : Mar 2007
Message : #3
Carte aléatoire - quel algorithme pour un tracé correct ?
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

07-05-2010 01:13 AM
Visiter le site internet de cet utilisateur Trouver tous les messages de cet utilisateur Citer ce message dans une réponse
Roworll Hors ligne
Posting Freak
*****

Messages : 1 082
Inscription : Dec 2006
Message : #4
Carte aléatoire - quel algorithme pour un tracé correct ?
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.

Quand on te dit qu'un projet est terminé à 90%, prépare toi pour les 90% suivant
Ninety-Ninety Rule

"Une guerre de religions, c'est quand deux peuples s'entretuent pour savoir qui a le meilleur ami imaginaire"
Vu sur IRC
07-05-2010 06:58 AM
Trouver tous les messages de cet utilisateur Citer ce message dans une réponse
Harparine Hors ligne
Senior Member
****

Messages : 474
Inscription : Mar 2007
Message : #5
Carte aléatoire - quel algorithme pour un tracé correct ?
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.
@+

07-05-2010 11:40 AM
Visiter le site internet de cet utilisateur Trouver tous les messages de cet utilisateur Citer ce message dans une réponse
Roworll Hors ligne
Posting Freak
*****

Messages : 1 082
Inscription : Dec 2006
Message : #6
Carte aléatoire - quel algorithme pour un tracé correct ?
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.


Pièce(s) jointe(s)
.zip  RM - Geography Generation Rules.zip (Taille : 684,87 Ko / Téléchargements : 60)

Quand on te dit qu'un projet est terminé à 90%, prépare toi pour les 90% suivant
Ninety-Ninety Rule

"Une guerre de religions, c'est quand deux peuples s'entretuent pour savoir qui a le meilleur ami imaginaire"
Vu sur IRC
07-05-2010 12:29 PM
Trouver tous les messages de cet utilisateur Citer ce message dans une réponse
Harparine Hors ligne
Senior Member
****

Messages : 474
Inscription : Mar 2007
Message : #7
Carte aléatoire - quel algorithme pour un tracé correct ?
Merci beaucoup.
@+

07-05-2010 12:44 PM
Visiter le site internet de cet utilisateur Trouver tous les messages de cet utilisateur Citer ce message dans une réponse
Delkaes Hors ligne
Member
***

Messages : 196
Inscription : Mar 2008
Message : #8
Carte aléatoire - quel algorithme pour un tracé correct ? (Ce message a été modifié le : 07-05-2010 09:03 PM par Delkaes.)
(07-05-2010 06:58 AM)Roworll a écrit :  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 7

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

07-05-2010 03:12 PM
Trouver tous les messages de cet utilisateur Citer ce message dans une réponse
Poster une réponse 




ContactJeuWeb - Crée ton jeu par navigateurRetourner en hautRetourner au contenuVersion bas-débit (Archivé)Syndication RSS