Zufällige Kartengenerierung - Strategien zum Streuen / Clustering von zufälligen Knoten

Ich mache ein einfaches 4X-Strategiespiel im Weltraum, bei dem jeder Knoten ein Sonderziel ist (ein Planet, ein Asteroid usw.).

Um zufällig eine Karte zu generieren, würde ich die folgenden Schritte ausführen

1. Entscheiden Sie, wie viele Arten von Knoten die Karte haben soll (z. B. 5 erdähnliche Planeten, 10 unfruchtbare Planeten usw.).

2. Platzieren Sie jeden Knotentyp auf der Karte.

Für Schritt 2 möchte ich eine gleichmäßige Verteilung jedes Knotentyps haben. Zum Beispiel würde ich damit beginnen, alle erdähnlichen Planeten zu platzieren. Wenn ich einfach einen Rand (map.width, map.height) mache, um die Position zu bestimmen, kann es sein, dass sich alle erdähnlichen Planeten zusammenballen, was dem Spieler, der in diesem Bereich startet, einen Vorteil verschafft.

Gibt es Methoden, wie die Verwendung verschiedener Graphfunktionen oder Rauschfunktionen, die eine Folge von (x, y) -Koordinaten erzeugen könnten, die voneinander verteilt sind? Gibt es auch Möglichkeiten, nahe beieinander liegende Koordinaten zu generieren?

Das Problem, mit dem Sie konfrontiert sind, ist, dass die zufällige Auswahl nicht diskriminiert, und das kann bedeuten, dass sie nicht optimal zu dem passt, was Sie tun müssen. Es gibt jedoch mindestens einen einfachen Weg, dies zu umgehen:

1. Teilen Sie Ihren Raum in Sektoren auf (z. B. wenn Sie eine Fläche von 100 x 100 haben und 100 dieser Sonnensysteme erzeugen müssen, teilen Sie Ihre Fläche in ein 10 x 10-Raster von Sektoren auf).

2. Durchlaufen Sie jeden Sektor und wiederholen Sie Schritt 3 (der wiederum Schritt 4 mehrmals wiederholt).

3. Bestimmen Sie zufällig die Anzahl der Planeten für das aktuelle Sonnensystem (z. B. für einen Bereich von 3 bis 7 Planeten, erfassen Sie einfach eine Zufallszahl zwischen 0 und 4 und addieren Sie 3) im aktuellen Sektor (wenn Sie mehr als eine Sonne haben System in einem Sektor, hier würden Sie eine weitere Schleife einrichten)

4. Weisen Sie Ihre Planeten zufällig dem aktuellen Sonnensystem zu, das von Ihrer Schleife identifiziert wird (Sie können auch Zufallszahlen verwenden, um die Mindestabstände zwischen den Planeten zu erhöhen). Hier würden Sie die Arten von Planeten bestimmen, die auch zufällig mit einer Vielzahl von Gewichten oder einer von Ihnen bevorzugten Methode bestimmt werden könnten

Möglicherweise möchten Sie auch einen Bereich außerhalb der Grenzen um den Rand jedes Sektors definieren, um zu verhindern, dass Planeten benachbarter Sektoren direkten Kontakt miteinander haben (nur für den Fall, dass sie tatsächlich zufällig nebeneinander angeordnet sind), oder. ..

Eine andere Lösung könnte darin bestehen, den Standort jedes Sonnensystems und / oder jedes Planeten zu bestimmen, indem Sie einfach eine schnelle Näherungsprüfung für benachbarte Sektoren durchführen und entsprechend anpassen (z. B. sich um einen Mindestabstand plus einen zufälligen Abstand vom Rand entfernen ).

Der beste Weg, um eine gleichmäßige Verteilung sicherzustellen, besteht darin, jeden Knoten als eine Art physikalisches Partikel zu behandeln. Führen Sie zunächst eine zufällige Verteilung über eine kontinuierliche (Gleitkomma-) xy-Ebene durch. Wenn Sie Abstoßungskräfte zwischen jedem einzelnen Paar einzelner Partikel in der Ebene anwenden, werden Sie feststellen, dass sie sich langsam ausbreiten. In gewisser Weise ist es wie eine Kollisionsauflösung, nur gibt es keinen nennenswerten Kontakt. Es ist dann eine einfache Sache, diese Ebene wieder in ein ganzzahlig indiziertes Gitter umzuwandeln ("zu rastern"). Sie können dies zunächst einfach von einem ganzzahlig indizierten Raster aus tun, aber es ist möglicherweise etwas schwieriger, die Dinge "schön" zu machen - dies hängt davon ab, wie hoch die Auflösung Ihres Rasters ist ... je höher, desto besser , in diesem Fall.

Offensichtlich möchten Sie möglicherweise auch Kräfte von den Rändern der quadratischen Ebene aus aufbringen, oder Sie finden viele Partikel, die sich "an den Ufern abwaschen". Alternativ können Sie ein Feld erstellen, das viel größer ist als Sie benötigen, und dann einen Schnappschuss eines kleinen Bereichs davon erstellen - dies vermeidet das oben genannte Problem.

Wenn Sie das Gegenteil sicherstellen wollen, das heißt , dass Clustering nicht auftritt, dann schauen Sie in „Standard“ oder „Gaußsche“ Verteilung. Aus diesem Grund sehen zufällig erzeugte Sternenfelder oft falsch aus. Sie verwenden eher eine reine Zufallsverteilung als ein naturalistischeres Verteilungsmodell.

Sie können einen einfachen Poisson-Disk-Verteilungsalgorithmus verwenden , um eine "Blue Noise" -Verteilung zu erhalten. Dies führt zu Punkten in der Ebene, die ungefähr gleich weit voneinander entfernt sind. Dies funktioniert nicht nur in Ihrem 2D-Beispiel, sondern auch in 3D und auch in nichteuklidischen Räumen, aber die Berechnungen können schnell unhandlich werden.

Die Grundidee dieser Algorithmen besteht darin, dass Sie mit einem ersten "Startpunkt" beginnen und dann nach außen arbeiten und zufällige oder pseudozufällige Punkte im Ringraum zwischen den maximalen und minimalen Abständen hinzufügen, die Sie ab dem Punkt haben möchten, und eliminieren diejenigen, die zu nahe beieinander liegen. Ihr Algorithmus arbeitet dann so nach außen, bis entweder die Anzahl der benötigten Punkte hinzugefügt wird (wodurch Sie eine ungefähr kreisförmige Punktwolke erhalten) oder der verfügbare Platz gefüllt ist.

Ein schneller und eleganter alternativer Algorithmus zur Erzeugung eines solchen 2D-Rauschens sowie eine kurze Diskussion seiner Eigenschaften finden sich in " Eine räumliche Datenstruktur für die schnelle Erzeugung von Poisson-Disk-Proben " von Daniel Dunbar und Greg Humphreys von der Universität von Virginia.