This app demonstrates three well-known CAD algorithms for multilayer routing connections between modules. It includes the realization of the Lee Algorithm, the A* Algorithm, and the Hadlock’s Algorithm.
To Use the App
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 choose the routing algorithm by clicking on the combo box and click on the source and destination points and press the start button. The app will then show the search performed by the chosen algorithm and the final connection that is made. You can make additional connections by clicking to select an additional source and destination points.
To erase all connections and start over, click on the “trash can” button.
To change the speed of the expansion, drag the “slide bar”.
To pause the routing, click on the “pause” button.
To stop the routing, click on the “stop” button.
To see the routing step by step, first, click on the “pause” button, then click on the “step” button.
To disable the audio feedback, click on the “Mute” check box.
To change the number of layers and the size of grids, click on the “Resize” button, a pop-up window will occur, type in the desired grid size and number of layers and click on “Resize”.
If you’re interested, here is the source code
Routing is the task of finding a set of connections that will wire together with 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 search and labeling each gridpoint with its 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.