Lee algorithm
The Lee algorithm is one of several solutions for breadth-first search / pathfinding , i.e. finding a way from a starting point to a destination. At first it was used for the automatic creation of circuit boards , but can also be used in computer games to move the characters within the game world .
algorithm
In the following, the Lee algorithm is given in pseudocode . There is an array in which there are accessible fields, non-accessible fields as well as a start and an end point.
1) initialization
- Der Startpunkt wird mit 0 markiert - i := 0
2) Wavy propagation
- 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) clean up
This only has to happen if you z. B. wants to layout boards. In computer games, where you want to calculate the paths of characters, you do not have to block the path, because the characters have walked along the path and are no longer blocking it.
- Der gefundene Pfad wird als nicht begehbar markiert. - Alle anderweitig markierten Felder werden auf ihren Initialwert zurückgesetzt.
Web links
swell
- Wayne Wolf: Modern VLSI Design . Prentice Hall, ISBN 0-13-061970-1 , pp. 518 ff .
- CY Lee: An Algorithm for Path Connections and Its Applications . In: IRE Transactions on Electronic Computers . EC-10, no. 2 , 1961, p. 346-365 .