Dungeon Generation ohne Korridore und Raumabhängigkeiten

Ich mache ein Spiel mit einer prozedural erzeugten Welt, die zu Beginn des Spiels erstellt wurde und aus mehreren Bereichen besteht, die durch Gitter dargestellt werden (z. B. 8x8, 9x6, die Größen wären idealerweise beliebig). Diese Bereiche sollen über eine Abhängigkeitsliste miteinander verbunden sein.

Eine Verbindung besteht, wenn mindestens drei Bereiche dieses Rasters zwischen diesen beiden Bereichen freigelegt sind. In der mittleren Zelle dieses 3-Raum-Verbindungsbereichs befindet sich die Tür zwischen den Bereichen:

Ich habe versucht, einen Weg zu finden, sie zu verbinden, aber es wird immer komplexer, je mehr Bereiche Sie gleichzeitig berücksichtigen müssen.

Ich habe einige Papier-Prototypen ausprobiert, und obwohl dies visuell sehr einfach ist, habe ich keine guten mathematischen Ausdrücke gefunden, mit denen ich Räume mit der gleichen Effizienz per Code platzieren kann.

Hier ist ein "einfaches" Beispiel, mit dem ich gerade zu kämpfen habe:

• Bereich 'a' muss mit 'b' und 'c' verbunden werden
• Bereich 'b' muss mit 'a' und 'd' verbunden sein
• Bereich 'c' muss mit 'a' und 'd' verbunden sein
• Bereich 'd' muss mit 'b' und 'c' verbunden sein

Nehmen wir zur Vereinfachung an, wir platzieren die Räume in der Reihenfolge ihres Auftretens auf der Liste (ich habe andere ausprobiert). Ich betrachte dies als Ihren standardmäßigen prozeduralen Dungeon-Generierungsalgorithmus.

Wir platzieren 'a' irgendwo auf dem Brett, da es der erste Bereich ist. Als nächstes wählen wir zufällig eine Wand und da nichts mit dieser Wand verbunden ist, können wir dort 'b' platzieren:

Jetzt müssen wir 'c' platzieren, aber 'a' befindet sich bereits auf der Tafel und hat eine besetzte Wand. Deshalb entscheiden wir uns, sie an eine andere Wand zu hängen. Aber nicht jede Platzierung ist ausreichend, da "d" ansteht und auch mit "b" und "c" verbunden werden muss:

Ich habe eine mögliche Einschränkung ausprobiert, dass 2 Räume mit denselben Abhängigkeiten nicht an gegenüberliegenden Wänden liegen können, aber auch das garantiert keinen Erfolg:

Und in anderen Fällen, in denen die Bereiche unterschiedlich groß sind, kann es funktionieren, wenn Sie sich an gegenüberliegenden Wänden befinden:

Auch die Nichtberücksichtigung einer gebrauchten Wand ist eine fehlerhafte Annahme, da sie gültige Lösungen ausschließt:

Ich habe versucht, mich mit anderen Algorithmen zur Prozedurgenerierung oder ähnlichen zu befassen, z. B. mit Optimal Rectangle Packing- und Graph Layout-Algorithmen. In der Regel berücksichtigen diese Algorithmen jedoch nicht alle Einschränkungen dieses Problems und sind schwer miteinander zu mischen.

Ich habe über eine Reihe von Ansätzen nachgedacht, einschließlich Platzieren eines Bereichs und Zurückverfolgen, bis eine geeignete Platzierung gefunden ist, aber sie scheinen sehr abhängig von Versuch und Irrtum und in Bezug auf die Berechnung kostspielig zu sein. Aber angesichts der umfangreichen Nachforschungen zu den beiden zuletzt genannten Problemen könnte es die einzige / beste Lösung sein?

Ich wollte nur sehen, ob jemand in der Vergangenheit ähnliche Probleme hatte oder bereit ist, mir dabei zu helfen, dies herauszufinden, und mir ein paar Hinweise zu geben, wo ich mit dem Algorithmus beginnen sollte. Andernfalls muss ich mich mit der Lockerung der von mir festgelegten Einschränkungen befassen.

Das ist ein cooles Problem. Ich glaube, es kann durch Aktionsplanung im Raum der Platzierung gelöst werden.

Definieren Sie den Zustand der Welt wie folgt:

//State:
//    A list of room states.
//    Room state:
//      - Does room exist?
//      - Where is room's location?
//      - What is the room's size?

Definieren Sie eine Einschränkung als:

 // Constraint(<1>, <2>):
 //  - If room <1> and <2> exist, Room <1> is adjacent to Room <2>

Wo "benachbart" ist, wie Sie beschrieben haben (teilen Sie sich mindestens 3 Nachbarn)

EIN Einschränkung gilt als ungültig, wenn die beiden Räume nicht nebeneinander liegen und beide Räume existieren.

Definiere a Staat , der gültig ist, wenn:

// foreach Constraint:
//        The Constraint is "not invalidated".
// foreach Room:
//       The room does not intersect another room.

Definieren Sie eine Aktion als Platzierung eines Raums in einem aktuellen Status. Die Aktion ist gültig, wenn der aus der Aktion resultierende Status gültig ist. Aus diesem Grund können wir für jeden Status eine Liste mit Aktionen erstellen:

// Returns a list of valid actions from the current state
function List<Action> GetValidActions(State current, List<Constraint> constraints):
    List<Action> actions = new List<Action>();
    // For each non-existent room..
    foreach Room room in current.Rooms:
        if(!room.Exists)
            // Try to put it at every possible location
            foreach Position position in Dungeon:
                 State next = current.PlaceRoom(room, position)
                 // If the next state is valid, we add that action to the list.
                 if(next.IsValid(constraints))
                     actions.Add(new Action(room, position));

Nun bleibt Ihnen ein Diagramm , in dem Zustände Knoten und Aktionen Verknüpfungen sind. Ziel ist es, einen Staat zu finden, der ist sowohl gültig ist als auch alle Räume platziert wurden. Wir können eine gültige Platzierung finden, indem wir das Diagramm auf beliebige Weise durchsuchen, möglicherweise mit einer Tiefensuche. Die Suche sieht ungefähr so ​​aus:

// Given a start state (with all rooms set to *not exist*), and a set of
// constraints, finds a valid end state where all the constraints are met,
// using a depth-first search.
// Notice that this gives you the power to pre-define the starting conditions
// of the search, to for instance define some key areas of your dungeon by hand.
function State GetFinalState(State start, List<Constraint> constraints)
    Stack<State> stateStack = new Stack<State>();
    State current = start;
    stateStack.push(start);
    while not stateStack.IsEmpty():
        current = stateStack.pop();
        // Consider a new state to expand from.
        if not current.checked:
            current.checked = true;
            // If the state meets all the constraints, we found a solution!
            if(current.IsValid(constraints) and current.AllRoomsExist()):
                return current;

            // Otherwise, get all the valid actions
            List<Action> actions = GetValidActions(current, constraints);

            // Add the resulting state to the stack.
            foreach Action action in actions:
                State next = current.PlaceRoom(action.room, action.position);
                stateStack.push(next);

    // If the stack is completely empty, there is no solution!
    return NO_SOLUTION;

Nun hängt die Qualität des generierten Dungeons von der Reihenfolge ab, in der Räume und Aktionen berücksichtigt werden. Sie können interessante und unterschiedliche Ergebnisse erzielen, indem Sie die Aktionen, die Sie in jeder Phase ausführen, zufällig durchlaufen und dabei einen zufälligen Spaziergang durch das Diagramm mit den Statusaktionen machen. Die Sucheffizienz hängt stark davon ab, wie schnell Sie ungültige Status zurückweisen können. Es kann helfen gültige Status aus den Einschränkungen generieren , wenn Sie nach gültigen Aktionen suchen möchten.

Ihre Generationsprioritäten stehen in Konflikt. Bei der Erstellung von Ebenen sollte Ihr erstes Ziel ein Netz aus planaren (nicht überlappenden) verbundenen Punkten sein , unabhängig vom Maßstab. Erstellen Sie anschließend Räume aus den Punkten in diesem Web. Das Erstellen von Raumformen ist im Allgemeinen ein Fehler. Stellen Sie zuerst eine Verbindung her und prüfen Sie dann, welche Raumformulare darin untergebracht werden können.

Allgemeiner Algorithmus

1. Erstellen Sie mithilfe eines 2D-Arrays oder Bildes ein quantisiertes Bodenraster von ausreichender Größe, um Ihre Ebene zu unterstützen.

