Benutzer-Werkzeuge

Webseiten-Werkzeuge


graphen:breitensuche:lee:start

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:

graphen/breitensuche/lee/start.1697637168.txt.gz · Zuletzt geändert: 2023/10/18 13:52 von Martin Pabst

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki