Auf der Suche nach einem guten Algorithmus zur Generierung von Weltkarten [geschlossen]

Ich arbeite an einem Civilization-ähnlichen Spiel und suche nach einem guten Algorithmus zum Generieren erdähnlicher Weltkarten. Ich habe mit einigen Alternativen experimentiert, aber noch keinen echten Gewinner gefunden.

Eine Möglichkeit besteht darin, eine Höhenkarte mit Perlin-Rauschen zu erstellen und Wasser in einer Höhe hinzuzufügen, sodass etwa 30% der Welt Land sind. Während Perlin-Rauschen (oder ähnliche fraktalbasierte Techniken) häufig für Gelände verwendet wird und einigermaßen realistisch ist, bietet es nicht viel Kontrolle über die Anzahl, Größe und Position der resultierenden Kontinente, was ich gerne möchte aus spielerischer Sicht haben.

Eine zweite Möglichkeit besteht darin, mit einem zufällig positionierten Samen mit einer Kachel zu beginnen (ich arbeite an einem Kachelraster), die gewünschte Größe für den Kontinent zu bestimmen und in jeder Runde eine Kachel hinzuzufügen, die horizontal oder vertikal neben dem vorhandenen Kontinent liegt, bis Sie haben die gewünschte Größe erreicht. Wiederholen Sie dies für die anderen Kontinente. Diese Technik ist Teil des in Civilization 4 verwendeten Algorithmus. Das Problem besteht darin, dass nach dem Platzieren der ersten Kontinente ein Startort ausgewählt werden kann, der von anderen Kontinenten umgeben ist und daher nicht zum neuen passt. Außerdem neigt es dazu, Kontinente zu nahe beieinander zu spawnen, was zu etwas führt, das eher einem Fluss als Kontinenten ähnelt.

Kennt jemand zufällig einen guten Algorithmus zum Generieren realistischer Kontinente auf einer gitterbasierten Karte, während er die Kontrolle über deren Anzahl und relative Größe behält?

Sie könnten sich an der Natur orientieren und Ihre zweite Idee ändern. Sobald Sie Ihre Kontinente generiert haben (die alle ungefähr gleich groß sind), bringen Sie sie dazu, sich zufällig zu bewegen und zu drehen und zu kollidieren und sich gegenseitig zu deformieren und voneinander zu driften. (Hinweis: Dies ist möglicherweise nicht die einfachste Implementierung.)

Bearbeiten: Hier ist eine andere Möglichkeit, einschließlich einer Implementierung - Polygonale Kartengenerierung für Spiele .

Ich würde vorschlagen, dass Sie sich sichern und

1. Überlegen Sie, was "gute" Kontinente ausmacht.
2. Schreiben Sie einen Algorithmus, der ein gutes kontinentales Layout von einem schlechten unterscheiden kann.
3. Verfeinern Sie den Algorithmus, damit Sie quantifizieren können, wie gut ein gutes Layout ist.

Sobald Sie dies eingerichtet haben, können Sie mit der Implementierung eines Algorithmus beginnen, der wie folgt gestaltet sein sollte:

• Generiere beschissene Kontinente und verbessere sie dann.

Zur Verbesserung können Sie alle Arten von Standard-Optimierungstricks ausprobieren, unabhängig davon, ob es sich um simuliertes Annealing, genetische Programmierung oder etwas völlig Ad-hoc- Trick handelt, z. B. das Verschieben eines zufällig ausgewählten Kantenquadrats von der Stelle auf dem Kontinent zur Kante gegenüber dem Massenschwerpunkt des Kontinents. Der Schlüssel ist jedoch, ein Programm schreiben zu können, das gute von schlechten Kontinenten unterscheiden kann. Beginnen Sie mit handgezeichneten Kontinenten sowie Ihren Testkontinenten, bis Sie etwas bekommen, das Ihnen gefällt.

