Génération procédurale de régions sur l'île

29

J'ai actuellement des îles qui ressemblent à ceci:

île

Et je veux le subdiviser procéduralement en régions, comme ceci:

île avec régions

Quel algorithme fait ce que je recherche? Avez-vous des suggestions sur la façon de créer des régions cohérentes comme dans l'image du bas. Votre aide est appréciée.

domisum
la source
Comment avez-vous obtenu cette image de l'île en premier lieu? L'avez-vous généré, et si oui, comment l'avez-vous atteint?
Vaillancourt
Je l'ai obtenu d'un générateur de cartes en ligne.
domisum
Désolé pour le retard dans la mise à jour de ma réponse - il a fallu plus de temps pour rentrer à la maison qu'initialement prévu. J'ai ajouté quelques illustrations et liens.
Pikalek
Si vous avez obtenu cela d'un générateur en ligne, vous devriez regarder le générateur de carte Fantasy d'Azgaar . Il a des régions et des noms, avec des paramètres personnalisables, et WB.SE dit bonjour. C'est un github, donc vous pourrez peut-être vérifier leur code.
Anoplexian

Réponses:

40

Dans le monde réel, ces frontières provinciales suivent souvent des caractéristiques géologiques comme les rivières.

Alors peut-être qu'une bonne approche serait de modéliser la géologie de l'île et d'en faire tomber les frontières?

Red Blob Games a de bons articles sur ce sujet, avec de beaux résultats.

Son approche semble impliquer l'utilisation de la tessellation Voronoi et définir les rivières comme les limites entre les cellules.

Consultez les autres articles sur son site, il a beaucoup écrit sur le sujet de la génération de cartes .

île

Bram
la source
3
Notez que dans le monde réel, les divisions politiques ou administratives ont parfois aussi des divisions arbitraires, généralement des lignes droites (par exemple le long des lignes latitud / longitud, des lignes entre les sommets des montagnes, etc.).
Pablo H
2
@PabloH Bon point, bien que les frontières droites semblent être un phénomène de l'ère coloniale post-médiévale. Mais comme nous ne connaissons pas le réglage du problème des PO, cela pourrait être pertinent
Sentry
27

Je résoudrais ce problème avec deux passes de diagrammes de Voronoi:

Premier passage: partitionnement de région

La première passe utiliserait une distribution de points quelque peu clairsemée (c'est-à-dire que la distance entre les points devrait être relativement grande) afin de diviser grossièrement l'île en régions (voir la note ci-dessous concernant la génération de points). Générez ensuite un diagramme de Voronoi basé sur ces points. Cela divisera l'île en régions polygonales autour de chaque point, comme indiqué ci-dessous:

entrez la description de l'image ici

Deuxième passage: randomisation des frontières

Maintenant que l'île a été divisée en régions, la prochaine étape consiste à «brouiller» les frontières entre elles. Pour ce faire, générez une nouvelle couche de points en utilisant une distribution de points plus compacte (c'est-à-dire que la distance entre les points doit être petite) et utilisez à nouveau ces points pour créer un autre diagramme de Voronoi. Ensuite, pour chaque petite région, affectez-la à une plus grande région en vérifiant son point de départ. Cela se traduira par des frontières plus dentelées entre les grandes subdivisions. Voici un aperçu de ce à quoi il ressemble avec les deux diagrammes de Voronoi en place:

entrez la description de l'image ici

Et voici cette même zone montrant uniquement les limites finales:

entrez la description de l'image ici

Commentaires sur Point Generation

En ce qui concerne la génération de points, j'aime utiliser une distribution de disques de Poisson afin d'obtenir une distribution relativement agréable et uniforme des points. L'autre option courante consiste à obtenir une distribution homogène de la même manière: utiliser l'algorithme de Lloyd sur un ensemble de points aléatoires «réguliers». LLoyd est plus facile à coder, mais peut prendre un certain nombre d'essais et d'erreurs pour déterminer le nombre de passes nécessaires pour donner le résultat souhaité.

Un problème potentiel avec cette approche est que le partitionnement de première passe peut générer de très petites régions. Si vous ne les voulez pas dans votre résultat final, je les fusionnerais simplement avec une région adjacente aléatoire.

Notes finales

Les illustrations que j'ai fournies sont des images tramées, mais cette technique fonctionne également avec les représentations polygonales / vectorielles.

