Lee algorithm
Encyclopedia
The Lee algorithm is one possible solution for maze routing problem
s based on Breadth-first search
.
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.
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.