Ich habe etwas Ähnliches geschrieben, wie Sie es für einen automatisierten Bildschirmschoner-ähnlichen Klon von Civilization 1 suchen. Für die Aufzeichnung habe ich dies in VB.net geschrieben, aber da Sie in Ihrer Frage nichts über Sprache oder Plattform erwähnen, werde ich es behalten es abstrakt.

Die "Karte" gibt die Anzahl der Kontinente, die Abweichung der Kontinentgröße (z. B. 1,0 würde alle Kontinente mit derselben ungefähren Landfläche halten, bis zu 0,1 würde es Kontinenten ermöglichen, mit 1/10 der Masse des größten Kontinents zu existieren) und die maximale Landfläche an (als Prozentsatz) zu generieren, und die zentrale Landbias. Ein "Keim" wird für jeden Kontinent zufällig auf der Karte verteilt und gemäß der zentralen Vorspannung zur Mitte der Karte gewichtet (z. B. erzeugt eine niedrige Vorspannung verteilte Kontinente, die der Erde ähnlicher sind, wobei eine hohe zentrale Vorspannung eher einer ähnelt Pangaea). Dann weisen die "Samen" für jede Iteration des Wachstums Landplättchen gemäß einem Verteilungsalgorithmus zu (dazu später mehr), bis eine maximale Landfläche erreicht ist.

Der Landverteilungsalgorithmus kann so präzise sein, wie Sie möchten, aber ich habe interessantere Ergebnisse gefunden, indem ich verschiedene genetische Algorithmen angewendet und die Würfel gewürfelt habe. Conways "Game of Life" ist wirklich einfach zu beginnen. Sie müssen EINIGE global bewusste Logik hinzufügen, um zu vermeiden, dass Dinge wie Kontinente ineinander wachsen, aber zum größten Teil kümmern sich die Dinge um sich selbst. Das Problem, das ich bei fraktaleren Ansätzen fand (was meine erste Neigung war), war, dass die Ergebnisse entweder zu strukturiert aussahen oder zu zu vielen Szenarien führten, in denen Regeln für die Problemumgehung mit Hacky-Feeling erforderlich waren, um ein Ergebnis zu erzielen, das sich immer noch nicht dynamisch genug anfühlte. Abhängig von dem von Ihnen verwendeten Algorithmus möchten Sie möglicherweise einen "Unschärfe" -Pass über das Ergebnis anwenden, um Dinge wie reichlich vorhandene quadratische Ozeankacheln und karierte Küsten zu beseitigen. Für den Fall, dass so etwas wie ein Kontinent entsteht, der von mehreren anderen umgeben ist und nirgendwo mehr wachsen kann, verschieben Sie den Samen an einen neuen Punkt auf der Karte und setzen Sie die Wachstumspässe fort. Ja, es kann bedeuten, dass Sie manchmal mehr Kontinente als geplant haben, aber wenn Sie dies wirklich nicht wollen, können Sie die Wachstumsalgorithmen so beeinflussen, dass sie das Wachstum in die Richtung mit der geringsten Nähe zu anderen begünstigen Saat. Im schlimmsten Fall (meiner Meinung nach jedenfalls) können Sie eine Serie als ungültig markieren, wenn ein Samen nirgendwo mehr wachsen und eine neue Karte erstellen kann. Stellen Sie einfach sicher, dass Sie eine maximale Anzahl von Versuchen festlegen. Wenn also etwas Unrealistisches angegeben wird (z. B. das Anpassen von 50 gleichgewichteten Kontinenten auf ein 10x10-Board), wird nicht ewig versucht, eine gültige Lösung zu finden.

Ich kann nicht dafür bürgen, wie Civ usw. es macht, und natürlich nicht Dinge wie Klima, Landalter usw. abdecken, aber wenn Sie mit dem Samenwachstumsalgorithmus herumspielen, können Sie ziemlich interessante Ergebnisse erzielen, die Kontinenten, Archipelen usw. ähneln Verwenden Sie den gleichen Ansatz, um auch „organisch“ aussehende Flüsse, Gebirgszüge usw. zu produzieren.

