Recherche d'un bon algorithme de génération de carte du monde [fermé]

Je travaille sur un jeu de type civilisation et je recherche un bon algorithme pour générer des cartes du monde semblables à la Terre. J'ai expérimenté quelques alternatives, mais je n'ai pas encore trouvé de vrai gagnant.

Une option consiste à générer une carte d' altitude en utilisant le bruit de Perlin et à ajouter de l'eau à un niveau tel qu'environ 30% du monde soit terrestre. Bien que le bruit Perlin (ou des techniques fractales similaires) soit fréquemment utilisé pour le terrain et soit raisonnablement réaliste, il n'offre pas beaucoup de contrôle sur le nombre, la taille et la position des continents résultants, ce que j'aimerais avoir du point de vue du gameplay.

Une deuxième option consiste à commencer avec une graine à une tuile positionnée au hasard (je travaille sur une grille de tuiles), à déterminer la taille souhaitée pour le continent et à chaque tour, ajouter une tuile qui est horizontalement ou verticalement adjacente au continent existant jusqu'à ce que vous avez atteint la taille souhaitée. Répétez pour les autres continents. Cette technique fait partie de l'algorithme utilisé dans Civilization 4. Le problème est qu'après avoir placé les premiers continents, il est possible de choisir un emplacement de départ qui est entouré par d'autres continents, et ne conviendra donc pas au nouveau. En outre, il a tendance à engendrer des continents trop rapprochés, ce qui donne quelque chose qui ressemble plus à un fleuve qu'à des continents.

Quelqu'un connaît-il un bon algorithme pour générer des continents réalistes sur une carte basée sur une grille tout en gardant le contrôle de leur nombre et de leur taille relative?

Vous pouvez vous inspirer de la nature et modifier votre deuxième idée. Une fois que vous avez généré vos continents (qui ont tous à peu près la même taille), faites-les se déplacer et tourner au hasard, se heurter, se déformer et s'éloigner les uns des autres. (Remarque: ce n'est peut-être pas la chose la plus simple à mettre en œuvre.)

Edit: Voici une autre façon de le faire, avec une implémentation - Polygonal Map Generation for Games .

Je vous suggère de reculer et

1. Pensez à ce qui fait de «bons» continents.
2. Écrivez un algorithme qui peut distinguer une bonne disposition continentale d'une mauvaise.
3. Affinez l'algorithme afin de pouvoir quantifier la qualité d'une bonne mise en page.

Une fois que vous l'avez en place, vous pouvez commencer à implémenter un algorithme qui devrait être formé comme ceci:

• Générez des continents de merde et améliorez-les.

Pour vous améliorer, vous pouvez essayer toutes sortes d'astuces d'optimisation standard, qu'il s'agisse de recuit simulé, de programmation génétique ou de quelque chose de complètement ad hoc , comme déplacer un carré d'arête choisi au hasard de n'importe où sur le continent vers le bord opposé au centre de masse du continent. Mais la clé est de pouvoir écrire un programme capable de distinguer les bons continents des mauvais. Commencez avec des continents dessinés à la main ainsi que vos continents de test, jusqu'à ce que vous obteniez quelque chose que vous aimez.

J'ai écrit quelque chose de similaire à ce que vous recherchez pour un clone de Civilization 1 de type économiseur d'écran automatisé. c'est abstrait.

La "carte" spécifie le nombre de continents, la variance de la taille du continent (par exemple, 1,0 conserverait tous les continents avec la même superficie approximative, jusqu'à 0,1 permettrait aux continents d'exister avec 1 / 10ème de la masse du plus grand continent), la superficie maximale des terres (en pourcentage) à générer et le biais foncier central. Une "graine" est distribuée au hasard autour de la carte pour chaque continent, pondérée vers le centre de la carte selon le biais central (par exemple, un biais faible produit des continents distribués plus similaires à la Terre, où un biais central élevé ressemblera davantage à un Pangée). Puis pour chaque itération de croissance, les «graines» attribuent des tuiles de terrain selon un algorithme de distribution (plus à ce sujet plus tard) jusqu'à ce qu'une superficie maximale de terrain soit atteinte.

