Wie kann ich schrittweise ein Diagramm erstellen?

8

Ich habe gerade ein neues Projekt gestartet, in dem ich möchte, dass die Spielwelt aus prozedural generierten Orten besteht, die durch Teleporter verbunden sind. Nach ein wenig Recherche habe ich festgestellt, dass dies entweder als "Graphentheorie" oder als "blutig kompliziert" bezeichnet wird, je nachdem, wer darüber spricht. Leider habe ich nur sehr wenige Informationen zum Generieren von Diagrammen gefunden. Die meisten Tools, die ich gesehen habe, zielen darauf ab, vorhandene Diagramme zu untersuchen.

Vorausgesetzt, ich habe die Terminologie korrekt sortiert, muss das Diagramm wie folgt lauten:

  • einfach - kein Ort (Scheitelpunkt) sollte einen Teleporter (Rand) haben, der wieder mit sich selbst verbunden ist, noch sollten zwei Scheitelpunkte mehrere Kanten haben, die sie verbinden
  • verbunden - es sollte möglich sein, zwischen zwei beliebigen Eckpunkten in der Grafik zu reisen (obwohl ich nicht voraussehe, dass ich jemals den Pfad finden muss; es reicht aus, nur zu wissen, dass der Spieler einen finden kann, wenn er dies wünscht)
  • zyklisch - Es sollte mehr als einen Pfad zwischen zwei beliebigen Scheitelpunkten geben
  • ungerichtet - alle Kanten können in beide Richtungen bewegt werden
  • unendlich - wenn der Spieler dies wünscht, sollte er in der Lage sein, unbegrenzt zu reisen, wobei der Graph weiterhin inkrementell generiert wird, wenn er sich seinen äußersten unerforschten Eckpunkten nähert
  • lokal endlich - der Grad eines Scheitelpunkts sollte sich niemals ändern, nachdem der Spieler ihn besucht hat
  • stabil markiert - jeder Scheitelpunkt stellt einen Ort dar, der selbst prozedural aus einem Samen erzeugt wird; Der gleiche Startwert muss einem Scheitelpunkt zugewiesen werden, unabhängig davon, welchen Pfad der Spieler verwendet hat, um dorthin zu gelangen, oder wie groß die Grafik ist, wenn er dies tut

Ich hatte einige Ideen (die ich noch nicht zu implementieren versucht habe) bezüglich der Verwendung der lokalen Maxima des 2D-Perlin-Rauschens als Eckpunkte (die Eingabe x und y könnte dann als Bezeichnung verwendet werden), aber das fühlt sich klobig und überkompliziert an.

Gibt es eine bessere Möglichkeit, ein solches Diagramm zu erstellen? Ich entwickle in Python 2.6 mit Panda3D und numpy und wäre natürlich bereit, andere Bibliotheken einzubeziehen, wenn sie bei diesem Problem helfen!

Bearbeiten

Ich glaube, ich habe einige meiner Anforderungen schlecht erklärt, also ist es Zeit für Illustrationen! Hoffentlich klärt dies die Dinge auf.

Was ich mit stabilen Etiketten meine, ist, dass ich zum Beispiel möchte, dass Spieler A eine Reihe von Erkundungen durchführen und unter anderem einen Radweg zurück zu seinem Startort und einen Berg finden kann, der wie eine Katze aussieht. Sein Spiel sieht nun ungefähr so ​​aus (Eckpunkte werden mit ihrem Samen und Kanten in der Reihenfolge nummeriert, in der der Spieler sie durchquert hat). Er startete am Scheitelpunkt 8329 (grün) und Happycat Mountain befindet sich am Scheitelpunkt 6745 (blau).

Weltgraph von Spieler A.

Der gute Freund von Spieler A Spieler B ist ein Fan von Katzen, deshalb möchte er es ihr zeigen. Er gibt ihr den Wurzelsamen für seine Welt und Richtungen entlang des kürzeren Weges zum Berg von Interesse. Ihr Spiel sollte jetzt so aussehen:

Weltgraph von Spieler B.

