Ich versuche, den Algorithmus der ersten Tiefensuche in mein Spiel zu implementieren. Ich habe diese Webseite studiert: http://www.mazeworks.com/mazegen/mazetut/index.htm , nur um festzustellen, dass ich sie nicht mit Blöcken anstelle von Wänden verwenden kann. Was ich mit Blöcken meine, ist ein Quadrat, das die gesamte Zelle abdeckt, anstatt nur die Ränder. Ich dachte, es wäre einfacher, es auf diese Weise zu tun, aber jetzt bin ich mir nicht mehr so sicher. Hat das schon jemand gemacht? Wenn ja, wie? (Psuedocode ist in Ordnung). Oder sollte ich einfach mit den Wänden Methode gehen, wenn es einfacher ist?
Antwort
Zu viele Anzeigen?
Je nachdem, was Sie eigentlich erreichen wollen, habe ich zwei Lösungen für Sie. Beide sind im Grunde der Algorithmus, der auf der von Ihnen genannten Website vorgestellt wird.
1.) Es gibt Blöcke an vordefinierten Positionen in deinem Labyrinth
- führen Sie den Algorithmus auf einer
2*k+1Gitter - Gehen Sie davon aus, dass die Nummerierung Ihrer Zellen oben links mit (0,0) beginnt. Markieren Sie alle Zellen mit 2 ungeraden Koordinaten (
(2*p+1, 2*q+1); p,q < k) als Blöcke. - Sie führen den geänderten Algorithmus aus Ihrer Quelle auf den verbleibenden Zellen ("gerade Zellen") aus. die Änderungen sind:
- mit einer zufällig ausgewählten geraden Zelle beginnen
- eine "Nachbarzelle" ist die übernächste Zelle in einer beliebigen Gitterrichtung; d.h. man 'springt' über einen Ziegelstein.
- anstatt die Mauer zwischen den Zellen niederzureißen, verwandeln Sie den Block in eine zugängliche Zelle. Diese Zelle wird jedoch bei der Auswahl nicht berücksichtigt. und Rückverfolgung
2.) Anstelle von Wänden, die die Zellen voneinander trennen, sollten Sie Blöcke verwenden.
vor dem Start des Algorithmus eine beliebige Anzahl von Zellen als Blöcke markieren. Gehen Sie wie in Ihrem Quelltext beschrieben vor, aber berücksichtigen Sie niemals eine der Blockzellen. Sie müssen besondere Vorsichtsmaßnahmen ergreifen, wenn Sie Folgendes garantieren wollen Sie müssen besondere Vorkehrungen treffen, wenn Sie die vollständige Zugänglichkeit in Ihrem Labyrinth gewährleisten wollen. als Block zu markieren, die mehr als 1 Block als Nachbarn hat.
Ich hoffe, diese Ideen entsprechen Ihren Bedürfnissen,
mit freundlichen Grüßen, carsten
