Sicherstellen, dass das Labyrinth der Hauskarten mit Aufzügen gelöst werden kann?

13

In meinem Spiel sehen wir die Fußböden eines Hauses von der Seite, und der Held kann Aufzüge nehmen - ein Aufzug fährt entweder nach oben (zum nächsten Aufzug nach oben) oder nach unten (zum nächsten Aufzug nach unten), je nach Pfeil als angezeigt, und es sind immer genau zwei Aufzüge miteinander verbunden. Nur so kann sich der Held vertikal bewegen, obwohl er sich horizontal frei bewegen kann. Die Hauskarte ist ein zufälliges 11x5-Raster mit verschiedenen Elementen und unüberwindlichen Wänden ganz links, ganz rechts und manchmal in einer der beiden mittleren Positionen:

Beispiel Aufzüge

Meine Frage: Wie kann ich sicherstellen, dass die Karte immer zufällig und dennoch immer lösbar ist und dass der Held, beginnend auf der linken Seite der unteren Etage, sie immer über einen nach oben weisenden Aufzug in der oberen Etage verlassen kann?

Für das, was es wert ist, verwende ich die Lua-Sprache für die Entwicklung. Vielen Dank!

2d maze Philipp Lenssen
quelle

Antworten:

14

Was Sie tun möchten, ist, ein Diagramm so zu erstellen, dass jeder Knoten eine Aufzugsposition ist und die Kanten zwischen ihnen bedeuten, dass Sie dort gehen / heben können. Sobald Sie das Diagramm erstellt haben, können Sie mit dfs / bfs prüfen, ob Sie vom Startknoten zum Endknoten gelangen können.

Anhand des obigen Beispiels habe ich ein Bild gemacht, wie das Diagramm aussehen würde. Grüne Kreise bedeuten, dass sich dort ein Aufzug befindet, und die grünen Linien bedeuten, dass Sie von Knoten zu Knoten fahren können.

Knoten

Luis Estrada
quelle
Danke, das ist sehr nützlich! Ich hätte in meiner Frage mehr betonen sollen, dass die Karte auch an erster Stelle generiert werden muss. Was ich jetzt überlege, ist, ob es nicht einfacher sein könnte, als immer wieder vollständig zufällige Kombinationen von Aufzügen und Wänden zu generieren und ihre Lösbarkeit zu überprüfen, wenn der Algorithmus wie der Held durch das Haus geht und auf diese Weise Generieren Sie zufällige Aufzüge und Türen (indem Sie zufällige Abstände zwischen Aufzügen und Abbiegungen von links nach rechts einhalten und beispielsweise Wände hinzufügen). Wie in "Gehen Sie nach rechts, entweder 0, 4 oder 8 Umdrehungen; schaffen Sie einen Aufstieg, steigen Sie von 1 auf 4 Stockwerke auf ..."
Philipp Lenssen
@PhilippLenssen Dies ist im Wesentlichen der Ansatz der "randomisierten Tiefensuche" zur Erzeugung von Labyrinthen in einem Graphen.
Kevin Reid
5

Der Unterschied zwischen dem, was Sie haben, und einem normalen Labyrinth besteht einfach darin, dass es vertikal nicht benachbarte Verbindungen hat. Ich denke, Sie sollten sich graphbasierte Labyrinth-Generierungsalgorithmen ansehen . Sie müssen einfach eine größere Menge von "angrenzenden Räumen" oder "möglichen Wänden" haben als ein gewöhnliches 2D-Labyrinth, da jedes vertikal ausgerichtete Paar von Bodengitterzellen, das noch keinen dazwischenliegenden Aufzug hat, benachbart ist. Sie könnten dies als ein Diagramm modellieren, in dem das Hinzufügen bestimmter Auftriebskanten nebenbei andere mögliche Auftriebskanten löscht. Einige Algorithmen könnten dadurch verwirrt werden, andere jedoch nicht.

Kevin Reid
quelle