1. Labyrinthe

Dies ist eine alte Version des Dokuments!

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/

Bei „Stages“ siehst du den einfachsten Testlevel und die Informationen, die man erhält.

Aufgabe

Überlege dir, welchen Algorithmus man bei der Testumgebung verwenden könnte? Wie steuert man den Bot zu den Edelsteinen?
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?
Ü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: 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: Breitensuche in Khan-Academy
Erklärung des Dijkstras-Algorithmus Dijkstra Computerphile

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
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()

1. Labyrinthe

2. Pfadfinder-Algorithmen

DokuWiki CSC