Das Problem, mit dem ich derzeit am meisten Schwierigkeiten habe, ist: "Wie generiere ich die gleichen Samen für Spieler B, wenn ihre Erkundung nicht den gleichen Weg gegangen ist?" Das brachte mich auf die Idee, Perlin-Rauschen zu verwenden - solange derselbe Wurzelsamen verwendet wird, bewegen sich die Maxima nicht, sodass ihre Koordinaten als stabile Scheitelpunktsamen verwendet werden können.

Ben Blank
quelle
Warum passt ein verbundener Graph nicht dazu? mathworld.wolfram.com/ConnectedGraph.html Möglicherweise fehlt mir der Punkt. Wenn ein Benutzer von einem Ort zum anderen wechseln möchte und alle verbunden sind, geben Sie ihm eine Liste der Orte und verschieben Sie seine Position auf der Weltkarte an den neuen Ort.
Brandon
@brandon - "Verbunden" ist die zweite Eigenschaft, die ich aufführe. :-)
Ben Blank
Mein Punkt ist, wenn Sie von einem Knoten zu einem anderen gehen können. Wenn sie einen Teleporter besuchen, geben Sie ihnen eine Liste aller Knoten, die sie besucht haben, mit Ausnahme dieses Knotens. Es ist kein Diagramm erforderlich. Sie führen eine Liste aller besuchten Knoten und ihrer Standorte und teleportieren sich einfach zu dem von ihnen ausgewählten Standort. Bin ich falsch verstanden?
Brandon
Fast alle Ihre Beschreibungen dieser Begriffe sind korrekt, mit Ausnahme von "zyklisch" und "lokal endlich". Das erste schränkt Ihre Grafiken so ein, wie sie klingen - ein Kreis. Ein Begriff, den Sie für die Anforderung verwenden können, dass es mehr als einen Pfad von einem Scheitelpunkt zu einem anderen gibt, ist "2-verbunden". "Lokal endlich" bedeutet nur, dass jeder Scheitelpunkt eine endliche Anzahl von Kanten hat.
Harry Stern
@Harry Stern - Mein Verständnis ist , dass zyklische Graphen sind grafische Darstellungen , die mindestens eine grafische Darstellung Zyklus . Es klingt wie Sie über ein sprechendes Zyklusdiagramm , das eine grafische Darstellung eines einzelnen Graphen - Zyklus und nichts anderes aus ist. Ich suche speziell nicht nach Grafiken, die "2-verbunden" sind (siehe "einfach"). Und ja, das habe ich mit "lokal endlich" gemeint.
Ben Blank

Antworten:

6

Sie können kein unendliches Diagramm erstellen. Ihr Gedächtnis ist endlich, daher ist auch die Anzahl der Eckpunkte und Kanten endlich. Sie können ein endliches Diagramm erstellen und dann weitere hinzufügen. Sie scheinen dies erkannt zu haben, aber ich denke, es ist wichtig, dass dies ausdrücklich angegeben wird, damit Sie nicht in eine Sackgasse gehen.

Sie müssen sehr vorsichtig sein, wenn Sie von "äußersten Eckpunkten" sprechen. Ein Graph ist eine Menge von Eckpunkten, eine Menge von Kanten und eine Funktion, die die beiden in Beziehung setzt. Es gibt keine festgelegte geometrische Interpretation, es sei denn, Sie wenden eine an. Zum Beispiel: Beide Bilder zeigen genau das gleiche Diagramm. Im ersten Bild könnte der Scheitelpunkt 2 als "äußerster" Scheitelpunkt betrachtet werden, im zweiten Bild würde der Scheitelpunkt 2 nicht als "äußerster" betrachtet. Wenn Sie drei Dimensionen betrachten, können Sie sagen, dass alle Eckpunkte "äußerste" sind.

Grafik 1 Grafik 2

Dies bedeutet, dass Sie einige andere Informationen haben müssen, damit Sie wissen können, was ein "äußerster" Scheitelpunkt ist. Sie könnten (x, y) Paare verwenden, da dies eine leicht zu visualisierende geometrische Darstellung ermöglicht, aber ich denke nicht, dass Sie so weit gehen müssen. Nach allem, was Sie sagen, müssen Sie nur wissen, welche Scheitelpunkte bereits im Diagramm enthalten sind.

Wenn Sie dies jedes Mal ausgeführt haben, wenn Sie einen Scheitelpunkt besucht haben:

