Lee algorithm
Encyclopedia
The Lee algorithm is one possible solution for maze routing problem
Maze router
Maze runner is a connection routing method that represents the entire routing space as a grid. Parts of this grid are blocked by components, specialised areas, or already present wiring. The grid size corresponds to the wiring pitch of the area....

s based on Breadth-first search
Breadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...

.

1) Initialisation
- Select start point, mark with 0
- i := 0
2) Wave expansion
- REPEAT
- Mark all unlabeled neighbors of points marked with i with i+1
- i := i+1
UNTIL ((target reached) or (no points can be marked))
3) Backtrace
- go to the target point
REPEAT
- go to next node that has a lower mark than the actual node
- add this node to path
UNTIL (start point reached)
4) Clearance
- Block the path for future wirings
- Delete all marks

Of course the wave expansion marks only points in the routable area of the chip, not in the blocks or already wired parts, and to minimize segmentation you should keep in one direction as long as possible.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK