ef:algorithmen:start [DokuWiki CSC]

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
======= 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.

<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 3**  
  - 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.
  - Wie funktioniert A*? Erkläre ihn. Recherchiere nach bekannten Pfadfinder-Algorithmen. [[https://youtu.be/-L-WgKMFuhE?si=I7kuQFjTcYBDQRN7|Sebastian Lague A*]]
  - Eine gute visuelle Darstellung von verschiedenen Algorithmen findet sich z.B. hier: [[https://clementmihailescu.github.io/Pathfinding-Visualizer/#]] 
 
</WRAP>


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>