Jonna, Jana, Majola, Jakob, Clemens

Besonderes Dankeschön an Mustafa und Peter

Jakob, Clemens

Protokoll

Github: https://github.com/kleeblatt007/Labyrinth.git

ZIP: labyrinth.zip

Unser Ziel war es, ein 4D-Labyrinth in Python zu programmieren. Dann wollten wir einen Weg finden, dieses darzustellen und durch einen Spieler erforschen zu lassen. Zuletzt wollten wir einen Algorithmus schreiben, der das Labyrinth löst.

Zuerst überlegten wir, wie man ein Labyrinth digital speichern kann. Zur Vereinfachung haben wir festgelegt, dass ein Labyrinth ein Quadrat bzw. Quader (2D bzw. 3D) bestehend aus kleineren Quadraten bzw. Quadern (sogenannten Zellen) ist. Eine Zelle kann passierbar oder unpassierbar sein, es gibt eine Start- und eine Zielzelle, die durch einen Weg aus passierbaren Zellen verbunden sind. Man darf sich nur über die Kanten der Zellen bewegen (darf also nicht diagonal laufen).

Also haben wir angefangen ein zwei-dimensionales Labyrinth darzustellen. Der einfachste Weg war dafür als Text-Datei. Zellen die passierbar sind, bekommen den Wert Null, ansonsten eine Eins, zugewiesen. So erhält man ein Feld aus Nullen und Einsen, die man Reihe für Reihe in eine Text-Datei schreibt.

Das obenstehende Labyrinth würde also folgendermaßen als Text-Datei dargestellt werden:

Diese Darstellung hat den Vorteil, dass man sie leicht an andere Programme übergeben kann. Auch ist sie für einen Menschen auf den ersten Blick noch halbwegs verständlich. Deswegen benutzen wir sie später auch nochmal.

Für den drei-dimensionalen Fall wird es aber kompliziert, da im Text-Editor keine dritte Dimension vorhanden ist. Dies kann man lösen, es wird aber nicht leichter und wir hatten noch eine andere Idee.

Und zwar als Graph. Ein Graph ist ein Netzwerk aus Knoten, die durch Kanten verbunden sein können. Wenn man die räumliche Komponente eines Labyrinths weglässt, ist dieses auch nichts anderes als viele ortlose Punkte, die teilweise untereinander verbunden sind.

Mit diesem runtergebrochenen Konzept kann man gut weiterarbeiten.

dem alle Knoten miteinander verbunden sind und dafür so wenige Kanten wie möglich verwendet werden. Die Tiefensuche läuft dabei wie im folgenden Bild ab: Es wird ein Start-Knoten ausgewählt (bei uns Knoten 0), der markiert wird. Von dort schauen wir uns alle Knoten an, die über eine Kante mit diesem verbunden sind und wählen einen nächsten Knoten aus, der noch nicht markiert ist. Die Kante über die wir diesen Knoten erreichen, speichern wir dabei ab. Der nächste Knoten wird nun markiert und das Spiel startet von vorne. Das geht so lange weiter, bis wir bei einem Knoten angekommen sind, der mit keinem weiteren unmarkierten Knoten verbunden ist. Ab dann gehen wir wieder einen Schritt zurück und schauen ob wir von dort zu einem weiteren unmarkierten Knoten kommen. Am Ende sind keine unmarkierten Knoten mehr über, die wir erreichen können. Jetzt haben wir unser minimales Netz.

Quelle: Blankertz, Benjamin, Röhr, Vera. „Algorithmen und Datenstrukturen“, 149, o. J.

Unser Programm besteht aus grundlegend aus vier Klassen:

Labyrinth:

Stellt die Hauptklasse. Besitzt ein Graphen und stellt alle Funktionen, die rund um das Labyrinth wichtig sind. Jede Dimension hat seine eigene Klasse, die leicht abweicht.

class Labyrinth(object):
   def __init__(self, N, start):
        self.N = N
        self.graph = Graph(pow(N, 2))
        self.start = start
        self.build()

Graph:

Ist das Grundgerüst, worauf das Labyrinth aufbaut. Sie beinhaltet einen Graphen, wie er schon beschrieben worden ist.

class Graph(object):
    def __init__(self, nodes):
        self.nodes = int(nodes)
        self.edges = 0
        self.adj = [[]for x in range(nodes)]

DepthFirstPath und RandomPath:

