Was ist eine gute Strategie zum Erstellen eines gerichteten Graphen für eine Spielkarte (in Python)?

Question

Ich entwickle eine prozedural generierte Spielwelt in Python. Die Struktur der Welt wird ähnlich dem MUD/MUSH-Paradigma von Räumen und Ausgängen sein, die als gerichteter Graph angeordnet sind (Räume sind Knoten, Ausgänge sind Kanten). (Beachten Sie, dass dies nicht unbedingt ein azyklischer Graph, obwohl ich bin bereit, azyklische Lösungen zu berücksichtigen.)

Zur Welterzeugungsalgorithmus, Zimmer verschiedener Art werden von jedem „Tags“ Attribut Zimmer unterscheiden (a Reihe von Zeichenfolgen). Sobald sie instanziiert wurden, können Räume abgefragt und nach Tags ausgewählt werden (Einzel-Tag, Tag-Schnittpunkt, Tag-Union, bester Kandidat).

Ich werde bestimmte Arten von Räumen mit einem verklärten System von Vorlagenobjekten und Fabrikmethoden erstellen - ich denke nicht, dass die Details hier wichtig sind, da sich die aktuelle Implementierung wahrscheinlich ändern wird, um der gewählten Strategie zu entsprechen. (Zum Beispiel wäre es möglich, Tags und Tag-Anfragen an die Raumvorlage System hinzuzufügen.)

Ein Beispiel ich Zimmer dieser Art haben:

side_street, main_street, plaza, bar, hotel, restaurant, shop, office

Schließlich die Frage: Was ist Eine gute Strategie, um diese Räume zu instanziieren und zu arrangieren, um ein Diagramm zu erstellen, das bestimmten Regeln entspricht?

Einige Regeln könnten enthalten: eine Plaza pro 10.000 Einwohner; main_street verbindet mit plaza; side_street verbindet mit main_street oder side_street; hotel bevorzugt oder plaza Verbindungen, und erhält entsprechend weitere Tags; usw.

Bonuspunkte, wenn eine vorgeschlagene Strategie eine datengesteuerte Implementierung ermöglichen würde.

Answer 1

Zuerst brauchen Sie ein Gefühl von Standort. Ihre verschiedenen Objekte belegen eine gewisse Menge an Koordinatenraum.

Sie müssen entscheiden, wie regelmäßig diese verschiedenen Dinge sind. Im trivialen Fall können Sie sie als einfache Rechtecke (oder rechteckige Volumenkörper) in Ihren Koordinatenraum einfügen, um die Planung von Orten zu vereinfachen.

Wenn die Dinge unregelmäßig und dicht gepackt sind, ist das Leben etwas komplexer.

Definieren Sie eine Karte, die Standorte enthält. Jeder Ort hat eine Spannweite von Koordinaten; Wenn Sie mit einfachen Rechtecken arbeiten, kann jeder Ort ein (links, oben, rechts, unten) Tupel haben.

Ihre Karte wird Methoden benötigen, um zu bestimmen, die in einem bestimmten Raum aufhält, und was mit dem benachbarten Raum ist usw.

Sie können dann diese Einheit Test mit einem festen Satz von Orten, die Sie gearbeitet haben, dass können alle in die Karte eingefügt werden und einige grundlegende Sicherheitsüberprüfungen für nicht kollidierende, benachbarte und dergleichen bestehen.

---

Zweitens benötigen Sie eine Art "Labyrinth-Generator". Ein einfach verbundenes Labyrinth wird leicht als eine Baumstruktur erzeugt, die in den gegebenen Raum gefaltet ist.

Das Labyrinth/Baum hat einen "Wurzel" Knoten, der das Zentrum des Labyrinths sein wird. Nicht unbedingt das physikalische Zentrum Ihres Raumes, aber der Wurzelknoten wird die Mitte der Labyrinthstruktur sein.

Im Idealfall enthält ein Zweig von diesem Knoten einen "Eingang" zum gesamten Raum.

Der andere Zweig von diesem Knoten enthält einen "Ausgang" vom gesamten Raum.

Jemand kann vom Eingang zum Ausgang wandern und viele "Sackgassen" auf dem Weg besuchen.

Wählen Sie eine Art von Speicherplatz für den Stammknoten aus. Legen Sie es in Ihren Kartenbereich.

haben diese erhalten 1 - n Eingänge, von denen jeweils ein Teilbaum mit einem Wurzelknoten sind 1 und - n Eingänge. Es ist dieses Multiple-Entry-Geschäft, das einen Baum zu dieser Struktur macht. Auch ein richtiger Baum ist immer gut verbunden, da Sie nie isolierte Abschnitte haben, die nicht erreicht werden können.

Sie werden - rekursiv - vom Stammknoten auffächern, Orte auswählen und sie in den verfügbaren Platz ablegen.

Unit-Test, um sicherzustellen, dass es Platz ziemlich gut füllt.

---

Der Rest Ihrer Anforderungen sind Feinabstimmung auf die Art, wie der Labyrinth-Generator Standorte wählt.

Am einfachsten ist es, eine Tabelle mit Gewichten und zufälligen Auswahlmöglichkeiten zu haben. Wählen Sie eine Zufallszahl, vergleichen Sie sie mit den Gewichten, um festzustellen, welche Art von Standort identifiziert wird.

---

Ihre Definition von Raum kann 2D oder 3D sein - beide sind ziemlich rational. Berücksichtigen Sie beim Bonuskredit, wie Sie einen 2D-Raum implementieren, der mit Sechsecken anstelle von Quadraten verkleidet ist.

Diese "Geometrie" kann ein Strategie Plug-in für die verschiedenen Algorithmen sein. Wenn Sie quadratisches 2D durch hexagonales 2D ersetzen können, haben Sie OO Design gut gemacht.

Answer 2

Schauen Sie sich die Diskussionen auf The MUD Connector an - es gibt einige großartige Diskussionen über das Layout und die Generierung der Welt und verschiedene Arten von Koordinaten/Navigationssystemen im Forum "Advanced Coding and Design" (oder ähnlich).