Ich habe etwas Ähnliches wie Ihr erstes Bild in JavaScript erstellt. Es ist nicht super raffiniert, aber es funktioniert:

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>

Artikel zur polygonalen Kartengenerierung beschreiben die schrittweise Kartengenerierung ohne Voronoi-Polygone.

Dieser Typ gibt auch alle Quellcodes. Es ist Flash (ActionScript 3 / ECMAScript), aber auf jede andere objektorientierte Sprache übertragbar

Oder versuchen Sie, Algorithmen zu verwenden, die in einigen Software für fraktale Umgebungen wie TerraJ implementiert sind

Ich denke hier nur an die Manschette:

Wählen Sie einige Startpunkte aus und weisen Sie jedem eine zufällig gezeichnete (erhoffte) Größe zu. Wenn Sie möchten, können Sie für geplante Kontinente und geplante Inseln eine separate Größenzeichnung verwalten.

Durchlaufen Sie die Landelemente und fügen Sie ein Quadrat hinzu, wenn sie noch nicht die geplante Größe haben. Aber der lustige Teil ist das Abwägen der Chance, dass jedes benachbarte Element dasjenige sein wird. Einige Vorschläge, die Folgendes berücksichtigen könnten:

1. Entfernung zum nächsten "anderen" Land. Weiter ist es besser, weite ozeanische Räume zu erzeugen. Näher ist besser macht schmale Kanäle. Sie müssen sich entscheiden, ob Sie auch Bits zusammenführen lassen möchten.
2. Entfernung vom Samen. Näher ist besser bedeutet kompakte Landmassen, weiter ist besser bedeutet lang aufgereihte Teile
3. Anzahl der vorhandenen angrenzenden Landquadrate. Wenn Sie zugunsten vieler benachbarter Plätze gewichten, erhalten Sie eine glatte Küste. Wenn Sie nur wenige bevorzugen, erhalten Sie viele Einlässe und Halbinseln.
4. Vorhandensein von "Ressourcen" -Quadraten in der Nähe? Hängt von den Spielregeln ab, wann Sie ein Ressourcenquadrat generieren und ob Sie es einfach machen möchten.
5. Erlauben Sie Bits, sich den Polen zu nähern oder sich mit ihnen zu verbinden?
6. ??? Ich weiß nicht was noch

Fahren Sie fort, bis alle Landmassen die geplante Größe erreicht haben oder aus irgendeinem Grund nicht mehr wachsen können.

Beachten Sie, dass Sie durch Ändern des Parameters auf diese Gewichtungsfaktoren die Art der erzeugten Welt einstellen können. Dies ist eine Funktion, die mir bei einigen Civs gefallen hat.

Auf diese Weise müssen Sie die Geländegenerierung für jedes Bit separat durchführen.

Sie können einen Diamantquadratalgorithmus oder Perlinrauschen ausprobieren, um so etwas wie eine Höhenkarte zu erzeugen. Weisen Sie dann dem, was auf der Karte angezeigt wird, Bereichswerte zu. Wenn Ihre "Höhe" von 0 bis 100 geht, dann machen Sie 0 - 20 Wasser, 20 - 30 Strand, 30 - 80 Gras, 80 - 100 Berge. Ich denke, Notch hat im Minicraft etwas Ähnliches gemacht, aber ich bin kein Experte, ich bin nur in einer Diamant-Quadrat-Denkweise, nachdem ich es endlich zum Laufen gebracht habe.

Ich denke, Sie können hier den Ansatz der "dynamischen Programmierung" verwenden.

Lösen Sie zuerst kleine Probleme und kombinieren Sie Lösungen intelligent, um größere Probleme zu lösen.

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" ;)

Es wird sehr gut sein, sich einige "Graph Layout Algorithmen" anzusehen.

• Kraftbasierte Algorithmen
• Genetischer Algorithmus für das Graphlayout

Sie können diese an Ihren Zweck anpassen.

Ich hatte eine Idee für die Kartenerstellung, ähnlich der Antwort auf tektonische Platten. Es ging ungefähr so:

