Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:glf25:labyrinthe:labyrinth-generieren [2026/02/21 13:20] – created Ivo Blöchliger
+++ lehrkraefte:blc:informatik:glf25:labyrinthe:labyrinth-generieren [2026/03/15 15:10] (current) – Ivo Blöchliger
@@ Line 5: / Line 5: @@
   * 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.
+<WRAP todo>
+Laden Sie folgende Python-Datei in Ihr Labyrinthverzeichnis:
+<code python 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
+</code>
+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.
+</WRAP>
+===== 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.
+<WRAP todo>
+  * 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:''
+</WRAP>