Prozedurale Dungeon-Generierung: Gibt es einen einfachen Algorithmus, um sicherzustellen, dass alle diese Räume über minimale Korridore miteinander verbunden werden?

Ist es möglich, eine bienenstockartige Struktur zu erhalten, die alle Räume verbindet, ohne zu viele Korridore zu haben? (Zu viele sind 3-4 + Korridore, die aus einem einzigen Raum kommen)

Unten sehen Sie die Ausgabe, wie meine Räume aussehen, im Grunde sind sie zufällig platziert.

Was ich hoffe, in Bezug auf den Korridor zu bekommen.

Der einfachste Weg, den ich mir vorstellen kann, besteht darin, sicherzustellen, dass alle Räume durch mindestens einen Korridor verbunden sind:

1. Beginnen Sie mit dem letzten oder ersten Raum.
2. Schnappen Sie sich einen zufälligen Raum in 1 Entfernung, der noch nicht mit einem Raum verbunden ist (alle Räume werden getrennt, sodass Sie dies auf Ihrem Weg verfolgen können).
3. Wenn es keinen solchen Raum gibt, gehen Sie zu Abstand +1. Wenn es in Ordnung ist, über / unter einen anderen Raum zu tunneln, ist dies einfacher, vorausgesetzt, Sie möchten keine Verbindungskorridore.
4. Arbeiten Sie sich pseudozufällig durch, bis alle Räume verbunden sind.

Jetzt wissen wir, dass Sie zu allen Räumen gelangen können. Wenn Sie jedoch mehr als dieses streng lineare Labyrinth wünschen, können Sie einfach durch Ihre Räume gehen und nach dem Zufallsprinzip einen neuen Pfad zum Verbinden von Räumen erstellen, bis zu einer Grenze pro Raum von 2-3 oder bis ein bestimmter Prozentsatz der Räume die maximale Anzahl von Verbindungen erreicht - usw.

Als letzten Schritt können Sie Regeln hinzufügen, die Ihre Ergebnisse an verschiedene Situationen anpassen. Sie können beispielsweise feststellen, dass jeder Raum mit nur einem Korridor per Definition eine Sackgasse ist. Sie könnten mehr Sackgassen machen oder sie alle beseitigen, indem Sie sicherstellen, dass alles mindestens zwei Verbindungen hat. Sie könnten Sackgassen dazu bringen, einen Geheimgang zu haben. Sie könnten sicherstellen, dass ein Chefraum eine Sackgasse ist. Sie können sicherstellen, dass Ihr Startraum eine Sackgasse ist, aber dann sicherstellen, dass der zweite Raum mindestens X Verbindungen hat. Ad infinitum.

Jede Annahme und Regel kann das Aussehen Ihrer Level radikal verändern, aber das macht Spaß! Dies sollte zumindest dazu führen, dass Sie Bienenstock- / Höhlen-ähnliche Räume beginnen.

Bauen Sie einfach Ihre bereits verbundenen Räume. Beginnen Sie mit einem Raum und bauen Sie dann 1-3 Korridore zu anderen Räumen. Dann wiederholen, bis Sie genügend Räume hinzugefügt haben.

Da es sich bei diesen Räumen um Graph-Eckpunkte handelt, die in eine 2D-Ebene eingebettet sind, könnte dies theoretisch durch Lösen des Problems des Handlungsreisenden erfolgen (was mit nur wenigen Räumen in Ordnung wäre). Offensichtlich eine einfache Heuristik wäre in Ordnung und würde eine angemessene Skalierbarkeit ermöglichen.

Sie berechnen die Kanten (Korridorlängen) zwischen allen Räumen. Sie sortieren sie nach Länge. Sie fügen den kürzesten Korridor hinzu, es sei denn, er erzeugt einen Zyklus oder erhöht den Grad des Scheitelpunkts (Raums) über Ihren gewünschten Maximalwert (3-4) (Wiederholen). Um nach Zyklen zu suchen, können Sie UnionFind anwenden oder ein schnelles BFS für kleine Daten durchführen.