Rundräume verbinden

7

Mein Roguelike erzeugt eine Reihe von runden Räumen. Ich mag die aktuellen Ergebnisse, die ungefähr so ​​aussehen:

Geben Sie hier die Bildbeschreibung ein

Es wird erzeugt, indem zufällige Kreise in einem gefüllten Raum herausgeschnitten werden.

Ich habe ein Hauptproblem damit: Mehrere Kreise sind völlig unverbunden. Ich kann nicht genau herausfinden, welchen Algorithmus ich verwenden soll, um sie zu verbinden.

Ich habe versucht, "für jeden Kreis den nächsten Kreis zu finden und in seine Mitte zu tunneln (horizontal und dann vertikal)", aber ich bekomme stattdessen etwas Schreckliches (dieselbe Karte wie oben):

Geben Sie hier die Bildbeschreibung ein

Was die richtige Passform zu sein scheint, ist so etwas wie "Finden Sie für jeden geschlossenen Raum den nächsten leeren Raum und tunneln Sie ihn an." Das scheint jedoch komplex zu sein (berechnen Sie für jeden kreisförmigen geschlossenen Raum die Entfernung zu jedem anderen Raum) und wird wahrscheinlich langsam sein (läuft auch auf Ruby)

Gibt es eine einfache Lösung für dieses Problem?

Asche999
quelle
Ist es das was du willst? Damit jeder Raum mit dem nächstgelegenen Raum im selben Bereich verbunden ist?
AturSams
Warum nicht entlang einer beliebigen Linie tunneln, nicht nur horizontaler / vertikaler Linien?
user1095108
@ArthurWulfWhite Ich möchte, dass die gesamte Karte verbunden wird. Der nächstgelegene Raum ist etwas kompliziert (ich verfolge noch keine Begrenzungskacheln).
Asche999
1
Randnotiz: Wechseln Sie zu Linux, wo es schöne Terminals gibt und verwenden Sie Farbe! Das ist neben all den Extras, die ein Programmierer in einer Unix-basierten Umgebung erwartet!
Shahbaz
@ Shahbaz Ich benutze hauptsächlich Linux (zumindest für Spieleentwickler). Ich werde meine Screenshots mit den (imo, schöneren) Linux-Versionen aktualisieren, sobald ich die Integration der VirtualBox-Zwischenablage herausgefunden habe ...
ashes999

Antworten:

6

In Ordung. Für dieses Problem gibt es eine recht rechnerisch kostengünstige Lösung. Verwenden Sie zuerst Union Find , um Räume zu verfolgen, die noch nicht verbunden sind.

Jedes Quadrat gehört jetzt zu einem Satz mit einem eindeutigen Index.

  1. Wenn Sie einen kreisförmigen Raum erstellen, führen Sie alle darin enthaltenen Quadrate zu demselben Satz zusammen.
  2. Wenn Sie einen Raum erstellen, der sich mit einem anderen Raum überschneidet, vereinen Sie die beiden Sätze zu einem.
  3. Sobald Sie fertig sind, sollten Sie eine Reihe von Leerzeichen haben. Jeder verbundene Bereich hat eine eigene eindeutige ID in der Union Find-Datenstruktur.
  4. Wählen Sie den größten offenen Raum aus (Sie müssen die Größe der Sätze in Union Find verfolgen).
  5. Behandeln Sie die Karte als eine Grafik von Knoten, bei denen jeder Knoten durch eine Kante links, rechts, oben und unten mit ihm verbunden ist. Wenn eine Kante zu einer Wand führt, kostet sie (1), andernfalls kostet sie epsilon0,0001. Alle anderen Räume (leere Räume) werden mit einer freien Kante mit einem virtuellen Zielknoten verbunden.
  6. Verwenden Sie Dijkstra, um den kürzesten Weg vom aktuellen Raum zum Ziel zu finden und diesen Weg freizumachen, indem Sie die Wände in diesem Weg entfernen.
  7. Führen Sie nun die Sets (die verbundenen Räume) zusammen und setzen Sie diesen Vorgang mit Dijkstra fort.
AturSams
quelle
Möglicherweise möchten Sie einige Fragen dazu stellen, wenn Sie keinen CS-Hintergrund haben, aber im Allgemeinen nach dem kürzesten Weg zwischen Räumen suchen (die nicht verbunden sind [speziell durch Wände schauen]) und wenn Sie einen Weg gefunden haben, Räumen Sie es auf (entfernen Sie Wände) und identifizieren Sie sie (die beiden neuen verbundenen Räume) als dasselbe Set. Verbinden Sie dann den wachsenden Hauptbereich mit allen nicht zusammenhängenden Räumen, indem Sie den Vorgang mit Dijkstra mehrmals wiederholen.
AturSams
Ich habe einen CS-Hintergrund. Die geheime Sauce hier verwendet Dijkstra (oder vielleicht A *), um die Wandzellen zu durchqueren. Sehr interessante Idee; Danke, ich werde es versuchen.
Asche999
1

Arthurs Antwort scheint Ihr Problem zu lösen, aber hier ist ein einfacher Ansatz:

  1. Beginnen Sie mit einer der leeren Zellen.
  2. Markieren Sie mit dem BFS-Algorithmus alle Zellen in diesem Bereich.
  3. Fügen Sie alle im vorherigen Schritt besuchten Knoten hinzu, um die Liste der neuen BFS-Algorithmen zu starten, und durchsuchen Sie sie durch die Wände, bis Sie einen anderen leeren Bereich finden, der noch nicht besucht wurde
  4. Löschen Sie den Pfad, den Ihr zweites BFS genommen hat, um das neue Gebiet zu erreichen.
  5. Wiederholen Sie den Vorgang ab Schritt 2, bis alle Zellen besucht sind.

