lehrkraefte:blc:informatik:glf25:labyrinthe:labyrinth-generieren [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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.

<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>