Wie erstellt man ein zufälliges Pacman-Labyrinth

Question

Hallo Ich habe an einem Algorithmus gearbeitet, um ein zufälliges Pacman-Labyrinth zu erzeugen. Ich habe ein paar Artikel gesehen, konnte aber die Logik nicht durchbrechen. Ich benutze zuerst den Labyrinth-Algorithmus und dann das Labyrinth, um jedes Labyrinth symetrisch zu machen. Ich stoße auf Probleme wie die Beseitigung der Sackgassen. Wenn das nicht möglich ist, würde ich auch einen anderen Algorithmus versuchen, wenn jemand seine eigene Logik hat, um das zufällige Labyrinth zu erzeugen. Jede Hilfe wird geschätzt. Danke

Answer 1

Ich würde anbieten, einen zufälligen Spaziergang durch dfs im sauberen Bereich zu machen (ohne irgendeine Wand, in n * n Matrix von Nullen), danach füllen Sie die Bereiche, die nicht durch zufälligen Spaziergang (machen sie als Wand), dies könnte auch zu ungenutzten Räumen führen, aber dies garantiert einen langen Spaziergang. Sie können die Größe des Weges beliebig einstellen (z. B. wenn Ihre Gehgröße bei (n^2)/2 angekommen ist, könnten Sie den Spaziergang stoppen).

Answer 2

Ich löste mein Problem und wollte teilen. Für den Anfang setze ich die obere Reihe und die erste Spalte und die letzte Spalte als ein Wandhindernis, dann setze ich einen Weg auf die zweite Spalte, vorletzte Reihe und zweite Reihe, so dass sie die äußere Wand umgibt. Bedenken Sie auch, dass ich nur 50% des Labyrinths erschaffe, also wenn ich fertig bin, kopiere ich das Labyrinth so, dass beide Seiten gleich sind. Dann habe ich einen Mittelteil geschaffen, der von einer Mauer umgeben ist, in der die Geister spawnen. Dann wurde jeder Teil des Irrgartens, der nicht untersucht wurde, mit dem Suchalgorithmus für die erste Tiefe erstellt. Nachdem dies geschehen ist, weiß ich, dass es in einem Pacman Labyrinth keine Sackgassen gibt. Was ich getan habe, war jede Zelle zu überprüfen, die Teil des Pfades ist, den Pacman reisen kann. Wenn eine Zelle nur 1 angrenzende Zelle hat, dann ist es eine Sackgasse. Wenn es eine Sackgasse ist, sehen Sie, ob es mit einem anderen Pfad verbunden werden kann. Wenn Sie die Sackgasse nicht als Mauer stellen, überprüfen Sie das Labyrinth erneut auf Sackgassen. Nachdem Sie diese Schritte ausgeführt haben, werden Sie ein zufälliges Labyrinth ohne Sackgassen haben, das dem typischen Pacman-Labyrinth ähnelt.

Answer 3

Ich habe einen zufälligen PacMan Labyrinth Generator vor langer Zeit auf der C = 64 mit der Tiefe zuerst und Eliminierung von Sackgassen erstellt, aber kürzlich von meinem Freund herausgefordert, es wieder zu tun. Einen besseren Weg gefunden. Ich habe ein Raster von Räumen erstellt, wobei jede Richtung eine offene Tür hat (an der Grenze geschlossen, außer dort, wo der Tunnel hinführt), und beginne dann, die Türen zufallsgemäß nach der Regel zu schließen, die es niemals geben sollte mehr als 1 geschlossene Tür in einem angrenzenden Raum, wenn 2 Türen geschlossen sind, würde eine dritte eine Sackgasse bilden. Tun Sie dies immer nur zufällig, bis alle möglichen Türen entweder geschlossen oder offen sind.

Spiegeln war ein bisschen mehr Arbeit, aber ich begann mit den Grundlagen und baute nur die Regeln für die Spiegelung, Geisterhaus Ort, minimale Wandlänge (keine einwandigen Kreisverkehre) und maximale Wandlänge, etc ...