Beachten Sie, dass Sie bei jeder Wiederholung nur das vorherige BFS fortsetzen müssen. Ich meine, ein Neustart des Algorithmus von Anfang an verringert nur Ihre Leistung und führt zu keinen besseren Ergebnissen.

Ali1S232
quelle
1
Ich verstehe, was Sie tun, aber wenn Sie das nicht stoppen bfsund nur von den aktuellen Außenwänden des Perimeters aus neu starten, garantiert dies nicht, dass die kürzesten Wege zwischen offenen Bereichen genommen werden. Davon abgesehen sollte es ziemlich gleich funktionieren und die Lösung und ihre Komplexität vereinfachen.
AturSams
Nun, es garantiert den kürzesten Weg. Und selbst wenn ich einen Fehler mache (den ich wirklich bezweifle), sind die generierten Pfade nahezu optimal.
Ali1S232
1

Wenn Sie noch eine einfachere Lösung wünschen, da die Räume einfach und kreisförmig sind, können Sie dies stattdessen tun:

  1. Wähle zufällig einen Raum aus.
  2. Fügen Sie es der (derzeit leeren) Liste der visitedRäume hinzu.
  3. Durchlaufen Sie eine Datenstruktur, die alle unvisitedRäume enthält, und suchen Sie den nächstgelegenen unvisitedRaum. Wenn der Abstand zwischen ihnen kleiner als die Summe ihrer Radien ist, gibt es wahrscheinlich keinen Grund, sie zu verbinden, aber auf jeden Fall einen Korridor mit einer nicht geraden Linie zwischen ihren Zentren zu "zeichnen" (ich werde den Algorithmus später beschreiben).
  4. Wiederholen Sie alles unvistedund finden Sie dasjenige, das einem von denen am visitednächsten ist.
    • min [(xu-xv)^2 + (yu-yv)^2].
  5. Verbinden Sie die beiden Räume, fügen Sie den neuen Raum hinzu visited, entfernen Sie ihn aus dem unvisitedund wiederholen Sie den Vorgang, bis alle Räume visitederfolgreich sind.

Dies sollte mit einer Karte funktionieren, die weniger als hundert Räume hat, aber in vielerlei Hinsicht in der Recheneffizienz verbessert werden könnte (die für die Frage irrelevant sind).

Verwenden Sie den folgenden Pseudo-Algorithmus, um eine nicht gerade Linie zu zeichnen:

Der Code wurde von hier übernommen

       /**
        * Draw a line
        * 
        * @param x0     first point x coord
        * @param y0     first point y coord 
        * @param x1     second point x coord
        * @param y1     second point y coord
        * @param c      color (0xaarrvvbb)
        */
        public function line ( x0:int, y0:int, x1:int, y1:int, color:uint ):void
        {   
            var dx:int;
            var dy:int;
            var i:int;
            var xinc:int;
            var yinc:int;
            var cumul:int;
            var x:int;
            var y:int;
            x = x0;
            y = y0;
            dx = x1 - x0;
            dy = y1 - y0;
            xinc = ( dx > 0 ) ? 1 : -1;
            yinc = ( dy > 0 ) ? 1 : -1;
            dx = dx < 0 ? -dx : dx;
            dy = dy < 0 ? -dy : dy;
            setPixel32(x,y,color);

            if ( dx > dy )
            {
                cumul = dx >> 1;
                for ( i = 1 ; i <= dx ; ++i )
                {
                    x += xinc;
                    cumul += dy;
                    if (cumul >= dx)
                    {
                        cumul -= dx;
                        y += yinc;
                    }
                    setPixel32(x,y,color);
                }
            }else
            {
                cumul = dy >> 1;
                for ( i = 1 ; i <= dy ; ++i )
                {
                    y += yinc;
                    cumul += dx;
                    if ( cumul >= dy )
                    {
                        cumul -= dy;
                        x += xinc ;
                    }
                    setPixel32(x,y,color);
                }
            }
        }
AturSams
quelle
1

Leider erwiesen sich beide Lösungen von Arthur für mich nicht als brauchbar. Es kam zu einem Problem, das lösbar ist, aber nicht schnell genug lief (es dauerte eine Größenordnung von Sekunden, bis es lief; ich brauche etwas fast augenblickliches).

Dies ist vielleicht meine Schuld, weil ich nicht alles genau so implementiert habe, wie er es vorgeschlagen hatte, sondern stattdessen einfacheren Code (über schnelleren Code) gewählt habe.

Trotzdem habe ich eine einfache Lösung gefunden, die schnell ausgeführt und einfach zu codieren ist. Die Hauptschritte sind:

  • Angenommen, der "Startraum" ist nicht der größte, sondern der Raum, in dem der Spieler erscheint
  • Suchen Sie für jeden nicht verbundenen Raum den nächstgelegenen verbundenen Raum (O (n ^ 2)).
  • Erstellen Sie einen Tunnel, der die beiden Räume verbindet

Dies ist kein minimaler Spanning Tree, daher gibt es Fälle, in denen die Reihenfolge wichtig ist. Ich iteriere Räume in der falschen Reihenfolge und verbinde sie am Ende auf längere Weise anstatt auf kürzere Weise.

Für mein Spiel und meine Anforderungen hat dies funktioniert. In Zukunft kann ich es erweitern, indem ich stattdessen einen minimalen Spannbaum verwende.

Für die Nachwelt ist hier derselbe Boden, der mit meiner Lösung erzeugt wurde.

Geben Sie hier die Bildbeschreibung ein

Sie können einen Schnappschuss des Kerncodes auf GitHub sehen, beginnend hier .

Asche999
quelle
Ja, ein minimaler Spannbaum wäre hier optimal. Die anderen Lösungen sind nicht so gut.
AturSams