L'algorithme de distribution des terres peut être aussi précis que vous le souhaitez, mais j'ai trouvé des résultats plus intéressants en appliquant divers algorithmes génétiques et en lançant les dés. Le "Game of Life" de Conway est vraiment facile à démarrer. Vous devrez ajouter QUELQUE logique consciente du monde entier pour éviter que des choses comme les continents ne se développent les unes dans les autres, mais pour la plupart, les choses prennent soin d'elles-mêmes. Le problème que j'ai trouvé avec les approches plus fractales (ce qui était ma première inclination) était que les résultats semblaient trop structurés, ou conduisaient à trop de scénarios nécessitant des règles de contournement de hacky pour obtenir un résultat qui ne semblait pas encore assez dynamique. En fonction de l'algorithme que vous utilisez, vous souhaiterez peut-être appliquer une passe de "flou" au résultat pour éliminer des éléments tels que les abondantes tuiles océaniques à un carré et les côtes en damier. Dans le cas où quelque chose comme un continent serait engendré entouré de plusieurs autres et n'ayant nulle part où se développer, déplacez la graine vers un nouveau point sur la carte et poursuivez la croissance. Oui, cela peut signifier que vous vous retrouvez parfois avec plus de continents que prévu, mais si c'est vraiment quelque chose que vous ne voulez vraiment pas, une autre façon d'éviter cela est de biaiser les algorithmes de croissance afin qu'ils favorisent la croissance dans la direction la moins proche des autres. des graines. Au pire (à mon avis en tout cas), vous pouvez marquer une série comme invalide lorsqu'une graine n'a nulle part où se développer et générer une nouvelle carte. Assurez-vous simplement de définir un nombre maximum de tentatives, donc si quelque chose d'irréaliste est spécifié (comme installer 50 continents à pondération égale sur une carte 10x10), cela ne passe pas éternellement à essayer de trouver une solution valide.

Je ne peux pas garantir la façon dont Civ etc. le fait, et bien sûr ne couvre pas des choses comme le climat, l'âge des terres, etc., mais en jouant avec l'algorithme de croissance des graines, vous pouvez obtenir des résultats assez intéressants qui ressemblent à des continents, des archipels, etc. utiliser la même approche pour produire des rivières, des chaînes de montagnes, etc. d'aspect «biologique».

J'ai créé quelque chose de similaire à votre première image en JavaScript. Ce n'est pas super sophistiqué mais ça marche:

http://jsfiddle.net/AyexeM/zMZ9y/

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Untitled Document</title>

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script>
<style type="text/css">
    #stage{
        font-family: Courier New, monospace;
    }
    span{
        display: none;
    }
    .tile{
        float:left;
        height:10px;
        width:10px;
    }
    .water{
        background-color: #55F;
    }
    .earth{
        background-color: #273;
    }
</style>
</head>

<body>


<div id="stage">

</div>

<script type="text/javascript">

var tileArray = new Array();
var probabilityModifier = 0;
var mapWidth=135;
var mapheight=65;
var tileSize=10;

var landMassAmount=2; // scale of 1 to 5
var landMassSize=3; // scale of 1 to 5


$('#stage').css('width',(mapWidth*tileSize)+'px');


for (var i = 0; i < mapWidth*mapheight; i++) {

    var probability = 0;
    var probabilityModifier = 0;

    if (i<(mapWidth*2)||i%mapWidth<2||i%mapWidth>(mapWidth-3)||i>(mapWidth*mapheight)-((mapWidth*2)+1)){

        // make the edges of the map water
        probability=0;
    }
    else {

        probability = 15 + landMassAmount;

        if (i>(mapWidth*2)+2){

            // Conform the tile upwards and to the left to its surroundings 
            var conformity =
                (tileArray[i-mapWidth-1]==(tileArray[i-(mapWidth*2)-1]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-mapWidth]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-1]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-mapWidth-2]));

            if (conformity<2)
            {
                tileArray[i-mapWidth-1]=!tileArray[i-mapWidth-1];
            }
        }

        // get the probability of what type of tile this would be based on its surroundings 
        probabilityModifier = (tileArray[i-1]+tileArray[i-mapWidth]+tileArray[i-mapWidth+1])*(19+(landMassSize*1.4));
    }

    rndm=(Math.random()*101);
    tileArray[i]=(rndm<(probability+probabilityModifier));

}

for (var i = 0; i < tileArray.length; i++) {
    if (tileArray[i]){
        $('#stage').append('<div class="tile earth '+i+'"> </div>');
    }
    else{
        $('#stage').append('<div class="tile water '+i+'"> </div>');
    }
}

</script>

</body>
</html>

L' article sur la génération de carte polygonale décrit la génération de carte étape par étape qui désengage les polygones de Voronoi.

Ce gars donne aussi tous les codes sources. C'est Flash (ActionScript 3 / ECMAScript) mais transposable à tout autre langage orienté objet

Ou essayez d'utiliser des algorithmes implémentés dans certains logiciels d'environnement fractal comme TerraJ

Penser simplement ici:

Choisissez des points de départ et attribuez à chacun une taille tirée au sort (espérée). Vous pouvez maintenir un tirage de taille distinct pour les continents planifiés et les îles planifiées si vous le souhaitez.

Faites une boucle sur les éléments terrestres, et là où ils ne sont pas encore à la taille prévue, ajoutez un carré. Mais la partie la plus amusante est de peser la chance que chaque élément voisin soit le seul. Une chose suggérée qui pourrait prendre en compte:

