Maze runner

From Wikipedia, the free encyclopedia

 This article needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (December 2006)

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. The goal is to find a chain of grid cells that go from point A to point B.

[edit] Algorithm

The algorithm used for maze runners the Lee algorithm. It uses a wave propagation style (a wave are all cells that can be reached in n steps) throughout the routing space. The wave stops when the target is reached, and the path determined by backtracking through the cells.

[edit] References

  • C.Y. Lee, An algorithm for path connections and its applications, IRE Trans. Electronic Comput., EC-10, 346–365, 1961. One of the first descriptions of a maze router.
This computer network-related article is a stub. You can help Wikipedia by expanding it.