Maze runner

This article is about the computer routing method. For the novel by James Dashner, see The Maze Runner. For the film adaptation of the novel, see The Maze Runner (film).

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.

A maze runner may use 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 is determined by backtracking through the cells.

References

Lee, C. Y. (1961), "An Algorithm for Path Connections and Its Applications", IRE Transactions on Electronic Computers, EC-10 (2): 346–365 . One of the first descriptions of a maze router.

This article is issued from Wikipedia - version of the Friday, December 25, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.