Ideale Labyrinthe auf dem Gitter 40×28: rekursiver Rückverfolger, Wilson, Eller oder zufälliger Prim; Lösung mit A* (Manhattan, 4-Nachbarschaft). Wände nachzeichnen und Start sowie Ziel versetzen.
Zum Modell
Labyrinthe und A*: ein ideales Labyrinth ist ein Spannbaum auf dem Gitter der Räume — ein Weg zwischen den Zellen, solange das Feld nicht nachbearbeitet wird. Es entsteht auf demselben Gitter 40×28 wie engineering/astar-dijkstra-grid. „Räume“ sind Zellen mit ungeraden Indizes (1,1)…; Gänge brechen sowohl die Räume als auch die Wand dazwischen auf, daher ist das Labyrinth zusammenhängend und kreisfrei, bis man das Feld bearbeitet. Zur Wahl stehen rekursiver Rückverfolger (DFS-Stapel), Wilson (zufällige Irrfahrten mit Schleifenlöschen), Eller (Vereinigung von Mengen zeilenweise mit zufälligen Vertikalen) und zufälliger Prim (Wachstum des Baums an einer Kantenfront). Nach der Erzeugung läuft **A* mit Manhattan-Heuristik und 4-Nachbarschaft** — dasselbe diskrete Modell wie in der A*-Übung, ohne Diagonalen und ohne „teure“ Zellen. Man kann Wände setzen, Gänge löschen und S/G versetzen; beim Versetzen bleiben die Enden zwingend begehbar.
Für wen: Diskrete Mathematik und Informatik: Labyrintherzeugung und kürzester Weg auf dem Gitter neben A*/Dijkstra.
Wichtige Begriffe
ideales labyrinth
spannbaum
rekursiver rückverfolger
algorithmus von wilson
algorithmus von eller
zufälliger prim
a*-suche
manhattan-heuristik
So funktioniert es
Ideales Labyrinth auf 40×28: Räume auf dem ungeraden Gitter, Gänge brechen die Wände dazwischen auf — ein Spannbaum ohne Kreis. Rekursiver Rückverfolger / Wilson / Eller / Prim liefern verschiedene Zufallsbäume; danach sucht derselbe Lehr-A* (4-Nachbarschaft, Manhattan) den kürzesten Weg an den fertigen Wänden.
Häufige Fragen
Warum sehen Labyrinthe nach Wilson und nach Eller verschieden aus?
Beide bauen zufällige Spannbäume auf demselben Gitter, aber eine andere lokale Zufälligkeit (Wilson-Wurzel, horizontale Entscheidungen bei Eller) ergibt bei endlicher Größe ein anderes Muster.
Ist das derselbe A* wie auf der Seite A* / Dijkstra?
Dieselben vier Richtungen, Manhattan-Heuristik und Einheitskosten je freien Schritt. Hier gibt es keine Diagonalen, gewichteten Zellen und keine Modi Dijkstra oder gierige Suche — nur den Lehr-A*.
Kann man die „Idealität“ des Labyrinths zerstören?
Ja: der Radierer erzeugt einen Kreis (zweiter Weg zwischen Gebieten), überzählige Wände können den Zusammenhang zerreißen. A* zeigt die neue Topologie; fehlt der Weg nach G, gilt kein Pfad.