if(this.needsNeighbours)
{
    List<int> connections = genRandomNumbers(n);
    foreach (int connection in connections)
    {
        //Simple graph
        if(connection == this.seed || this.hasNeighbour(connection))
        {
            continue;
        }
        //Connections to already existing, unvisited vertices
        else if(nodeMap.containsKey(connection) && 
                nodeMap.getByKey(connection).needsNeighbours)
        {
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
        //Grow graph with new vertices
        else
        {
            nodeMap.add(connection, new Node(connection));
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
    }
    this.needsNeighbours = false;
}

Ihr Diagramm würde alle Ihre Anforderungen erfüllen, außer dass es zyklisch ist. Ich weiß nicht, ob Sie tatsächlich eine Garantie benötigen. Wenn Sie dies tun, können Sie speziell einen nicht besuchten Knoten auswählen und eine Verbindung herstellen. Dies würde einen Pfad zwischen dem aktuellen Knoten und einem bereits besuchten Knoten garantieren, da alle nicht besuchten Knoten mit mindestens einem besuchten Knoten verbunden sind und Sie einen besucht haben müssen Besuchen Sie den Knoten, um dorthin zu gelangen, wo Sie sich gerade befinden. Es gibt jetzt mindestens zwei Pfade.

Es ist einfach, weil es eine explizite Prüfung dafür gibt, verbunden, weil alle neuen Knoten mindestens eine Verbindung erhalten, lokal endlich, weil Kanten nur vor Ihrem Besuch oder bei Ihrem ersten Besuch hinzugefügt werden und nur zu nicht besuchten Knoten. Technisch gesehen ist es nicht ungerichtet, aber funktional ist es dasselbe, wenn Sie eine Richtungskante in beide Richtungen erstellen. Sie können den Knoten beliebig beschriften. Ich verwende die generierte Zufallszahl, aber Sie können dem Konstruktor auch andere Parameter hinzufügen, von denen einer Ihr Startwert ist.

Zäher Kaugummi
quelle
Sie nehmen genau wahr, was ich mit "unendlich" gemeint habe, und Ihr Punkt über "äußerste" ist gut aufgenommen - ich habe das Wort in meiner Frage optimiert. Entweder verstehe ich Ihren Generator jedoch nicht richtig oder ich habe meine Bedürfnisse schlecht erklärt, da dies nicht den gleichen Startwert für verschiedene Pfade zum gleichen Scheitelpunkt erzeugen würde. Ich habe meiner Frage einige Abbildungen hinzugefügt, die hoffentlich klarer machen, was ich erreichen möchte. :-)
Ben Blank
Ich verstehe, was du jetzt meinst. Das ist etwas schwieriger. Sie müssten lediglich den Aufruf von genRandomNumbers in eine Funktion ändern, die für ihre Eingabe immer die gleichen Zahlen zurückgibt, und den Startwert des Knotens als Argument verwenden. Dies würde garantieren, dass Sie die gleichen Verbindungen und Startwerte erhalten, unabhängig davon, welchen Pfad Sie einschlagen oder mit welchem ​​Knoten Sie beginnen. Sie müssen darauf achten, dass der Satz von Zahlen für Knoten B, mit dem A verbunden ist, auch A enthält, damit Sie Ihre ungerichtete Diagrammeigenschaft erhalten. Wenn Sie dies nicht tun, erhalten Sie ein gerichtetes Diagramm.
Chewy Gumball
1

Eine Methode:

init:
  root = generateLocation using random seed
  store root's seed
  place player in root location

when the player enters a new location:
  release the memory used by locations that are further than 1 edge away, but keep their seeds
  generate some neighbors for the new location. for every neighbor n:
    gen.seed(getSeed(n))
    n = generateLocation using n's random seed
    numCyclicEdges = gen.randint(0, 1)
    create numCycleEdges edges to existing locations

getSeed(n):
  if(n already has a seed) return n's seed
  else return randomSeed()

Es gibt viele Details, die ich ausgelassen habe, aber dies sollte die allgemeine Idee erfassen. Möglicherweise möchten Sie Nachbarn im Speicher behalten, die mehr Kanten vom aktuellen Standort entfernt sind, je nachdem, wie viel Weltabstand zwischen Portalen besteht, wie viel Speicher verfügbar ist usw.

Jiahua Wang
quelle