Ich versuche ein kleines Roguelike zu kreieren und bin so weit gegangen, dass ich zufällig Räume und Korridore generiere. Jeder Raum ist ein instanziiertes Objekt und enthält eine Arrayliste der anderen Räume, die durch einen Korridor verbunden sind.
Ich kann nicht verbundene Räume herausgreifen, aber wie kann ich die Räume kennen, die nur miteinander verbunden sind, aber nicht mit den meisten anderen, die eine Insel bilden?
Um dies besser zu veranschaulichen, ist das Problem hier ein Bild von der Konsole auf einer festgefahrenen Ebene. Die Räume 5 und 6 sind nur miteinander verbunden. Welchen Algorithmus kann ich verwenden, um das zu erkennen?
Antworten:
Beginnen Sie mit einer vollständigen Liste der Zimmer. Wähle einen Startraum. Navigieren Sie von diesem Raum zu allen verbundenen Räumen. Entfernen Sie es für jeden Raum, den Sie besuchen, aus der Liste der Räume und fügen Sie es einer Liste A hinzu . Sobald Sie alle Ihre Verbindungen besucht haben, sind alle auf der Liste verbleibenden Räume nicht mehr mit dem Startraum oder einem der Räume auf Liste A verbunden .
Sie können dann fortfahren, indem Sie einen Raum aus den Resten der vollständigen Liste auswählen und erneut navigieren. Diesmal zur Liste B hinzufügen . Setzen Sie diesen Vorgang fort, bis Sie keine Räume mehr auf der ursprünglichen Liste haben. Sie haben jetzt Listen aller verbundenen Raumsets.
Probleme wie dieses lassen sich leicht an graphentheoretische Probleme anpassen. Das oben beschriebene Problem bezieht sich beispielsweise direkt auf die Konnektivität .
quelle
Ihre Raumsammlung ist im Wesentlichen ein Diagramm, und Ihr Problem besteht darin, verbundene Komponenten ("Inseln") in diesem Diagramm zu finden.
Eine einfache Möglichkeit, verbundene Komponenten zu finden, besteht darin, BFS (Breitensuche) von jedem Scheitelpunkt aus durchzuführen. Wenn Sie BFS von einem Scheitelpunkt A aus ausführen, erhalten Sie alle Scheitelpunkte in der verbundenen Komponente, zu der Scheitelpunkt A gehört.
Im Grunde genommen beginnen Sie mit einem beliebigen Scheitelpunkt, führen ein BFS durch und markieren jeden angetroffenen Scheitelpunkt als Mitglied der 1. "Insel". Dann fahren Sie mit dem nächsten nicht markierten Scheitelpunkt fort und führen erneut ein BFS durch. Diesmal kennzeichnen Sie angetroffene Scheitelpunkte als Mitglieder der 2. "Insel" und so weiter.
quelle
Sie können die Räume als Eckpunkte in einem gerichteten Diagramm darstellen . Auf diese Weise können Sie bekannte Algorithmen anwenden, um Ihr Problem zu lösen.
Der Dijkstra-Algorithmus erzeugt beispielsweise einen kürzesten Pfadbaum für einen bestimmten Startscheitelpunkt in einem Diagramm. Dieser Baum enthält alle erreichbaren Eckpunkte vom Startpunkt aus. Sie können dann ableiten, dass die im Baum nicht vorhandenen Eckpunkte Teil anderer Inseln sind. Sie können den Algorithmus auf diese Eckpunkte anwenden, um Bäume zu erhalten, die jede Insel darstellen.
quelle