Reduzieren Sie die Anzahl der Kanten eines Diagramms und halten Sie es verbunden

10

Ich entwerfe ein Spiel mit zufällig generierten Dungeons. Ich möchte dies als ein verbundenes, ungerichtetes Diagramm betrachten, in dem Knoten Räume und Kanten Türen oder Korridore sind. Dann wähle ich einen "Seiten" -Knoten als Dungeoneingang, berechne den Abstand zwischen diesem Eingang und allen anderen Knoten und entscheide, dass einer der am weitesten entfernten Knoten das "Ziel" des Dungeons ist (der Ort des Schatzes, des Chefs, Prinzessin usw.).

Ich habe zwei Möglichkeiten gesehen, um die endgültige Dungeontopographie zu erstellen:

  • Generieren Sie zuerst ein zufälliges Diagramm und versuchen Sie dann, die 2D-Welt mit Räumen an zufälligen Orten zu füllen, wobei Sie die Randverbindungen berücksichtigen. Ich dachte, das wäre manchmal schwierig, weil die Raumgeneration "verschlossen" werden könnte, um Räume an unmöglichen Orten unterzubringen.
  • Generieren Sie die ersten Räume, platzieren Sie sie zufällig dort, wo sie passen, und ordnen Sie das Ergebnis dann Knoten und Kanten zu. Ich habe beschlossen, dies zu versuchen.

Meine Idee besteht aus:

  • Generiere zuerst einen großen Raum, der den gesamten Dungeon enthalten würde.
  • Stellen Sie an einer zufälligen Stelle eine Wand in den großen Raum und teilen Sie den großen Raum in zwei kleinere Räume mit unterschiedlichem Bereich.
  • Dann teile ich jeden Raum weiter in 2, bis sie zu klein sind oder die Gesamtzahl der Räume ein Maximum erreicht (oder eine andere Bedingung). Jeder neue Raum ist ein Knoten.
  • Sobald ich fertig bin, überprüfe ich jeden Raum und finde alle angrenzenden anderen Räume, wobei ich die 2 Knoten als durch eine Kante verbunden markiere.

Auf diese Weise stelle ich sicher, dass alle Räume einen möglichen Standort in der 2D-Welt haben und von einem verbundenen Diagramm korrekt abgebildet werden.

Mein Problem ist, dass es zu viele Türen und Korridore gibt, die die Räume verbinden.

Ich möchte also einen Algorithmus, der die Anzahl der Kanten eines verbundenen ungerichteten Graphen reduziert , ihn aber am Ende in Verbindung hält (alle Knoten bleiben erreichbar).

algorithm procedural-generation random topography graphs Splo
quelle
Ihre Idee ist im Grunde ein binärer Suchbaum, wenn Sie wissen wollen. Ich benutzte es; es macht ziemlich schöne Dungeons und ist einfach. :)
Die kommunistische Ente
2
Zu Ihrer Information: Ein vollständiges Diagramm hat Kanten zwischen allen Scheitelpunktpaaren. Wenn also doppelte Kanten nicht zulässig sind, können Sie keine Kanten entfernen und haben dennoch ein vollständiges Diagramm. Der richtige Begriff ist ein zusammenhängender Graph .
Michael Madsen
Binärer Suchbaum, verbundener Graph, rechts. Ich bin so schlecht mit herkömmlichen Namen.
Splo

Antworten:

13

Verwenden Sie den Prim-Algorithmus , um den minimalen Spannbaum für Ihr Diagramm zu erhalten (fügen Sie zufällige Gewichte hinzu oder fügen Sie die höheren Gewichte in der Nähe des Eingangs hinzu oder führen Sie einen Algorithmus Ihrer Wahl aus) und fügen Sie einige Türen / Kanten nach dem Zufallsprinzip wieder hinzu. Auf diese Weise haben Sie alle Räume miteinander verbunden und einige zusätzliche redundante Pfade.

r2d2rigo
quelle
1
Oh, richtig, der minimale Spannbaum natürlich! Gute Idee, danke.
Splo
1

Sie können auch den Kruskal-Algorithmus ausprobieren

Gastón
quelle
0

Einige der Dungeon-Generatoren auf dieser Liste von Inkwell Ideas sind Open Source oder bieten Dokumentation zu ihren Algorithmen. Google wird Ihnen auch durch die Suche nach "[Programmiersprache Name] Dungeon Generator" viel bieten. Leider kann mein Favorit mit keiner dieser Methoden gefunden werden, obwohl er der am besten dokumentierte ist, den ich je gesehen habe, und ich kann mich nicht an seinen Namen erinnern, da ich ihn kürzlich durch einen Festplattenabsturz verloren habe. Ich werde diese Antwort aktualisieren, nachdem ich die Wiederherstellung auf diesem Laufwerk durchgeführt habe.

Sparr
quelle