Lee-Algorithmus
Der Lee-Algorithmus ist eine von mehreren Lösungen zur Breitensuche/Pathfinding, also das Finden eines Weges von einem Ausgangspunkt zu einem Zielpunkt. Zuerst wurde er bei der automatischen Erstellung von Platinen angewandt, kann aber auch bei Computerspielen zum Einsatz kommen, um die Figuren innerhalb der Spielwelt zu bewegen.
Algorithmus
Im Folgenden wird der Lee-Algorithmus in Pseudocode angegeben. Gegeben ist ein Array, in dem es betretbare Felder, unbetretbare Felder sowie einen Start- und einen Endpunkt gibt.
1) Initialisierung
- Der Startpunkt wird mit 0 markiert
- i := 0
2) Wellenförmige Ausbreitung
- REPEAT
- Markiere alle unmarkierten, betretbaren Felder, deren Nachbar mit i markiert ist, mit i+1
- i := i+1
UNTIL ((Endpunkt erreicht) or (kein Feld kann markiert werden))
3) Backtrace
- gehe zum Endpunkt
REPEAT
- Gehe zum nächsten Feld, das mit einem Wert markiert ist, der genau dem Wert −1 entspricht, den das aktuelle Feld hat
- markiere dieses Feld als Teil des Pfades
UNTIL (Startpunkt erreicht wird)
4) Aufräumen
Dieses muss nur geschehen, wenn man z. B. Platinen layouten will. In Computerspielen, wo man die Wege von Spielfiguren berechnen will, muss man nicht den Pfad blockieren, weil die Spielfiguren ja den Pfad entlanggelaufen sind und ihn nicht mehr blockieren.
- Der gefundene Pfad wird als nicht begehbar markiert. - Alle anderweitig markierten Felder werden auf ihren Initialwert zurückgesetzt.
Quellen
- Wayne Wolf: Modern VLSI Design. Prentice Hall, ISBN 0-13-061970-1, S. 518 ff.
- C. Y. Lee: An Algorithm for Path Connections and Its Applications. In: IRE Transactions on Electronic Computers. EC-10, Nr. 2, 1961, S. 346–365.