Labyrinthe

• Intro, Wegfindungsalgorithmen als Pseudocode
• Klassen Laby und Zelle
• Wegfindungsalgorithmen
• Wegfindung mit Todo-Liste
• Tiefensuche, Breitensuche, Zufallssuche Handhabung der Todo-Liste
• Labyrinthe generieren
• Bilder einlesen
• Modularisierung von Verteilen des Codes auf mehrere Dateien.

Der Begriff «Labyrinth» bezieht sich im folgenden immer auf rechteckiges Raster aus quadratischen Zellen, die mit einem beliebigen Symbol markiert sein können und von denen es bis zu vier Nachbarn (rechts, unten, links, oben) geben kann, wobei dazwischen jeweils eine Mauer vorhanden ist, oder eben nicht.

Gegeben ist folgener Pseudo-Code

Gegeben: ein Labyrinth und eine Startzelle. Alle Zellen unmarkiert.
 
Markiere Startzelle mit 'S'
Neue Todo-Liste mit Startzelle als einzigen Eintrag.
So lange Todo-Liste nicht leer:
    Entferne die letzte Zelle aus der Todo-Liste, nenne diese «aktuell».
    Wenn es eine unmarkierte Nachbarszelle gibt, keine Mauer dazwischen:
        Markiere Nachbarszelle mit '.'
        Füge die «aktuelle» Zelle der Todo-Liste hinzu
        Füge die Nachbarszelle der Todo-Liste hinzu

• Erklären Sie, warum jede direkte Nachbarszelle (ohne Mauer dazwischen) von 'S' besucht wird.
• Erklären Sie, warum jede von 'S' aus erreichbare Zelle auch besucht und markiert wird.
• Erklären Sie, warum die Todo-Liste immer einen direkten Weg von 'S' zur Aktuellen Zelle enthält.
• Welche Zelle wird zuallerletzt aus der Todo-Liste entfernt (bevor diese dann definitiv leer ist und die Wiederholung abgebrochen wird).

Gegeben ist folgener Pseudo-Code

Gegeben: Breite und Höhe des zu generierenden Labyrinths
 
Erzeuge ein neues Labyrinth mit gegebener Grösse, alle Mauern geschlossen, alle Zellen unmarkiert.
Sei die Startzelle die Zelle oben links.
Markiere Startzelle mit 'S'
Neue Todo-Liste mit Startzelle als einzigen Eintrag.
So lange Todo-Liste nicht leer:
    Entferne die letzte Zelle aus der Todo-Liste, nenne diese «aktuell».
    Wenn es eine unmarkierte Nachbarszelle mit einer Mauer dazwischen gibt, wähle diese zufällig aus allen möglichen aus:
        Entferne die Mauer zwischen «aktuell» und der Nachbarszelle
        Markiere Nachbarszelle mit '.'
        Füge die «aktuelle» Zelle der Todo-Liste hinzu
        Füge die Nachbarszelle der Todo-Liste hinzu

• Erklären Sie, warum es danach zu sämtlichen Zellen einen Weg von der Startzelle aus gibt.
• Erklären Sie, warum es nie zwei unterschiedliche Wege von der Startzelle aus zu einer Zelle gibt.
• Erklären Sie, warum es zwischen zwei beliebigen Zellen exakt einen Weg gibt (und nicht zwei oder null).
• Erklären Sie, warum der obige Algorithmus relativ lange Gänge ohne Kreuzungen erzeugt.
  • Wie könnte der Algorithmus abgeändert werden, dass «etwas mehr Kreuzungen» erzeugt werden?