1. Distance à l '«autre» terrain le plus proche. De plus, c'est mieux génère de larges espaces océaniques. Plus près est mieux fait des canaux étroits. Vous devez décider si vous allez également laisser les bits fusionner.
2. Distance de la graine. Plus près est mieux signifie des masses terrestres compactes, plus loin est mieux signifie de longs morceaux
3. Nombre de carrés de terrain existants adjacents. La pondération en faveur de nombreuses cases adjacentes vous donne une côte lisse, préférer peu vous donne beaucoup d'entrées et de péninsules.
4. Présence de cases «ressources» à proximité? Cela dépend des règles du jeu, du moment où vous générez un carré de ressources et si vous voulez le rendre facile.
5. Autoriserez-vous les morceaux à s'approcher ou à se joindre aux pôles?
6. ??? je ne sais pas quoi d'autre

Continuez jusqu'à ce que toutes les masses terrestres aient atteint la taille prévue ou ne puissent plus croître pour une raison quelconque.

Notez que le fait d'ajouter le paramètre à ces facteurs de pondération vous permet d'ajuster le type de monde généré, ce qui est une fonctionnalité que j'ai appréciée dans certaines Civs.

De cette façon, vous devrez faire la génération de terrain sur chaque bit séparément.

Vous pouvez essayer un algorithme de carré de diamant ou un bruit perlin pour générer quelque chose comme une carte de hauteur. Ensuite, attribuez des valeurs de plages à ce qui apparaît sur la carte. Si votre "hauteur" va de 0 à 100, alors faites 0 - 20 eau, 20 - 30 plage, 30 - 80 herbe, 80 - 100 montagnes. Je pense que notch a fait quelque chose de similaire dans le mini-artisanat, mais je ne suis pas un expert, je suis juste dans un état d'esprit carré de diamant après l'avoir finalement fait fonctionner.

Je pense que vous pouvez utiliser une approche de style "programmation dynamique" ici.

Résolvez d'abord les petits problèmes et combinez intelligemment les solutions pour résoudre des problèmes plus importants.

A1= [elliptical rectangular random ... ]// list of continents with area A1 approx. 
A2= [elliptical rectangular random ... ]// list of continents with area A2 approx.
A3= [elliptical rectangular random ... ]// list of continents with area A3 approx.
...
An= [elliptical rectangular random ... ]// list of continents with area An approx.

// note that elliptical is approximately elliptical in shape and same for the other shapes.

Choose one/more randomly from each of the lists (An).

Now you have control over number and area of continents.

You can use genetic algorithm for positioning them 
as you see "fit" ;)

Ce sera très bien de jeter un oeil à quelques "algorithmes de mise en page graphique"

• Algorithmes basés sur la force
• Algorithme génétique pour la mise en page graphique

Vous pouvez les modifier en fonction de votre objectif.

J'ai eu une idée de création de carte similaire à la réponse des plaques tectoniques. Il est allé quelque chose comme ceci:

1. balayer les carrés de la grille en donnant à chaque carré un carré «terre» si rnd <= 0,292 (le pourcentage réel de terre sèche sur la planète terre).
2. Migrez chaque parcelle de terrain d'un carré vers son voisin le plus proche. Si les voisins sont équidistants, allez vers le plus gros morceau. Si les morceaux sont de taille égale, choisissez-en un au hasard.
3. si deux carrés de terrain se touchent, regroupez-les en un seul morceau, en déplaçant tous les carrés comme un à partir de maintenant.
4. Répétez à partir de l'étape 2. Arrêtez lorsque tous les blocs sont connectés.

Ceci est similaire au fonctionnement de la gravité dans un espace 3D. C'est assez compliqué. Un algorithme plus simple pour vos besoins fonctionnerait comme suit:

1. Déposez n carrés de terrain de départ à des positions x, y aléatoires et à des distances acceptables les unes des autres. Ce sont des graines pour vos continents. (Utilisez le théorème de Pythagore pour vous assurer que les graines ont une distance minimale entre elles et toutes les autres.)
2. faire apparaître une case de terrain à partir d'une case de terrain existante dans une direction aléatoire, si cette direction est une case d'océan.
3. répétez l'étape 2. Arrêtez-vous lorsque les carrés de terrain occupent 30% de la taille totale de la carte.
4. si les continents sont suffisamment proches les uns des autres, déposez des ponts terrestres comme vous le souhaitez pour simuler un effet de type Panama.
5. Laissez tomber des îles plus petites et aléatoires comme vous le souhaitez pour un look plus naturel.
6. pour chaque carré "d'île" supplémentaire que vous ajoutez, découpez les mers intérieures et les carrés de lac des continents en utilisant le même algorithme en sens inverse. Cela maintiendra le pourcentage de terres au montant souhaité.

Faites-moi savoir comment cela fonctionne. Je ne l'ai jamais essayé moi-même.