1. Durchlaufen Sie die Gitterquadrate und geben Sie jedem Quadrat ein "Land" -Quadrat, wenn rnd <= 0,292 (der tatsächliche Prozentsatz an trockenem Land auf dem Planeten Erde).
2. Migrieren Sie jedes Landstück um ein Quadrat in Richtung des nächsten größeren Nachbarn. Wenn die Nachbarn gleich weit entfernt sind, gehen Sie in Richtung des größeren Teils. Wenn die Chunks gleich groß sind, wählen Sie einen nach dem Zufallsprinzip aus.
3. Wenn sich zwei Landquadrate berühren, gruppieren Sie sie zu einem Stück und verschieben Sie von nun an alle Quadrate als eins.
4. Wiederholen Sie den Vorgang ab Schritt 2. Stoppen Sie, wenn alle Chunks verbunden sind.

Dies ähnelt der Funktionsweise der Schwerkraft in einem 3D-Raum. Es ist ziemlich kompliziert. Ein einfacherer Algorithmus für Ihre Anforderungen würde wie folgt funktionieren:

1. Legen Sie n Starter-Landquadrate an zufälligen x-, y-Positionen und akzeptablen Abständen voneinander ab. Dies sind Samen für Ihre Kontinente. (Verwenden Sie den Satz von Pythagoras, um sicherzustellen, dass die Samen einen Mindestabstand zwischen sich und allen anderen haben.)
2. Laichen Sie ein Landquadrat aus einem vorhandenen Landquadrat in zufälliger Richtung, wenn diese Richtung ein Ozeanquadrat ist.
3. Wiederholen Sie Schritt 2. Halten Sie an, wenn die Landquadrate 30% der gesamten Kartengröße ausfüllen.
4. Wenn die Kontinente nahe genug beieinander liegen, lassen Sie Landbrücken wie gewünscht fallen, um einen Effekt vom Typ Panama zu simulieren.
5. Lassen Sie kleinere, zufällige Inseln wie gewünscht fallen, um ein natürlicheres Aussehen zu erhalten.
6. Schneiden Sie für jedes zusätzliche "Insel" -Quadrat, das Sie hinzufügen, Binnenmeere und Seequadrate von den Kontinenten mit demselben Algorithmus in umgekehrter Reihenfolge aus. Dadurch wird der Landprozentsatz auf dem gewünschten Betrag gehalten.

Lassen Sie mich wissen, wie das funktioniert. Ich habe es selbst nie versucht.

PS. Ich sehe, das ist ähnlich wie das, was du versucht hast. Es sei denn, es werden vor Beginn alle Samen auf einmal eingerichtet, sodass die Kontinente weit genug voneinander entfernt sind und anhalten, wenn die Karte ausreichend gefüllt ist.

Ich habe das nicht wirklich versucht, aber es wurde von David Johnstones Antwort bezüglich tektonischer Platten inspiriert. Ich habe versucht, es selbst in meinem alten Civ-Projekt zu implementieren, und als es um den Umgang mit Kollisionen ging, hatte ich eine andere Idee. Anstatt Kacheln direkt zu generieren, besteht jeder Kontinent aus Knoten. Verteilen Sie die Masse auf jeden Knoten und generieren Sie dann eine Reihe von "Blob" -Kontinenten mithilfe eines 2D-Metaball-Ansatzes. Tektonik und Kontinentalverschiebung wären lächerlich einfach zu "fälschen", indem man einfach die Knoten bewegt. Abhängig davon, wie komplex Sie sein möchten, können Sie sogar Strömungen anwenden, um die Knotenbewegung zu handhaben und Gebirgszüge zu erzeugen, die überlappenden Plattengrenzen entsprechen. Wahrscheinlich würde ich dem Gameplay nicht so viel hinzufügen,

Eine gute Erklärung für Metabälle, wenn Sie noch nicht mit ihnen gearbeitet haben:

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

Hier ist, was ich denke, da ich im Begriff bin, so etwas zu implementieren, das ich für ein Spiel in der Entwicklung habe. ::

