from zelle import Zelle
from laby import Laby
from startzielpaar import startzielpaar
from random import shuffle


def wegAufBild(laby:Laby) -> list[Zelle]:
    """
    Generiert eine Liste mit Zellen eines Weges, der nur schwarze Pixel benutzt
    und zwei möglichst weit voneinander entfernte Randzellen verbindet.
    """
    paar = startzielpaar(laby)
    dirs = [0,1,2,3]
    todo = [paar[0]]     # todo-Liste, start beim ersten Element vom Paar
    paar[0].mark = "S"   # Startzelle markieren
    while len(todo)>0:   # So lange, wie es noch Elemente in der Todo-Liste hat
        aktuell = todo.pop()  # Letztes Element entfernen
        shuffle(dirs)
        for dir in dirs:
            nb = aktuell.nachbar(dir)
            if nb!=None and nb.mark==" " and nb.bild==0:
                aktuell.zustand(dir, True)  # Wand öffnen
                retourDir = (dir+2) % 4     # 180 Grad drehen, von 4,5 auf 0,1 korrigieren (module)
                nb.mark=str(retourDir)      # Nachbar markieren
                todo.append(aktuell)   # Da könnte es ja noch in andere Richtungen weiter gehen
                todo.append(nb)        # Den Nachbar als nächstes bearbeiten
                break                  # For-Schleife verlassen
    print(laby)
    aktuell = paar[1]     # Zielzelle
    weg = [aktuell]    # Weg besteht erst mal nur aus der Zielzelle
    while aktuell!=paar[0]:   # Solange man nicht bei der Startzelle angekommen ist
        wohin = int(aktuell.mark)   # Richtung, in der es zurück geht.
        aktuell = aktuell.nachbar(wohin)  # Nachbarzelle
        weg.append(aktuell)

    print(laby)
    return weg