PS. Je vois que c'est similaire à ce que vous avez essayé. Sauf qu'il met en place toutes les graines à la fois, avant de commencer, donc les continents seront suffisamment éloignés et s'arrêteront lorsque la carte sera suffisamment remplie.

Je n'ai pas vraiment essayé cela, mais cela a été inspiré par la réponse de David Johnstone concernant les plaques tectoniques. J'ai essayé de l'implémenter moi-même dans mon ancien projet Civ et quand il s'agissait de gérer les collisions, j'avais une autre idée. Au lieu de générer directement des tuiles, chaque continent se compose de nœuds. Distribuez la masse à chaque nœud puis générez une série de continents "blob" en utilisant une approche 2D Metaball. La tectonique et la dérive des continents seraient ridiculement faciles à «simuler» simplement en déplaçant les nœuds. En fonction de la complexité que vous souhaitez atteindre, vous pouvez même appliquer des éléments tels que des courants pour gérer le mouvement des nœuds et générer des chaînes de montagnes qui correspondent à des frontières de plaques qui se chevauchent. N'ajouterait probablement pas grand chose au côté gameplay des choses,

Une bonne explication des metaballs si vous n'avez jamais travaillé avec eux auparavant:

http://www.gamedev.net/page/resources/_//feature/fprogramming/exploring-metaballs-and-isosurfaces-in-2d-r2556

Voici ce que je pense, puisque je suis sur le point d'implémenter quelque chose comme ça que j'ai pour un jeu en développement. :

Le monde divisé en régions. en fonction de la taille du monde, il déterminera le nombre de régions. Pour cet exemple, nous supposerons un monde de taille moyenne, avec 6 régions. Chaque zone de grille se divise en 9 zones de grille. ces zones de grille se divisent en 9 grilles chacune. (ce n'est pas pour le mouvement des personnages, mais simplement pour la création de cartes) Les grilles sont pour les biomes, les zones de grille sont pour les caractéristiques terrestres surplombantes (continent vs océan) et les régions sont pour le climat général. Les grilles se décomposent en tuiles.

Générés aléatoirement, les régions reçoivent des ensembles climatiques logiques attribués. Les zones de grille sont attribuées au hasard, par exemple; océan ou terre. Les grilles reçoivent des biomes attribués au hasard avec des modificateurs en fonction de leurs zones de grille et de leur climat, qu'il s'agisse de forêt, de désert, de plaine, de glacier, de marais ou de volcan. Une fois que toutes ces bases sont attribuées, il est temps de les mélanger, en utilisant une fonction basée sur un pourcentage aléatoire qui remplit les ensembles de tuiles. Par exemple; si vous avez un biome forestier, à côté d'un biome désertique, vous avez un algorithme qui diminue la probabilité qu'une tuile soit «forestière» et augmente qu'elle sera «déserte». Ainsi, à peu près à mi-chemin entre eux, vous verrez une sorte d'effet mélangé combinant les deux biomes pour une transition quelque peu douce entre eux. La transition d'une zone de grille à la suivante exigerait probablement un peu plus de travail pour assurer des formations logiques de masse continentale, comme par exemple un biome d'une zone de grille qui touche le biome d'une autre, au lieu d'avoir un simple pourcentage de commutation basé sur la proximité. Par exemple, il y a 50 tuiles du centre du biome au bord du biome, ce qui signifie qu'il y en a 50 du bord qu'il touche au centre du biome suivant. Cela laisserait logiquement un changement de 100% d'un biome à l'autre. Ainsi, à mesure que les tuiles se rapprochent de la frontière des deux biomes, le pourcentage se réduit à environ 60% environ. Il serait, je pense, imprudent de donner trop de chances de traverser des biomes loin de la frontière, mais vous voudrez que la frontière soit quelque peu mélangée. Pour les zones de grille, la variation en pourcentage sera beaucoup plus prononcée. Au lieu que le% descende à environ 60%, il ne tomberait qu'à environ 80%. Et une vérification secondaire devrait ensuite être effectuée pour s'assurer qu'il n'y a pas de tuile d'eau aléatoire au milieu d'un biome terrestre à côté de l'océan sans une certaine logique. Alors, connectez cette tuile d'eau à la masse océanique pour créer un canal pour expliquer la tuile d'eau, ou supprimez-la complètement. La terre dans un biome à base d'eau est plus facile à expliquer en utilisant des affleurements rocheux et autres.

Oh, un peu stupide, désolé.

Je placerais le terrain fractal selon une disposition que vous savez "fonctionne" (par exemple, grille 2x2, losange, etc., avec un peu de gigue) mais avec une distribution gaussienne qui amortit les pics vers les bords des centres du continent. Placez le niveau d'eau plus bas de manière à ce qu'il soit principalement terrestre jusqu'à ce que vous vous approchiez des bords.