Generieren Sie zufällig einen gerichteten Graphen in einem Raster

Ich versuche, zufällig ein gerichtetes Diagramm zu erstellen, um ein Puzzlespiel zu erstellen, das den Eisrutschpuzzles von Pokemon ähnelt.
Dies ist im Wesentlichen das, was ich zufällig generieren möchte: http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory .

Ich muss in der Lage sein, die Größe des Diagramms in einer x- und y-Dimension zu begrenzen. In dem im Link angegebenen Beispiel wäre es auf ein 8x4-Raster beschränkt.
Das Problem, auf das ich stoße, besteht nicht darin, den Graphen zufällig zu generieren, sondern zufällig einen Graphen zu generieren, den ich in einem 2D-Raum richtig abbilden kann, da ich etwas (wie einen Stein) auf der gegenüberliegenden Seite eines Knotens benötige, um ihn zu erstellen Optisch sinnvoll, wenn Sie aufhören zu rutschen. Das Problem dabei ist, dass der Stein manchmal auf dem Weg zwischen zwei anderen Knoten oder möglicherweise auf einem anderen Knoten selbst landet, wodurch der gesamte Graph gebrochen wird.

Nachdem wir das Problem mit einigen mir bekannten Personen besprochen hatten, kamen wir zu einigen Schlussfolgerungen, die zu einer Lösung führen könnten.

• Einbeziehen der Hindernisse in das Raster als Teil des Diagramms bei der Erstellung.
• Beginnen Sie mit einem vollständig ausgefüllten Raster und zeichnen Sie einfach einen zufälligen Pfad und löschen Sie Blöcke, damit dieser Pfad funktioniert.

Das Problem besteht dann darin, herauszufinden, welche gelöscht werden müssen, um die Einführung eines zusätzlichen, kürzeren Pfads zu vermeiden. Wir dachten auch, dass ein dynamischer Programmieralgorithmus von Vorteil sein könnte, obwohl keiner von uns zu geschickt darin ist, dynamische Programmieralgorithmen aus dem Nichts zu erstellen. Alle Ideen oder Referenzen darüber, wie dieses Problem offiziell genannt wird (wenn es sich um ein offizielles Grafikproblem handelt), wären am hilfreichsten.

Hier sind einige Beispiele dafür, was ich bisher erreicht habe, indem ich nur zufällig Blöcke platziert und das Navigationsdiagramm aus dem ausgewählten Start / Ziel generiert habe. Die Idee (wie im vorherigen Link beschrieben) ist, dass Sie am grünen S beginnen und zum grünen F gelangen möchten. Sie bewegen sich dazu nach oben / unten / links / rechts und bewegen sich weiter in die gewählte Richtung, bis Sie a treffen Mauer. In diesen Bildern ist Grau eine Wand, Weiß ist der Boden und die violette Linie ist die Mindestlänge von Anfang bis Ende, und die schwarzen Linien und grauen Punkte repräsentieren mögliche Pfade.

Hier sind einige schlechte Beispiele für zufällig generierte Diagramme:

Hier sind einige gute Beispiele für zufällig generierte (oder von Hand optimierte) Diagramme:

Ich habe auch bemerkt, dass die schwierigeren, wenn ich dies tatsächlich als Puzzle spiele, diejenigen sind, die viele hochgradige Knoten entlang des minimalen Pfades haben.

• Es ist Eis, du wirst dich bewegen, wenn du nicht auf einen Felsen triffst.
• Die einzige Möglichkeit, die Richtung zu ändern, besteht darin, einen Stein zu treffen.
• Wenn Sie auf einen Felsen treffen, müssen Sie die Richtung ändern.
• Zyklen sind aus offensichtlichen Gründen gut.
• Es kann mehrere Starts und mehrere Enden geben.

erweiterte Eigenschaften:

• Die Zellen ohne angrenzende Felsen sind nicht erreichbar (einige können durchquert werden)
• Wände sind auch Steine. Wenn Sie sie entfernen, können Sie sich entscheiden, sie zu umwickeln.
• Sie können Teilgitter als Muster verwenden ("Kacheln" 3x3, 3x4, 5x5, ... usw.)
• Sie können ein Puzzle-MxN-Plättchen über einen nicht durchquerbaren MxN-Bereich legen und einen Stein hinzufügen, um ihn hinein- und herauszuleiten.
• Drehung oder Symmetrie einer Fliese kann interessant sein
• Sie können eine Kachel erweitern, indem Sie eisige Zeilen / Spalten einfügen