Sind zwei unterschiedliche Klassen, funktionieren aber grundlegend gleich. Sie erstellen auf einem Graphen über die Tiefensuche einen Pfad, der alle Knoten des Graphen miteinander verknüpfen. Einmal systematisch und einmal randomisiert.

Coordinaten:

Dient nur zum abspeichern der Koordinaten der Knoten.

class Coordinate(object):
    def __init__(self, x, y, z = 0, w = 0):
        self.x = x
        self.y = y
        self.z = z
        self.w = w

Die Grundlage für unser Labyrinth stellt ein Grid dar. Wie im Bild zu sehen, ist dabei im zweidimensionalen Raum jeder Knoten mit einem Knoten rechts, links, über und unter ihm verbunden. Die einzigen Ausnahmen stellen die äußeren Kanten dar, diese haben ein bzw. zwei Kanten weniger. Das Grid wird direkt in der Labyrinth-Klasse erstellt.

Wir erstellen nun unser Labyrinth, indem wir ein Grid bauen und darauf eine randomisierte Tiefensuche laufen lassen. So bekommen wir ein Labyrinth, was garantiert lösbar ist, da jeder Knoten mit jedem verbunden ist und gleichzeitig zyklenfrei ist, was nachher für die Pfadfindung wichtig wird. Gleichzeitig bekommen wir mit jedem neuen Aufbau ein neues random erstelltes Labyrinth.

Unseren Pfad finden wir im Grunde, genau so, wie wir auch unser Labyrinth aufbauen. Wir gehen unser Labyrinth diesmal mit einer systematischen Tiefensuche durch und merken uns bei jedem Knoten den Vorgänger, über welchen wir den Knoten erreicht haben. So ist es uns dann möglich rückwärts vom End-Knoten zum Startknoten zu gehen und dabei den kürzesten Weg zu bestimmen.

Dadurch, dass wir unser Labyrinth auf einen Graphen aufbauen, ist es kein Problem in höhere Dimensionen zu gehen. Die Knoten und Kanten haben von sich aus ja erst einmal keine Lage im Raum. Mit steigender Dimension bekommen nur die Knoten im Grid mehr Nachbarn, mit denen sie verknüpft werden müssen, was den Aufbau des Grid etwas erschwert. Ansonsten sind wir nicht in der Dimension beschränkt.

Um das ganze graphisch darstellen zu können, haben wir Matplotlib benutzt. Dafür mussten wir bloß für unsere Knoten die Koordinaten bestimmen. Da die Knoten durchnummeriert sind, konnten wir die Koordinaten im zweidimensionalen Raum einfach ausrechnen. Für den drei- und vierdimensionalen Raum sind wir nicht so schnell auf eine Formel gekommen und haben so beim erstellen des Grids, wo wir uns ja sowieso jeden Knoten anschauen, gleich noch die Koordinaten mit abgespeichert. So konnten wir unsere Labyrinthe sehr einfach Plotten lassen.

Wie beschrieben, sind wir durch die Struktur des Labyrinths als Graphen prinzipiell erstmal an keine Dimension gebunden. Die Dimension ändert erstmal nur, wie sich das Grid am Anfang des Algorithmus' aufbaut, wie die Knoten also untereinander verbunden sind. Doch auch für vier Dimension kann man einfach den Gesetzmäßigkeiten der Dimensionen davor folgen und so ein Netzwerk konstruieren, dass auf dem Papier vier Dimensionen hat.
Die Tiefensuche zum Generieren des Labyrinths bzw. Finden des richtigen Wegs bleibt auch unberührt, da sie ja sowieso die räumliche Komponente nicht braucht und davon komplett unabhängig ist.

Im Programm existiert also ein vier-dimensionales Labyrinth, dass man sich theoretisch Knoten für Knoten ausgeben könnte; auch den Weg durch dieses zu finden, ist möglich. Doch dieses vier-dimensionale Konstrukt in unserem drei-dimensionalen Raum bzw. auf unseren zwei-dimensionalen Bildschirmen darzustellen, war für uns nicht möglich. Verschiedene Ansätze die vierte Achse darzustellen, ob als Einfärbung der Knoten oder zeitliche Änderung, waren nicht zufriedenstellend. Dies blieb bis zum Schluss unser letztes Problem.

Hier ein Versuch ein 4D-Labyrinth in Matplotlib darzustellen

Jonna, Majola, Jana

Hier ist unser wöchentliches Protokoll, sowie die zip-Datei mit unserem finalen Ergebnis zu finden:

