Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ss2021:project6:4d_labyrinth [2021/10/14 18:14]
clemens_bandrock
+++ ss2021:project6:4d_labyrinth [2021/10/19 00:16] (aktuell)
clemens_bandrock
@@ Zeile 17: / Zeile 17: @@
 [[ss2021:project1:dokumentation|Protokoll]]
-==== Dokumentation Gruppe 1 ====
+Github: [[https://github.com/kleeblatt007/Labyrinth.git]]
+ZIP: {{:ss2021:project6:labyrinth.zip|}}
+===== Dokumentation Gruppe 1 =====
 ==== Ziele ====
-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.
+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.
 ==== Wie formalisiert man ein Labyrinth ====
@@ Zeile 27: / Zeile 31: @@
-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 0, ansonsten eine 1, zugewiesen. So erhält man ein Feld aus Nullen und Einsen, die man Reihe für Reihe in eine Text-Datei schreibt.
+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.
@@ Zeile 35: / Zeile 38: @@
 Das obenstehende Labyrinth würde also folgendermaßen als Text-Datei dargestellt werden:
-{{:ss2021:project6:bildschirmfoto_2021-10-14_um_17.58.36.png?200|}}
+{{:ss2021:project6:screenshot_1.png|}}
-Diese Darstellung hat den Vorteil, dass man sie leicht an andere Programme übergeben kann. Deswegen benutzen wir sie später auch nochmal.
+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.
@@ Zeile 43: / Zeile 47: @@
-Und zwar als Graph. Ein Graph ist ein Netzwerk aus Knoten, die durch Kanten verbunden sein können. Formal runtergebrochen auf das nötigste
+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.
-Da ein Labyrinth formell runtergebrochen auch nichts anderes als ist, eignet sich diese Struktur...
+Mit diesem runtergebrochenen Konzept kann man gut weiterarbeiten.
-Diese Struktur kann man leicht in Python umsetzen und man kann gut mit ihr weiterarbeiten.
+==== Tiefensuche ===
+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.
+{{ :ss2021:project6:bildschirmfoto_2021-10-14_um_18.42.31.png |}}
+Quelle: Blankertz, Benjamin, Röhr, Vera. „Algorithmen und Datenstrukturen“, 149, o. J.
-=== Aufbau ===
+==== Aufbau ====
 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.
 <code python>
@@ Zeile 65: / Zeile 75: @@
 </code>
 Graph:
 Ist das Grundgerüst, worauf das Labyrinth aufbaut. Sie beinhaltet einen Graphen, wie er schon beschrieben worden ist.
 <code Python>
@@ Zeile 74: / Zeile 85: @@
 </code>
 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.
 <code Python>
@@ Zeile 88: / Zeile 101: @@
 </code>
+==== Aufbau des Labyrinths ====
+=== Grid ===
+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.
+{{:ss2021:project6:bildschirmfoto_2021-10-14_um_18.23.11.png?200|}}
+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.
+{{:ss2021:project6:bildschirmfoto_2021-10-14_um_18.24.18.png?200|}}
+=== Pfadfindung im 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.
+{{:ss2021:project6:bildschirmfoto_2021-10-14_um_18.25.20.png?200|}}
+=== von 2D zu 3D zu 4D ===
+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.
+=== Visualisierung ===
+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.
+{{:ss2021:project6:bildschirmfoto_2021-10-14_um_18.27.06.png?200|}}
+=== Versuche im vierdimensionalen Raum ==
+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.
+{{:ss2021:project6:bildschirmfoto_2021-10-14_um_18.31.58.png?200|}}
+Hier ein Versuch ein 4D-Labyrinth in Matplotlib darzustellen
 ===== Gruppe 2 =====
 ==== Teilnehmer ====

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge