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.

1. Wie funktioniert die Breitensuche?
2. Was ist eine Queue und wie verwendet man sie, wenn man die Breitensuche implementiert? (Siehe Link von Khan-Academy)

main.py

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

cell.py

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