Grundidee
Die Grundidee ist die Gleiche wie bei der Wegfindung mit Liste, mit folgenden Unterschieden:
- Die vier möglichen Richtungen werden jedes mal in anderer, zufälliger Reihenfolge abgearbeitet.
- Ist ein Nachbar unbesucht, wird die Mauer dorthin entfernt.
- Die Reihenfolge in der Todo-Liste wird hin und wieder zufällig «verwürfelt», sonst aber wie bei der Tiefensuche gehandhabt. Bei seltenem verwürfeln gibt es längere Wege und weniger Kreuzungen, bei häufigem Verwürfeln gibt es mehr kurze und damit offensichtliche Sackgassen.
Laden Sie folgende Python-Datei in Ihr Labyrinthverzeichnis:
- generator.py
from laby import Laby from zelle import Zelle import time from random import shuffle, randrange lab = Laby(8,5) # Neues Labyrinth mit allen Mauern zu # Todo-Liste enthält die Startzelle todo = [ lab[0,0] ] lab[0,0].mark = '.' # Startzell als besucht markieren # Liste mit allen Richtungen (wird dann verwürfelt) richtungen = [0, 1, 2, 3] # Solange die Todo-Liste nicht leer ist, wiederhole: while len(todo)>0: # Entferne eine Zelle aus der Todo-Liste, nenne diese «aktuell» aktuell = todo.pop() # Letzten Eintrag entfernen # Für alle Richtungen $d$ in zufälliger Reihenfolge shuffle(richtungen) for d in richtungen: # Ist Mauer in diese Richtung zu? # Gibt es in diese Richtung eine Nachbarszelle? # Ist diese noch nicht markiert? # Markieren, Mauer öffnen, aktuell und nachbar der todo-Liste hinuzfügen. # Schlaufe abbrechen pass
Versuchen Sie den Pseudo-Code in Python zu übersetzen. Konsultieren Sie dazu auch Ihre Python-Programme mit der Wegfindung mit Todo-Liste, bzw. Tiefen- und Breitensuche.
Verbesserungen der «Labyrinth-Qualität»
Mit der Tiefensuche werden sehr lange «Schläuche» (mit wenig Kreuzungen) produziert. Das liegt daran, dass halt so weit wie möglich weiter gegangen wird.
- Verwürfeln Sie nun auch die todo-Liste, damit mehr Kreuzungen eingebaut werden.
- Zu viele Kreuzungen? Verwürfeln Sie die todo-Liste z.B. nur jedes 10. Mal, mit
if randrange(10)==0: