Maze Router Applet
The Lee Algorithm

This applet demonstrates a well-known CAD algorithm for routing connections between modules.

To Use the Applet

The routing surface is represented as a grid in which each gridpoint can be the source of a connection, a destination of a connection, or a wire that connects adjacent gridpoints. To route connections, follow the prompt and click on the source and destination points. The applet will then show the search performed by the Lee Algorithm and the final connection that is made. You can make additional connections by clicking to select additional source and destination points.

To erase all connections and start over, click on the "CLEAR" button.

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.

| CadApplets Home | Channel Router Applet | Maze Router Applet | Multilayer Maze Routing | Placement | Annealing |

Last updated on July 27, 2001 by John A. Nestor