One of our team members, Robert Boyles, just built a new auto-routing feature for our schematic-style editor. This added a whole new level of sophistication and clarity for drawing a schematic and connecting components in a design.. Find out what he had to stay when we asked him a few questions about his process.
Up until this point, the logic behind the wiring of connections was pretty limited and there weren't any restrictions as to where were wires could be. This meant that when you uploaded a design, unless you had meticulously selected the position of each segment, there was a good chance that the segments could be going under/over a component, or even off of the diagram completely. While the connect was valid, it was simply too difficult for a user to follow what connections went where.
The purpose of the auto router is to take a set of existing connections and attempts to generate the optimal wire between each pair of connected ports. The goal was to improve the readability of a design without user interaction. This greatly benefits tool users because it decreases the amount of time in which a user spends figuring out what is going on, giving them more time to improve their design and continue to use the tools.
The key requirements of the design were that the router was restricted to generating wires which consisted of only horizontal and vertical segments. The results of the algorithm also needed to be an optimal wire in the sense that it resulted in the shortest path between two ports and produced the least number of bends. This means that while a short path is desired, we are willing to accept a longer path if it means the wire has a smaller number of bends in it. Finally, the most important objective was speed.
These requirements or objectives lead me to settle on a modified version of an A* algorithm. The A* algorithm is guaranteed to find the shortest path between two points by evaluating a cost function between your current location and each of your immediate neighbors. This was modified by adding a penalty to any move which would introduce a bend into the path.
The speed at which the algorithm runs depends on the size of the grid that a give path can move on; the more neighbors that you need to process, the longer the path will take to generate. The size of the grid was reduced substantially by generating a concept of an orthogonal visibility graph. The graph reduces the nodes that need to be processed by creating horizontal/vertical segments at points of interest, such as corners of component bounding boxes and component ports. Any locations where an intersection is created by there horizontal/vertical segments are also added to the list of nodes to be processed. These segments were generate by implementing a line sweep algorithm in both the horizontal and vertical directions using the locations of the components. Using this orthogonal visibility grid, rather than having to evaluation a cost function at each pixel on the diagram, you only need to process a number in the tens for a small design or a few hundred for a large design.
While the algorithm was guaranteed to produce the wire which resulted in the fewest number of bends, a lot of times segments of different connections will overlap, which is worse for clarity than segments that go off the diagram boundary. This was solved by determining which segments were overlapping once the A* search had run, and slightly separate them a few pixels.
The downside to this approach is that if an optimal wire follows a path that is along the edge of a component and needs to be separated, ti could end up passing over a component, which is one of the things we wanted to eliminate by implementing the router. To get around this, the bounding boxes of each component were padded by 10 pixels.
Currently overlapping segments are only attempted to be separated once. While this resolves most issues, sometimes separating one set of wires can produce an overlap with a different set. Trying to continuously loop through the set of overlapping segments until all conflicts are resolved results in an infinite loop pretty easily in the current implementation. This would be improved by following the procedure similar to the one laid out in the paper mentioned above