Dies ist eine alte Version des Dokuments!
Exkurs zu Game Development: Lee's Algorithm
Ausgangsproblem: Eine Figur (z.B. die Biene im Bild) soll auf kürzestem Weg zu einem Ziel (im Beispiel: der Edelstein) kommen, dabei aber Hindernissen (hier: die grauen Wände) ausweichen. Die Hindernisse können dabei ein beliebig komplexes Labyrinth bilden, so dass die Problemstellung nicht so trivial ist, wie sie auf den ersten Blick erscheint. Wir können sie aber lösen, indem wir das Spielfeld als Graph interpretieren. Dazu zerlegen wir es in lauter gleich große Quadrate ("Kacheln"), die entweder ganz aus Mauerwerk oder ganz aus betretbarem Boden bestehen. Jede Kachel ist ein Knoten im Graphen:
Die schwarzen Striche sind die Kanten des Graphen. Ausgehend von dem Knoten, an dem sich der Diamant befindet, traversieren wir den Graphen mittels Breitensuche solange, bis wir bei der Biene angelangt sind. Bei jedem Knoten speichern wir dabei, wie viele Schritte der Breitensuche wir bereits durchgeführt haben.
Jetzt muss die Biene nur noch in absteigender Reihenfolge den Zahlen folgen um zum Diamanten zu finden.
Haben Sie gestutzt, als Sie gelesen haben, dass wir die Breitensuche beim Diamanten und nicht bei der Biene beginnen? Welches Problem würde entstehen, wenn wir bei der Biene beginnen?
- im Einzelschrittmodus ausgeführt wird(Klick auf ),
- an einem Breakpoint hält (Setzen eines Breakpoints mit Mausklick links neben den Zeilennummern und anschließendes Starten des Programms mit ) oder
- in sehr niedriger Geschwindigkeit ausgeführt wird (weniger als 10 Schritte/s).