Was ist eine gute Methode, um zufällig Kanten zwischen Diagrammknoten zu generieren?

10

Ich mache einen zufälligen Kartengenerator für ein 4X-Weltraumspiel.

Jeder Knoten im Spiel wird an einer zufälligen (x, y) Koordinate in einem 2D-Gitter platziert. Ein Knoten kann eine oder mehrere bidirektionale Kanten zu einem anderen Knoten haben (der Wurmlöcher darstellt). Alle Knoten müssen mindestens ein Wurmloch haben und alle Knoten müssen zum selben Diagramm gehören.

Idealerweise sollte ein Wurmloch eine maximale Länge nicht überschreiten, und Wurmlöcher sollten sich nach Möglichkeit nicht kreuzen.

Meine naive Implementierung besteht darin, alle Knoten zu durchlaufen und die Knotenverbindung zu den nächsten 3 Knoten herzustellen. Am Ende habe ich jedoch zahlreiche Untergraphen. Was ist eine gute Methode, um die Kanten für die Knoten zu generieren?

Extrakun
quelle
Wie sind die Knoten über die Galaxie verstreut? Ich meine, darf ich annehmen, dass es für jeden Punkt (X, Y) in der Galaxie einen Knoten gibt? oder zumindest für die meisten von ihnen oder nicht?
Ali1S232
Nicht alle Koordinaten haben einen Knoten. Über 40% würde ich sagen.
Extrakun

Antworten:

9

Hier ist eine gute Antwort auf eine ähnliche Frage.

Erstellen Sie zunächst ein verbundenes Diagramm, möglicherweise unter Verwendung eines minimalen Spannbaums wie im obigen Link. Er schlägt vor, zufällige Kantengewichte zu verwenden, um den "minimalen" Baum zufällig zu machen. Dann können Sie zufällig weitere Kanten hinzufügen, sodass dies nicht nur der Mindestbaum ist. Wie genau Sie die zufälligen Kanten hinzufügen, hängt davon ab, welche Art von Diagramm Sie möchten.


Wenn das Problem nur darin besteht, sicherzustellen, dass alle Knoten zum selben Diagramm gehören, können Sie Ihre aktuelle Methode zur Zufallsgenerierung (oder eine andere) verwenden und den Prim-Algorithmus darüber anwenden. Wenn Sie nur minimale Änderungen am Diagramm vornehmen möchten, um sicherzustellen, dass alle Untergraphen verbunden sind, können Sie die Kantenkosten für bereits vorhandene Kanten auf 0 setzen.

Philip
quelle
+1, da es eine sehr gute Antwort ist, aber ich mag diese Art von Generation einfach nicht, also werde ich in den nächsten Tagen über einen besseren Algorithmus nachdenken!
Ali1S232
Ja, es gibt keine 'richtige' Antwort darauf. Ich bin gespannt, was andere sich einfallen lassen.
Philip
Offtopic, aber ich wollte auch auf meine Antwort verlinken! : p
r2d2rigo
Auf diese Weise bekomme ich Punkte dafür, ha!
Philip
7

Die Hauptbeschränkungen Ihres Problems sind zweierlei: Erstellen eines 1-verbundenen Diagramms; und Erstellen mit proximalen Verbindungen. Die Antwort von Philip ist zwar etwas wertvoll, spricht jedoch nicht alle Einschränkungen Ihres Problems an

Idealerweise sollte ein Wurmloch eine maximale Länge nicht überschreiten, und Wurmlöcher sollten sich nach Möglichkeit nicht kreuzen.

Wenn Sie Punkte in einer Cloud naiv verbinden, laufen Sie Gefahr (und zwar mit einem hohen Risiko), dass diese Bedingungen nicht erfüllt werden.

Sie sehen, das Problem liegt weniger in der Konnektivität als vielmehr in der Nähe dieser Verbindungen. Es ist trivial, jeden Knoten in einem Diagramm mit jedem anderen Knoten zu verbinden, aber es ist etwas schwieriger, nur die Knoten zu verbinden, die am nächsten sind, während die 1-Verbindung des gesamten Diagramms beibehalten wird.

Dies ist, was eine Delaunay-Triangulation in n Dimensionen erzeugt. Der erste Grund für die Verwendung der Delaunay-Triangulation besteht darin, dass beide implizit erfüllt werden. Der zweite Grund ist, dass es viel einfacher ist, von einem solchen Diagramm aus rückwärts zu arbeiten (Kanten und Scheitelpunkte zu subtrahieren, die Sie nicht möchten), als zu versuchen, es auf andere Weise zu erstellen.

  1. Erstellen Sie nach dem Zufallsprinzip Ihre Vollpunktwolke.
  2. Delaunay-Triangulieren Sie es.
  3. Konstruieren Sie das Diagramm (Verbindung von Punkten). In diesem Fall können Sie entweder zuerst das gesamte Diagramm (jeden Stern) generieren und dann das Diagramm als Minderjährige ableiten, die Ihre mit dem Wurmloch verbundenen Regionen darstellen, wenn Sie Schritt 4 ausführen. Alternativ können Sie auch umgekehrt arbeiten und nur die mit dem Wurmloch verbundenen Regionen generieren zuerst als Supergraph-Knoten und dann in einer zweiten Phase einzelne Sterne innerhalb der Begrenzungsvolumina dieser Regionen erzeugen (für diese würde ich den Graphen dual der Delaunay-Triangulation - das Voronoi-Diagramm in 3 Dimensionen) als Untergraphen ableiten. Jetzt haben Sie proximal verbundene Sternhaufen, und alle Haufen sind durch seltenere Wurmlöcher verbunden: Ihre Topologie und Topographie sind für den Spieler sinnvoll.
  4. Wenden Sie intelligente Methoden an, um die Super- und Subgraphen zu formen, je nachdem, wie Sie sie in Schritt 3 behandelt haben.

Es ist wichtig zu sehen, dass dies ein hierarchischer Prozess ist. Die erste Ebene befasst sich mit der Wurmlochkonnektivität. Die zweite befasst sich mit Entfernungen, die vermutlich mit einem Standard-Schiffsantrieb zurückgelegt werden können. Sie können Delaunay auf einer oder beiden Ebenen anwenden, um Ihre Einschränkungen zu erfüllen.

Wenn Sie dies rein topologisch tun, erhalten Sie Wurmlöcher, die keinen Sinn ergeben, da sie trotz einer hohen Dichte an Sternen dazwischen eine Seite der Galaxie mit einer anderen verbinden können (und möglicherweise sogar auf den direkten Weg des Wurmlochs fallen). Topologie ist keine Topographie; Letzteres ist eine Überlegung, die über Ersteres hinausgeht. Sie beschäftigen sich mit der Nähe und damit der Topographie.

Ingenieur
quelle
Eine Delaunay-Triangulation ist eine gute Idee, erzeugt jedoch keine zufälligen Kanten. Sie könnten Kanten zufällig von den durch die Delaunay-Triangulation erzeugten Kanten entfernen, aber dann riskieren Sie, wieder separate Diagramme zu erhalten ...
bummzack
@Bummzack "Es entstehen keine zufälligen Kanten". Schon mal was von Graph Minors gehört? Sobald Sie die schwierigeren Einschränkungen mit Delaunay gelöst haben, ist es trivial, das Diagramm nach Belieben zu ergänzen oder zu entfernen.
Ingenieur
@Bummzack, ich habe es gerade nochmal aktualisiert - danke für das Feedback.
Ingenieur