2. Verteile Punkte zufällig auf dieser leeren Fläche. Sie können für jede Kachel eine einfache Zufallsüberprüfung verwenden, um festzustellen, ob sie einen Punkt erhält, oder die Standard- / Gauß-Verteilung verwenden, um Punkte zu streuen. Weisen Sie jedem Punkt eine eindeutige Farbe / einen eindeutigen numerischen Wert zu. Dies sind IDs. (PS: Wenn Sie nach diesem Schritt das Gefühl haben, Ihren Speicherplatz vergrößern zu müssen, tun Sie dies auf jeden Fall.)

3. Für jeden derart erzeugten Punkt wird der Reihe nach inkrementell ein Begrenzungskreis oder ein Begrenzungsrechteck um einen einzelnen Schritt (typischerweise eine Rate von 0,5 bis 1,0 Zellen / Pixel pro Schritt) in xund vergrößerty . Sie können entweder alle Grenzen parallel anbauen, wobei alle mit der Größe Null im selben Schritt beginnen, oder Sie können sie zu unterschiedlichen Zeiten und mit unterschiedlichen Raten anbauen, wobei die Größe derer, die früher beginnen, voreingenommen ist (stellen Sie sich vor, die Sämlinge wachsen, wo einige spät anfangen). Mit "wachsen" meine ich, die neu inkrementierten Grenzen mit der Farbe / ID auszufüllen, die für den Startpunkt dieser Grenzen eindeutig ist. Eine Metapher dafür wäre, Markierungsstifte auf der Rückseite eines Blattes Papier zu halten und Tintenkleckse in verschiedenen Farben wachsen zu sehen, bis sie sich treffen.

4. Irgendwann kollidieren die Grenzen eines Punktes und eines anderen Punktes während des Wachstumsschritts. Dies ist der Punkt, an dem Sie aufhören sollten, die Grenzen für diese beiden Punkte zu erweitern - zumindest im in Schritt 3 beschriebenen einheitlichen Sinne.

5. Wenn Sie alle Grenzen der Punkte so weit wie möglich vergrößert und alle Wachstumsprozesse gestoppt haben, erhalten Sie eine Karte, die weitgehend, aber nicht vollständig gefüllt sein sollte. Vielleicht möchten Sie jetzt den leeren Raum, von dem ich annehme, dass er weiß ist, zusammenpacken, als ob Sie ihn auf einem Blatt Papier ausmalen.

Raumfüllung nach dem Prozess

Eine Vielzahl von Techniken kann verwendet werden, um die verbleibenden leeren / weißen Räume gemäß Schritt 5 auszufüllen:

• Lassen Sie einen einzelnen benachbarten, bereits farbigen Bereich den Raum beanspruchen, indem Sie ihn mit einer Flut füllen, damit sich alles verbindet.
• Überfluten Sie mit neuen, noch nicht verwendeten Farben / Zahlen / IDs, so dass sie völlig neue Bereiche bilden.
• Round Robin Annäherung derart, dass jeder bereits gefüllte Nachbarbereich ein wenig in den leeren Raum "hineinwächst". Denken Sie an Tiere, die an einer Wasserstelle trinken: Sie alle bekommen etwas Wasser.
• Füllen Sie den leeren Raum nicht vollständig aus, sondern kreuzen Sie ihn, um vorhandene Bereiche mit geraden Passagen zu verbinden.

Störung

Als letzten Schritt, damit die Dinge organischer aussehen, können Sie Randstörungen in unterschiedlichem Ausmaß an den Randzellen von Bereichen vornehmen. Achten Sie nur darauf, wichtige Bewegungsrouten nicht zu blockieren.

Theorie, um des Interesses willen

Dies ähnelt dem Ansatz in Voronoi-Diagrammen / Delaunay-Triangulation , mit der Ausnahme, dass Sie oben keine expliziten Kanten erstellen - stattdessen hört das Wachstum auf, wenn Grenzbereiche kollidieren. Sie werden feststellen, dass Voronoi-Diagramme den Raum füllen; Dies liegt daran, dass sie ihr Wachstum nicht nur durch Berühren, sondern durch einen nominalen Grad der Überlappung einstellen. Du könntest es ähnlich versuchen.