Programmierprojekt: Labyrinthe mit Bildern erzeugen

Der Fokus liegt darauf, die einzelnen Schritte im Detail zu verstehen. Gerade für das einlesen und bearbeiten von Bildern gibt es jede Menge an fertigen Bibliotheken (libraries). Selbstverständlich sollten für ein Softwareprodukt diese Bibliotheken verwendet werden. Wir werden aber so weit möglich, alles selber schreiben, aber externe Software für die Konvertierung und Anzeige von Bildern verwenden.

• Programmiersprache: Python.
• Verwendete Libraries: So wenige wie möglich.
• Externe Programme: VSCode, Gimp, Browser (evtl. Inkscape).

• Einheit 1: Pixelbilder im pnm-Format erstellen und mit Python einlesen

Das ist die zentrale Klasse, die alle nötigen Funktionen bereitstellt:

• Einheit 2: Erste Aufgaben mit der Labyrinth Klasse

Wegfindungs-Algorithmen sind ganz zentral für die Erzeugung von Labyrinthen. Diese Einheit soll damit vertraut machen.

• Einheit 3: Einfachere Wegfindungs-Algorithmen
• Einheit 4: Komplette Wegfindungs-Algorithmen

Ziel ist es, einen Weg zu erhalten, der möglichst alle Zellen besucht, die schwarzen Pixeln entsprechen.

Die Grundidee ist folgende:

• Man sucht zwei aufeinanderfolgende Zellen im Weg, so dass die beiden Zellen daneben schwarz, aber nicht auf dem Weg sind (z.B. Zellen a und b, oder c und d im folgendend Bild):

+---+---+---+---+---+---+   +
|   |   |   |   |   | d   # |
+---+---+---+---+---+   +---+
|   |   | a   b |   | c |   |
+---+---+   +   +---+   +---+

• Die Wand zwischen a,b wird dann gesetzt, und der Weg über die zwei benachbarten Zellen x, y umgeleitet:

+---+---+---+---+---+---+   +
|   |   | x   y |   | d   # |
+---+---+   +   +---+   +---+
|   |   | a | b |   | c |   |
+---+---+   +   +---+   +---+

• Das wiederholt man so lange, wie das möglich ist. Die Zellen werden zufällig ausgewählt, damit keine «geraden Korridore» entstehen.
• Damit man nicht alle 4 Fälle programmieren muss, wird mit Operationen auf der Richtung (wie ein Winkel) gearbeitet.
  • ist dir die Richtung, sind (dir+1)%4 und (dir+3)%4 die dazu rechtwinkligen Richtungen.
  • Die Klasse Zelle hat eine Methode dirTo(other), die die Richtung zu einer anderen Zelle berechnet.