Protokoll

Um das ganze Labyrinth auch ein wenig interaktiver zu gestalten, haben wir uns in unserer Gruppe überlegt, dass wir ein 4D-Labyrinth erstellen wollen, in dem man sich bewegen kann und das Ziel findenn kann. Unser Plan war es, zunächst ein 2D-Labyrinth zu erstellen und uns dann über 3D zu 4D hinzuarbeiten. Hierfür entschieden wir uns mit Pygame zu arbeiten, eine Python Bibliothek, die es ermöglicht 2D Spiele zu programmieren.

Unser Projekt kann in verschiedene Bereiche eingeteilt werden. Zunächst muss man sich mit Pygame an sich auseinandersetzen, dann muss der Spieler erstellt und zuletzt das Labyrinth generiert werden.

Pygame ist eine Programmbibliothek von Python, mit deren Hilfe man (vor allem 2D) Spiele programmieren kann. Die Bestandteile des Spiels, wie der Bildschirm, der Spieler, die Bewegung des Spielers, Hindernisse, etc. können dabei im Vorfeld eingestellt werden.

Ein wichtiger Teil des Spiels ist selbstverständlich die Spielfigur, die von dem Spieler vor dem Computer gesteuert wird. In unserem Fall ist sie ein gelbes Rechteck, bzw. Quadrat, das sich im Rahmen des Bildschirms bewegen kann und durch die Pfeiltasten gesteuert wird. Dadurch, dass der Spieler als Rechteck dargestellt wird, kann durch die Funktion „collide.rect“ vermieden werden, dass der Spieler später im Labyrinth durch die Wände laufen kann. Stattdessen kollidiert der Spieler nämlich mit den Wänden, welche ebenfalls aus Rechtecken bestehen.

#Klasse für den spieler
class Spieler(object):
 
    def __init__(self):
        self.rect = pygame.Rect(16, 16, 16, 16)    #SpielerRechteck wird erzeugt
 
    def move(self, dx, dy):
 
        if dx != 0:
            self.move_single_axis(dx, 0) #Spielerrechteck wird in dx Richtung bewegt
        if dy != 0:
            self.move_single_axis(0, dy)
 
    def move_single_axis(self, dx, dy):
 
        self.rect.x += dx
        self.rect.y += dy
 
        #Wandkollisionen abchecken
        for wall in walls:
            if self.rect.colliderect(wall.rect):
                if dx > 0: #Bewegung nach rechts, linke Seite der Wand
                    self.rect.right = wall.rect.left
                if dx < 0: #Bewegung nach links, linke Seite der Wand
                    self.rect.left = wall.rect.right
                if dy > 0: #Bewegung nach untem, obere Seite der Wand
                    self.rect.bottom = wall.rect.top
                if dy < 0: #Bewegung nach oben, untere Seite der Wand
                    self.rect.top = wall.rect.bottom

Das Wichtigste bei einem Labyrinth sind natürlich die Wände, die es schwierig machen, den korrekten Ausgang zu finden. Auch für die Wände haben wir eine Klasse erstellt. Sie enthält die Funktion init, die die Wände auf dem Bilschirm anzeigen lässt und zwei weitere Funktionen, die zum Erscheinen des Endbildschirmes dienen.

#Klasse für Wände
class Wall(object):
    def __init__(self, pos):
        walls.append(self)
        self.rect = pygame.Rect(pos[0], pos[1], 16, 16)
        self.screen = pygame.display.set_mode((r*32,r*32+16)) #r ist die Größe des Labyrinths
 
    def draw_text(self, words, screen, pos, size, colour, font_name, centered = False):
        screen = pygame.display.set_mode((r*32,r*32+16))
        font = pygame.font.SysFont(font_name, size)
        text = font.render(words, False, colour)
        text_size = text.get_size()
        if centered:
            pos[0] = pos[0]-text_size[0]//2
            pos[1] = pos[1]-text_size[1]//2
        screen.blit(text, pos)
 
 
    def endbildschirm(self):
        screen = pygame.display.set_mode((r*32,r*32+16))
        self.screen.fill((0,0,0))
        self.draw_text('You win!', self.screen, [
                       (r*32)/2, ((r*32+16)/2)-50], r*5, (170, 132, 58), 'Britannic Bold', centered=True)
        for e in pygame.event.get(): #alles was der Nutzer macht
            if e.type == pygame.QUIT:
                pygame.quit()
        pygame.display.update()    