Beispiel:

S=start, E=end, o=rock, .=ice

3 . 2 o        3 . . 2 o         . . . . . o o
4 . . E   ~=   4 . . . E   ~=    . . . . . 2 E
o . . .        o . . . .         . . . . . . .
S . 1 o        S . . 1 o         S . . . . 1 o

Beispiel für das Kombinieren von Kacheln:

3 . . 2 o       o 2 . . 3      3 . . 2 o 7 . . 6
4 . . . E   +   E . . . 4  =   4 . . . . . . . 5
o . . . .       . . . . o      o . . . . . . . o
S . . 1 o       o 1 . . S      S . . 1 o 8 . . E

Vielleicht gefällt dir das Spiel Tsuro , es verwendet Kacheln, um ein zufälliges Brett zu erzeugen.

Vielleicht könnte Ihnen Reverse Engineering helfen, wenn Sie dazu bereit sind.

Wenn es für jedes Problem nur eine einzige Lösung gibt, können Sie wahrscheinlich ein Diagramm basierend auf der eindeutigen Antwort erstellen. Dies erfordert keine dynamische Programmierung oder sogar das Überspringen von Brute Force und die Entscheidung für eine methodische Generierung.

Sie können es tun, indem Sie:

1. Halten Sie ein MxN-Diagramm bereit
2. Erstellen einer / mehrerer Lösung (en)
3. eine Frage stellen, ob es sich um ein singuläres Lösungsproblem handelt
4. Wenn es mehrere Lösungen für das Problem gibt, können Sie den obigen Vorgang so wiederholen, dass die aktuelle Iteration keine andere Lösung verhindert.

Sie müssen jedoch einen Weg finden, der der Komplexität und Problemgröße des Problems entspricht und diese Frage für Sie generiert. Gehen Sie nicht einfach auf Brute-Force. Versuchen Sie stattdessen einen zufälligen Algorithmus. Dies könnte Ihnen helfen.

Wie wäre es mit einem anderen Ansatz? Beginnen Sie mit einem leeren Labyrinth und fügen Sie Blöcke wie folgt hinzu:

1. Zufälliger Startblock und Endblock.
2. Machen Sie 1-3 "gleitende" Schritte in zufälliger (aber nicht zurückkehrender) Richtung und mit zufälliger Länge (*). Platzieren Sie nach jedem Schritt einen Block (um die Folie anzuhalten).
3. Finden Sie einen kürzesten Weg zum Ausgang. Wenn es zu wenige Segmente gibt (niedriger Schwierigkeitsgrad), nehmen Sie ein zufälliges Segment des Pfades und teilen Sie es mit einem Block. Andernfalls platzieren Sie einen Block wie in Schritt 1 und beenden Sie den Vorgang.
4. Wiederholen Sie 1 mit Vorsicht (*): Wenn Sie die Länge eines Gleitschritts auswählen, stellen Sie sicher, dass der von Ihnen platzierte Block den vorherigen Pfad nicht schließt.

Abschluss: Finden Sie den kürzesten Weg mit dem von Ihnen bereitgestellten Algorithmus. Notieren Sie sich alle verwendeten Zellen und füllen Sie den Rest nach dem Zufallsprinzip auf, um sicherzustellen, dass der kürzeste Weg nicht kürzer wird.

In Schritt 2 gibt es eine Einschränkung, wenn Sie den letzten Block nicht so platzieren können, dass er die verwendeten Pfade nicht kreuzt. Ich sehe jedoch zwei Lösungen dafür: Verschieben Sie den Endblock früher oder machen Sie einige Schritte rückgängig und versuchen Sie es erneut.

Und noch ein Gedanke für die zufällige Länge der Gleitschritte: Vielleicht möchten Sie sie so auswählen, dass ein früher platzierter Block wiederverwendet wird, solange sich die Pfade nicht überlappen.