Die Welt ist in Regionen unterteilt. Abhängig von der Größe der Welt wird bestimmt, wie viele Regionen es gibt. In diesem Beispiel nehmen wir eine mittelgroße Welt mit 6 Regionen an. Jede Gitterzone unterteilt sich in 9 Gitterzonen. Diese Gitterzonen unterteilen sich in jeweils 9 Gitter. (Dies ist nicht für die Bewegung von Charakteren gedacht, sondern lediglich für die Kartenerstellung.) Die Gitter sind für Biomes, Gitterzonen für übergewölbte Landmerkmale (Kontinent gegen Ozean) und die Regionen für das Gesamtklima. Die Gitter zerfallen in Fliesen.

Die Regionen werden zufällig generiert und erhalten logische Klimasätze. Rasterzonen werden beispielsweise zufällig zugewiesen. Ozean oder Land. Gittern werden nach dem Zufallsprinzip Biome mit Modifikatoren zugewiesen, die auf ihren Gitterzonen und ihrem Klima basieren. Dies sind Wald, Wüste, Ebene, Gletscher, Sumpf oder Vulkan. Sobald alle diese Grundlagen zugewiesen sind, ist es Zeit, sie mithilfe einer zufälligen prozentualen Funktion zu mischen, die Kachelsätze ausfüllt. Beispielsweise; Wenn Sie ein Waldbiom haben, haben Sie neben einem Wüstenbiom einen Algorithmus, der die Wahrscheinlichkeit verringert, dass eine Kachel "waldig" ist, und erhöht, dass sie "wüstenartig" ist. Auf halbem Weg zwischen ihnen sehen Sie also eine Art gemischten Effekt, bei dem die beiden Biome kombiniert werden, um einen etwas glatten Übergang zwischen ihnen zu erzielen. Der Übergang von einer Gitterzone zur nächsten würde wahrscheinlich etwas mehr Arbeit erfordern, um logische Landmassenformationen sicherzustellen. Wie zum Beispiel ein Biom aus einer Gitterzone, das das Biom aus einer anderen berührt, anstatt einen einfachen Schaltprozentsatz basierend auf der Nähe zu haben. Zum Beispiel gibt es 50 Kacheln von der Mitte des Bioms bis zum Rand des Bioms, was bedeutet, dass es 50 von der Kante gibt, die es berührt, bis zur Mitte des nächsten Bioms. Das würde logischerweise eine 100% ige Veränderung von einem Biom zum nächsten hinterlassen. Wenn sich die Kacheln der Grenze der beiden Biome nähern, verringert sich der Prozentsatz auf etwa 60%. Ich denke, es wäre unklug, zu viel Wahrscheinlichkeit anzugeben, dass Biomassen weit von der Grenze entfernt sind, aber Sie möchten, dass die Grenze etwas gemischt wird. Für die Gitterzonen ist die prozentuale Änderung viel ausgeprägter. Anstatt dass der Prozentsatz auf ungefähr 60% sinkt, würde er nur auf ungefähr 80% fallen. Und dann müsste eine sekundäre Überprüfung durchgeführt werden, um sicherzustellen, dass sich keine zufällige Wasserfliese in der Mitte eines Landbioms neben dem Ozean befindet, ohne dass dies logisch ist. Verbinden Sie diese Wasserplatte entweder mit der Ozeanmasse, um einen Kanal zur Erklärung der Wasserplatte zu erstellen, oder entfernen Sie sie ganz. Land in einem wasserbasierten Biom lässt sich leichter mit Felsvorsprüngen und dergleichen erklären.

Oh, irgendwie dumm, sorry.

Ich würde fraktales Terrain nach einem Layout platzieren, von dem Sie wissen, dass es "funktioniert" (z. B. 2x2-Gitter, Diamant usw. mit etwas Jitter), aber mit einer Gaußschen Verteilungsdämpfung, die in Richtung der Ränder der Kontinentzentren abfällt. Stellen Sie den Wasserstand so ein, dass er größtenteils landet, bis Sie sich den Rändern nähern.