Damit diese bei jedem Spiel neu generiert werden, das Labyrinth aber auch immer lösbar ist, haben wir das Material der Gruppe 1 benutzt. Gruppe 1 hatte eine Klasse „Labyrinth“ erstellt, die ein zufälliges Labyrinth erstellt und sowohl als Graph als auch als Textdatei („Lab.txt“) ausgibt. Bei der Textdatei stellt eine „0“ eine Wand und eine „1“ den Weg dar. In unserem Spiel haben wir die Wände dann als weiße Rechtecke dargestellt, mit den der Spieler bei Berührung kollidiert.

#Levellayout als Textdatei
with open('Lab.txt', 'r') as file:
    level = file.readlines()
 
#0 als Wand definieren und 2 als Ausgang
x = y = 0
for row in level:
    for col in row: #einzelnen Einträge in der Reihe werden nach und nach überprüft
        if col == "0":
            Wall((x, y)) #es wird auf Wall Klasse zugegriffen
        if col == "2":
            end_rect = pygame.Rect(x, y, 16, 16)
        x += 16 #immer 16, da ein Buchstabe 16 Pixel entspricht
    y += 16
    x = 0

Eine besondere Rolle spielt der Endblock, den der Spieler erreichen muss. Dieser ist in der Textdatei als „2“ dargestellt. Kollidiert der Spieler mit dem Endblock, wird der Endbildschirm angezeigt und das Spiel ist beendet.

#Spiel beenden durch berühren des Endblocks
if spieler.rect.colliderect(end_rect):
     state = False
 
while not state:
     wall.endbildschirm()
     running = False
     for e in pygame.event.get(): #alles was der Nutzer macht
         if e.type == pygame.QUIT:
             running = False
pygame.quit()             

Nachdem wir uns überlegt hatten mit einem 2D Labyrinth zu starten, haben wir uns darüber informiert, wie man mit Pygame arbeiten kann. Unter Anderem durch Internetseiten und Erklärvideos auf Youtube.

Zunächst einmal haben wir einen „Spieler“ erstellt auf einem Screen, den man mit den Pfeiltasten bewegen konnte. Um dafür zu sorgen, dass der Spieler nicht den Screen verlassen kann, erstellten wir um den screen herum Rechtecke. Wenn der Spieler mit denen kollidiert, bewegt er sich nicht weiter.

Bevor wir uns daran wagten, ein Labyrinth automatisch zu generieren, haben wir zunächst manuell eines erstellt. Eine Herausforderung war es, die Wände in dem Labyrinth undurchdringbar für den Spieler zu machen. Schlussendlich konnten wir die Wände dadurch generieren, dass wir einen string erstellt haben, aus „W“ und Leerzeichen und die W’s wurden ausgelesen und „umgewandelt“ in weiße Rechtecke, bei denen der Spieler stoppt, wenn er mit denen kollidiert.

Durch Erstellen eines Start- und Endbildschirms, wollten wir erreichen, dass sich unser (mittlerweile bezeichnet als) „2D-Labyrinth-Spaß“ sich noch mehr anfühlt, wie ein Spiel.

Zuletzt konnten wir unser Labyrinth verbinden, mit dem woran die letzte Gruppe gearbeitet hat, indem eine zufällig erstellte Text-Datei aus 0 und 1 ausgelesen werden konnte und in ein 2D-Labyrinth umgewandelt werden konnte.

Das Erstellen des 2D Labyrinths nahm doch mehr Zeit in Anspruch als wir zunächst eingeplant haben. Auch der Übergang von 2D zu 3D ist bei einem interaktiven Labyrinth ein bisschen schwieriger, da wir uns dafür nochmal mit einer anderen Python Bibliothek als Pygame hätten auseinandersetzen müssen. Für unser erstes Programmierprojekt sind wir mit dem Ergebnis, das wir haben aber ganz zufrieden und freuen uns, dass wir unsere Ausarbeitung, mit der von Gruppe 1 verknüpfen konnten. In Zukunft hatten wir noch ein paar Ideen, wie man den 2D-Modus noch spannender gestalten könnte. Wie zum Beispiel einen Mehrspielermodus oder einem Wettrennen mit einem Algorithmus. Und natürlich auch noch der Ausbau zu einem 3D und 4D Labyrinth wäre noch auf der To Do - Liste gewesen (Auch wenn wir uns immer noch nicht so sicher sind, wie ein 4D-Labyrinth aussieht)