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…

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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.