Pikalek
la source
1
Pour les plans d'étage procéduraux, c'est ce que je fais, faire un diagramme de Voronoi à partir de points à l'intérieur de la région (l'île), construire une grille (elle n'a pas besoin d'être rectangulaire, pour votre cas une grille déformée) qui englobe la même région, puis calculez les intersections booléennes de la grille et des Voronoi, calculez les surfaces et affectez à un arbre de données (liste de liste, tableau dentelé, etc ... quelle que soit la structure de données que vous préférez) selon le 0,6% de la plus petite cellule de la grille, vous obtiendrez des cellules manquantes, mais vous pouvez comparer votre grille de sélection avec l'original pour trouver et réaffecter à votre arbre.
Felipe Gutierrez
Vous avez ajouté des images! C'est exactement ce que je fais dans un but différent
Felipe Gutierrez
4

MineCraft le fait très bien, et son algorithme de génération mondiale a été analysé et documenté de manière approfondie.

Il existe différentes descriptions de l'algorithme, l'une d'elles ici: https://github.com/UnknownShadow200/ClassiCube/wiki/Minecraft-Classic-map-generation-algorithm

Le cœur de l'algorithme est un générateur de bruit Perlin . Cela contrôle directement l'élévation (plus ou moins, car l'étape suivante pour creuser des grottes peut également changer la surface), ainsi que la génération de biomes. Quelque chose comme le générateur de biome est probablement ce que vous souhaitez utiliser pour créer vos zones.

(Une ancienne version de celui-ci) est documentée , fondamentalement, cela fonctionne en utilisant deux générateurs de bruit Perlin différents, un pour la "température", un pour la "précipitation", puis en choisissant le biome parmi ces deux. Les variables elles-mêmes (température et précipitations) ne sont pas vraiment utilisées plus tard dans le jeu; par exemple, les déserts n'ont pas de pluie, mais le jeu le détermine à partir de la propriété "désert", pas à partir de la valeur des précipitations d'origine.

Il existe différents outils en ligne pour générer une carte du biome à partir d'une graine aléatoire, l'un d'eux est mineatlas.com . Je suppose que, en interne, ils utilisent un serveur java qui utilise les classes internes de MineCraft lui-même; Je ne sais pas si l'un de leurs codes source est disponible directement.

Guntram Blohm soutient Monica
la source
4

Un algorithme typique utilisé, par exemple, par Azgaar ( code source ). Est à peu près comme ceci:

  1. divisez votre masse continentale en zones plus petites, par exemple par triangulation delauny ou cellules voronoi.
  2. déterminez (au hasard ou autrement) des emplacements de "départ" pour vos cultures, royaumes, religions ou tout ce que vous voulez simuler.
  3. déterminer (aléatoirement ou non) un "facteur de croissance" pour chacun d'eux. Plus vous avez de facteurs de croissance, moins votre carte finale est uniforme.
  4. Maintenant, parcourez vos royaumes (etc.) et, en fonction du facteur de croissance, faites-les se propager dans les tuiles vides environnantes jusqu'à ce que la carte entière soit remplie.
  5. Vous voudrez probablement finir par redresser un peu les bordures, en changeant les cellules qui n'ont qu'un seul voisin dans leur propre couleur et qui sont autrement entourées par une autre de cette couleur.
À M
la source
3

Si vous êtes intéressé à le faire en format vectoriel plutôt qu'en approches raster, j'ai écrit un article de blog il y a quelque temps à peu près exactement à ce sujet.

http://blog.particracy.com/worlds-and-their-geography/

L'idée est de commencer avec un maillage (généralement basé sur Voronoi) et d'agrandir les régions de manière concentrique à partir de points semés au hasard et suffisamment espacés.

Wouter Lievens
la source
2

Quelle question amusante :) Cette approche est un peu basée sur les cellules de Vornoi, mais la métrique de distance n'est pas tout à fait euclidienne (j'ai utilisé la puissance de 1,5 au lieu de 2,0) et a un certain caractère aléatoire intégré. Il peut sauter par-dessus l'eau, ce qui n'est pas idéal.

Les régions voisines peuvent être fusionnées pour obtenir des formes plus intéressantes, ici j'ai en quelque sorte utilisé les N voisins les plus proches pour le déterminer.

Si vous êtes intéressé, je peux entrer dans plus de détails et partager le code Python.

carte 1 carte 2

NikoNyrh
la source