Wenn Sie das Wort " Verbundenheit" verwenden , sind Sie nur einen Katzensprung vom Werkzeug entfernt, das für die Bestimmung einer Lösung am besten geeignet ist: die Graphentheorie.
Verbundenheit ist eine Eigenschaft von Graphen. Diagramme können entweder verbunden oder getrennt werden (wie Sie erfahren, AKA ein Multigraph). Jedes Spiellevel in einer beliebigen Anzahl von Dimensionen kann als Grafik dargestellt werden. Logischerweise ist dies häufig der beste Weg, um sie zu manipulieren. Ihre Spielwelt ist ein Diagramm in Bezug auf die Nachbarschaft zwischen den einzelnen Bausteinen in Ihrer Welt. und auch auf der Ebene der Konnektivität zwischen Ihren verschiedenen Bereichen. Sie können das erstere verwenden, um das letztere abzuleiten.
Bei der Arbeit mit (2D) -Ebenen als Diagramme ist ein entscheidender Punkt zu berücksichtigen, und das ist Planarität . Abhängig von Ihren Anforderungen kann Planarität ein Problem sein oder auch nicht. Angesichts Ihrer Verwendung von Lärm erwarte ich Letzteres, aber ich skizziere hier die Optionen, damit Sie wissen, was sie sind.
Planarer Graph - einfachstes Beispiel ist ein Labyrinth. Ein Labyrinth unterscheidet sich von einem Labyrinth dadurch, dass es keine Verzweigungen enthält - es ist unikursal . Wenn Sie einen festen Gebüschblock (!) Nehmen und einen Labyrith durch ihn erzeugen würden, könnte eine Wende, die das Labyrinth nimmt, zu keinem Zeitpunkt auf einen vorhandenen Pfad stoßen. Es ist wirklich ein bisschen wie ein Schlangenspiel - wenn der Pfad der Körper der Schlange ist, darf er sich nicht beißen / schneiden. Außerdem könnten Sie ein planares Labyrinth haben; Dies würde sich verzweigen, aber zu keinem Zeitpunkt dürfen die Zweige vorhandene Teile des bereits erzeugten Labyrinths schneiden, genau wie bei einem Labyrinth.
Nicht planares Diagramm - Das einfachste Beispiel ist ein Stadtstraßenplan. Eine Stadt ist im Wesentlichen ein Labyrinth. Es ist jedoch ein stark verbundenes Labyrinth, da es viele einzelne Straßenrouten gibt, die von einem Ort zum anderen gelangen. Darüber hinaus ermöglicht eine nicht planare Grapheneinbettung Kreuzungen, was genau die Schnittpunkte sind. Und wie wir wissen, ist eine Stadt keine Stadt ohne Kreuzungen. Sie sind ein wesentlicher Bestandteil des Verkehrsflusses. In Spielen kann dies je nach Ihren Zielen gut oder schlecht sein. Ein guter Level-Flow ermöglicht es der KI, leichter zu agieren und die Erkundung freier zu gestalten. Andererseits ermöglicht es einem Spieler auch, schnell vom Startpunkt zum Ziel zu gelangen - möglicherweise zu schnell.
Dies bringt uns zu Ihrem Ansatz, Lärm zu verwenden. Abhängig von der Interpretation des Perlin-Rauschausgangs kann es einen gewissen Grad an Verbundenheit als Makroskala haben, es ist jedoch nicht für 1-Verbundenheit ausgelegt (ein einzelnes Diagramm). Dies lässt Ihnen einige Optionen.
Lassen Sie die Verwendung von Perlin-Rauschen fallen und generieren Sie stattdessen einen zufälligen, planaren (nicht kreuzenden), verbundenen Graphen. Dies bietet maximale Flusskontrolle. Dieser Ansatz ist jedoch nicht trivial, da die Planarität von Graphen die Identifizierung und Entfernung der Kuratowski-Untergraphen K3,3 und K5 erfordert. sowie Herstellen einer nachfolgenden planaren Einbettung; Beides sind NP-vollständige Probleme. Dies ist ohne Zweifel der schwierigste Ansatz, aber er musste zuerst erwähnt werden, um zu wissen, wo Sie stehen. Alle anderen Methoden sind eine Art Abkürzung um diese Methode, die die grundlegende Mathematik hinter der Labyrinthgenerierung darstellt.
Lassen Sie die Verwendung von Perlin-Rauschen fallen und generieren Sie stattdessen ein zufälliges, nicht planares Diagramm, das in eine planare Oberfläche eingebettet ist (AKA, eine planare Einbettung). So können Spiele wie Diablo und die Roguelikes problemlos funktionieren, da beide ein Raster verwenden Struktur zur Unterteilung eines planaren Raums (tatsächlich erlaubt die überwiegende Mehrheit der Ebenen in den Roguelikes Kreuzungen, was sich in der Anzahl der Vier-Wege-Kreuzungen zeigt). Algorithmen, die die Konnektivität zwischen Zellen oder Vorlagenräumen herstellen, werden häufig als "Schnitzer" oder "Tunnelbauer" bezeichnet, da sie schrittweise leeren Raum aus einem Felsblock herausschneiden.
Tun Sie dies als Option (2), aber vermeiden Sie Kreuzungen. Somit ist sowohl die Einbettung (Ebenengeometrie) planar als auch die Topologie (Ebenenfluss) planar. Sie müssen darauf achten, sich nicht in Sackgassen zu verwandeln, wenn Sie Kreuzungen vermeiden möchten.
Generieren Sie Ihre Karte mit Rauschen. Mithilfe eines Flutfüllungsalgorithmus für jede Zelle in Ihrer nicht verbundenen Ebene (ein Diagramm, wenn auch mehrteilig und gitterbasiert) können Sie dann alle nicht verbundenen, diskreten Untergraphen in diesem größeren Multigraph ableiten. Überlegen Sie sich als Nächstes, wie Sie die einzelnen Untergraphen verbinden möchten. Wenn Sie Kreuzungen vermeiden möchten, schlage ich eine sequentielle Verbindung dieser vor. Wenn nicht, können Sie sie beliebig verbinden. Um dies organisch zu tun, anstatt harte, gerade Passagen zu erzeugen, würde ich eine Art Kohärenzfunktion verwenden, um die nächsten Punkte jedes Paares von Untergraphen zu verschmelzen (wenn sie nacheinander verknüpft werden). Dadurch wird die Verbindung "flüssiger", was der typischen Perlin-Ausgabe entspricht. Die andere Möglichkeit, Bereiche zu verbinden, besteht darin, sie enger zusammenzustoßen.
Generieren Sie eine übermäßig große Karte mit Rauschen. Isolieren Sie alle Untergraphen wie in Option 3 beschrieben. Bestimmen Sie nach bestimmten Kriterien, welche am interessantesten ist (Größe oder etwas anderes, aber Größe ist am einfachsten). Wählen Sie nur den Teilgraphen aus und verwenden Sie ihn, der bereits vollständig selbst verbunden ist. Die Schwierigkeit bei diesem Ansatz besteht darin, dass es möglicherweise schwierig ist, die Größe Ihrer resultierenden Diagramme zu steuern, es sei denn, Sie generieren mit Brute Force eine wirklich große Karte oder viele kleinere, um Ihren perfekten Untergraphen auszuwählen. Dies liegt daran, dass die Größe der Untergraphen wirklich von den verwendeten Perlin-Parametern und der Interpretation des Ergebnisses abhängt.
Abgesehen von den letzten beiden, etwas, das Sie sicher bereits getan haben, aber nur für den Fall, dass dies nicht der Fall ist: Erstellen Sie in Flash einen Testfall für minimales Perlin-Rauschen. Spielen Sie mit den Parametern, bis Sie einen höheren Grad an Konnektivität zwischen Ihren "Insel" -Bereichen erhalten. Ich glaube nicht, dass dies Ihr Problem jemals über alle Generationen hinweg zu 100% lösen könnte, da Perlin-Rauschen keine inhärente Garantie für die Verbundenheit hat. Aber es könnte die Verbundenheit verbessern.
Was auch immer Sie nicht verstehen, fragen Sie und ich werde es klären.
Allgemeine Ansätze zu diesem Problem:
Ich stimme Kylotan zu, dass eine Rauschfunktion wahrscheinlich nicht ideal ist, aber Rauschfunktionen können viel bewirken und Sie können sie möglicherweise auf irgendeine Weise beheben. In diesem Artikel finden Sie einige Ideen.
quelle
Das Video ist nur verwirrend und ich kann nicht herausfinden, was Sie damit zeigen wollen, um ehrlich zu sein. Aber ich würde vorschlagen, dass Perlin-Rauschen wahrscheinlich der falsche Algorithmus für den Job ist. Es wurde für die reibungslose Welligkeit kontinuierlicher Entitäten entwickelt, während Sie versuchen, verstreute und diskrete Entitäten zu erstellen. Was wahrscheinlich besser funktionieren würde, ist die Verwendung von Zufallswerten, um handgefertigte Anordnungen von Plattformen neu anzuordnen und anzupassen, um sicherzustellen, dass der resultierende Bereich spielbar ist.
Hier finden Sie einige Informationen dazu, wie Spelunky dies getan hat: http://tinysubversions.com/2009/09/spelunkys-procedural-space/
quelle
Versuchen Sie, den Perlin-Wert basierend auf der Höhe zu ändern, dh addieren Sie unten 1 zum Rauschwert, subtrahieren Sie oben 1 vom Rauschwert und interpolieren Sie zwischendurch linear zwischen 1 und -1. Auf diese Weise erhalten Sie unten fast garantiert einen Wert> = 0 und oben fast garantiert einen Wert <= 0.
Dies setzt voraus, dass Werte <0 Luft sein sollen. Wenn ich Ihre Beschreibung richtig verstehe, müssen Sie sie umschalten.
Prost.
quelle
Ein einfacher Ansatz, den Sie angesichts Ihres vorhandenen Codes leicht anwenden können, besteht darin, so lange zufällige Karten zu generieren, bis eine Ihre Verbindungsbeschränkungen erfüllt.
Sie können Ihre Verbindungsbeschränkung wahrscheinlich schnell mit einer Flutfüllung von der Startposition aus überprüfen. Füllt es sich bis zu einem rechtlichen Endpunkt?
Sie können wahrscheinlich Tausende solcher Überprüfungen pro Sekunde durchführen, daher ist dies wahrscheinlich ein durchaus akzeptabler Hack.
quelle