Maze Router Applet The Lee Algorithm
This applet demonstrates a well-known CAD algorithm for routing connections
between modules.
If you're interested, here is the source code About Maze Routing Routing is the task of finding a set of connections that will wire together the terminals of different modules on a printed circuit board or VLSI chip. In the simplest case, these connections are made on a single routing layer of metal. Each connection or net connects a source terminal to a destination terminal. The Maze Routing algorithm represents the routing layer as a grid, where each gridpoint can contain connections to adjacent gridpoints. It searches for a shortest-path connection between the source and destination nodes of a connection by performing a breadth-first search and labelling each gridpoint with it's distance from the source. This expansion phase will eventually reach the destination node if a connection is possible. A second traceback phase then forms the connection by following any path with decreasing labels. This algorithm is guaranteed to find the shortest path between a source and destination for a given connection. However, when multiple connections are made one connection may block other connections. For more information about Maze Routing and other forms of routing, see a VLSI CAD textbook such as M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Design, McGraw-Hill, 1996. |