Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- ef:algorithmen:start [2025/10/30 14:55] – lehmannr
+++ ef:algorithmen:start [2025/11/19 16:27] (aktuell) – lehmannr
@@ Zeile 1: / Zeile 1: @@
-======= 1. Pfadfinder-Algorithmen =======
+======= 1. Labyrinthe =======
+Ein Labyrinth kann man durch einen Graphen darstellen. Ein sogenanntes "perfektes Labyrinth" wird dabei durch einen Baum dargestellt. Allgemeinerer Labyrinthe (die nicht "perfekt" sind), können durch Graphen repräsentiert werden.
-Betrachte die Aufgabe zum Programmierwettbewerb Hidden-Gems: [[https://hiddengems.gymnasiumsteglitz.de/]]
+<WRAP nicebox green>
+** Aufgabe 1 **
+  - Wie funktioniert der Algorithmus Randomized Depth First Search (DFS), um ein Labyrinth zu erstellen? Erkläre.
+  - Wozu benötigt man einen Stack, um den DFS zu implementieren.
+  - Finde zu einem gegebenen Labyrinth den zugehörigen Graphen und umgekehrt (vgl. Arbeitsblatt).
+</WRAP>
+======= 2. Pfadfinder-Algorithmen =======
+Betrachte die Aufgabe zum Programmierwettbewerb Hidden-Gems: [[https://hiddengems.gymnasiumsteglitz.de/]]
 Bei "Stages" siehst du den einfachsten Testlevel und die Informationen, die man erhält.
+Es gibt etliche Algorithmen, welche einen Pfad von einem Startpunkt zum Ziel finden sollen. Diese funktionieren sowohl bei Wegen mit Hindernissen, als auch bei Labyrinthen.
+===== 2.1 Labyrinthe lösen =====
+<WRAP nicebox green>
+**Aufgabe 2**
+  - Wie funktioniert der Random-Mouse Algorithmus?
+  - Wie funktioniert der "Hand on wall"-Algorithmus? Für welche Labyrinthe funktioniert er sicher?
+  - Wie funktioniert der DFS-Algorithmus um den Pfad in einem Labyrinth zu finden? Produziert er den kürzesten Weg?
+  - Wie funktioniert der BFS-Algorithmus um den Pfad in einem Labyrinth zu finden? Produziert er den kürzesten Weg?
+</WRAP>
+===== 2.2 Andere Pfad-Finder-Algorithmen =====
 <WRAP nicebox green>
-** Aufgabe **
+** Aufgabe 3**
-  - Überlege dir, welchen Algorithmus man bei der Testumgebung verwenden könnte? Wie steuert man den Bot zu den Edelsteinen?
+  - Wie funktioniert der Dijkstra-Algorithmus, um den schnellsten Weg zu finden? Funktioniert er für gerichtete und ungerichtete Graphen? Funktioniert er für gewichtete Graphen? [[https://www.youtube.com/watch?v=GazC3A4OQTE|Dijkstra Computerphile]]. Führe den Dijkstra-Algorithmus durch für das Beispiel in OneNote.
-  - Was ändert sich, wenn man sich in einer Umgebung mit Wänden bewegt? Wie wird die Umgebung, die Position des Bots und der Edelsteine repräsentiert?
+  - Wie funktioniert A*? Erkläre ihn. Recherchiere nach bekannten Pfadfinder-Algorithmen. [[https://youtu.be/-L-WgKMFuhE?si=I7kuQFjTcYBDQRN7|Sebastian Lague A*]]
-  - Überlege dir einen möglichen Algorithmus, der auch bei Wänden funktionieren könnte. Schreibe den exakten Ablauf deines Algorithmus schriftlich hin.
-  - Recherchiere nach bekannten Pfadfinder-Algorithmen. Was ist die Manhatten-Distanz? (BFS, DFS, Dijkstra, A*)(Bsp: [[https://www.youtube.com/watch?v=9W8hNdEUFbc|Englisches Video mit Visualisierung]])
   - Eine gute visuelle Darstellung von verschiedenen Algorithmen findet sich z.B. hier: [[https://clementmihailescu.github.io/Pathfinding-Visualizer/#]]
-  - Erklärung zur Breitensuche: [[https://de.khanacademy.org/computing/computer-science/algorithms/breadth-first-search/a/the-breadth-first-search-algorithm|Breitensuche in Khan-Academy]]
-  - Erklärung des Dijkstras-Algorithmus [[https://www.youtube.com/watch?v=GazC3A4OQTE|Dijkstra Computerphile]]
 </WRAP>
-  - Wie funktioniert die Breitensuche?
-  - Was ist eine Queue und wie verwendet man sie, wenn man die Breitensuche implementiert? (Siehe Link von Khan-Academy)
+main.py
+<sxh>
+# main.py
+import tkinter as tk
+from cell import Cell
+root = tk.Tk()
+root.title("Labyrinth")
+cols = 30
+rows = 30
+size = 40
+currentCell = None
+canvas = None
+cells = [] # Array mit allen Zellen
+stack = [] # stack für das Backtracking
+def remove_wall(cell1, wall):
+    x = cell1.x
+    y = cell1.y
+    cell1.walls[wall] = False
+    if (wall==0):
+        cells[get_index(x,y-1)].walls[2] = False
+    if (wall==1):
+        cells[get_index(x+1,y)].walls[3] = False
+    if (wall==2):
+        cells[get_index(x,y+1)].walls[0] = False
+    if (wall==3):
+        cells[get_index(x-1,y)].walls[1] = False
+# cells are stored in 1 dimensional array, getting indes of cell at position (i,j)
+def get_index(i,j):
+    return j*rows+i
+# Beispiel: mehrere Zellen
+def setup():
+    global canvas, cells, currentCell
+    canvas = tk.Canvas(root, width=cols*size+10, height=rows*size+10, bg="white")
+    canvas.pack()
+    for j in range(rows):
+        for i in range(cols):
+            cells.append(Cell(i, j, size, col="lightblue"))
+    currentCell = cells[0]
+def draw_maze():
+    global currentCell
+    canvas.delete("all")  # alte Zeichnungen entfernen
+    currentCell.visited = True
+    for c in cells:
+        c.draw(canvas)
+    nextCell = currentCell.checkNeighbors(cells, rows, cols)
+    if nextCell:
+        nextCell.visited = True
+        stack.append(nextCell)
+        dx = nextCell.x - currentCell.x
+        dy = nextCell.y - currentCell.y
+        if dx == 1: # nach rechts
+            remove_wall(currentCell,1)
+        if dx ==-1: # nach links
+            remove_wall(currentCell,3)
+        if dy == 1: # nach unten
+            remove_wall(currentCell,2)
+        if dy == -1: # nach oben
+            remove_wall(currentCell,0)
+        currentCell = nextCell
+    else:
+        if stack:
+            currentCell=stack.pop()
+            for i, c in enumerate(stack): # durch enumerate erhält man den index und das Element
+                intensity = int(200/len(stack)*i)
+                col = f"#{intensity:02X}FF{intensity:02X}"
+                c.highlight(canvas, col)
+    currentCell.highlight(canvas, "lightcoral")
+    root.after(100, draw_maze)
+setup()
+draw_maze()
+root.mainloop()
+</sxh>
+cell.py
+<sxh>
+import random
+class Cell:
+    def __init__(self, x, y, size, col="white"):
+        self.x = x                # X-Koordinate
+        self.y = y                # Y-Koordinate
+        self.size = size          # Breite/Höhe der Zelle
+        self.walls = [True, True, True, True]  # [oben, rechts, unten, links]
+        self.col = col            # Farbe der Zelle
+        self.visited = False      # Besuchsstatus
+    def highlight(self, can, col):
+        x1 = self.x * self.size+8
+        y1 = self.y * self.size+8
+        x2 = x1 + self.size-10
+        y2 = y1 + self.size-10
+        can.create_rectangle(x1, y1, x2, y2, fill=col, outline="")
+    def draw(self, can): # Zeichnet die Zelle auf dem übergebenen Canvas.
+        x1 = self.x * self.size+4  # +4, damit der linke bzw. obere Rand nicht abgeschnitten werden
+        y1 = self.y * self.size+4
+        x2 = x1 + self.size+4
+        y2 = y1 + self.size+4
+        # Hintergrundfarbe
+        if self.visited:
+            can.create_rectangle(x1, y1, x2, y2, fill=self.col, outline="")
+        else:
+            can.create_rectangle(x1, y1, x2, y2, fill="lightyellow", outline="")
+        # Wände zeichnen
+        if (self.walls[0]):  # oben
+            can.create_line(x1, y1, x2, y1, fill="black", width=4)
+        if self.walls[1]:  # rechts
+            can.create_line(x2, y1, x2, y2, fill="black", width=4)
+        if self.walls[2]:  # unten
+            can.create_line(x2, y2, x1, y2, fill="black", width=4)
+        if self.walls[3]:  # links
+            can.create_line(x1, y2, x1, y1, fill="black", width=4)
+    def checkNeighbors(self, cells, rows, cols):
+        neighbors = []
+        topIndex = Cell.get_index(self.x, self.y-1, rows, cols)
+        rightIndex = Cell.get_index(self.x+1, self.y, rows, cols)
+        bottomIndex = Cell.get_index(self.x, self.y+1, rows, cols)
+        leftIndex = Cell.get_index(self.x-1, self.y, rows, cols)
+        #top = cells[Cell.get_index(self.x, self.y-1, rows, cols)]
+        #right = cells[Cell.get_index(self.x+1, self.y, rows, cols)]
+        #bottom = cells[Cell.get_index(self.x, self.y+1, rows, cols)]
+        #left = cells[Cell.get_index(self.x-1, self.y, rows, cols)]
+        if (topIndex and (not cells[topIndex].visited)):
+            neighbors.append(cells[topIndex])
+        if (rightIndex and (not cells[rightIndex].visited)):
+            neighbors.append(cells[rightIndex])
+        if (bottomIndex and (not cells[bottomIndex].visited)):
+            neighbors.append(cells[bottomIndex])
+        if (leftIndex and (not cells[leftIndex].visited)):
+            neighbors.append(cells[leftIndex])
+        if neighbors:
+            return random.choice(neighbors)
+        else:
+            return None
+    @classmethod
+    def get_index(cls, i, j, rows, cols):
+        if (i<0 or j<0 or i>=cols or j >= rows):
+            return None
+        else:
+            return j*rows + i
+</sxh>