Lee algorithm

The Lee algorithm is one of several solutions for the breadth-first search / pathfinding, so finding a path from a starting point to a destination point. He was first employed in the automatic creation of boards, but can also occur in computer games used to move the characters within the game world.

Algorithm

Hereinafter the Lee - algorithm is given in pseudocode. Given an array where there are walkable fields unbetretbare fields as well as a start and an end point.

1 ) Initialization

- The starting point is marked with 0   - I: = 0 2) Wavy spread

- REPEAT       - Mark all unlabeled -accessible fields, the neighbor is checked with i, i 1       - I: = i 1     UNTIL ( (end-point is reached) or ( no field can be marked ) ) 3) backtrace

- Go back to the starting point, here is the actual path marked     REPEAT       - Go to the next field, which is marked with a value that corresponds exactly to the value -1 has to the current field       - Select this field as part of the path     ( Is achieved starting point) UNTIL 4) Clean up

This should only happen if, for example, Wants to lay out boards. In computer games, where one wants to calculate the paths of game characters, you do not block the path, because the game characters are so walked along the path and not block it.

- The path found will be marked as not accessible.   - All fields marked otherwise shared are reset to their initial value. Web Links

  • Http://www.eecs.northwestern.edu/ ~ haizhou/357/lec6.pdf

Swell

  • Wayne Wolf: Modern VLSI Design. Prentice Hall, ISBN 0-13-061970-1, pp. 518ff ..
  • CY Lee: An Algorithm for Path Connections and Its Applications. In: IRE Transactions on Electronic Computers. EC-10, No. 2, 1961, pp. 346-365.
  • Optimization algorithm
  • Routing
  • Graph search algorithm
  • Travel and Route Planning
  • Computer Aided Engineering
504354
de