Paths which create DRC violations with themselves #13
Description
This is a DRC violation because the two met1 (blue) via encap pads (around vertices) are too close to each other:
No existing rules are being broken. The problem is that the shortest-path search does not consider the path traversed so far in considering whether additional edges or nodes are valid. This is generally fine, since the routing grid is set up with enough rules that these violations are not common. However, cases like this suggest additional heuristics are required.
(The straightforward way to solve this is to equip the search with the path traversed so far, but this is computationally very expensive. Consider that each path, for each new vertex or edge, would have to check for conflicts against the entire path so far. O(n^2) at the least.)
It should be possible to statically force disuse of edges that are too short and do U-turns or something. But is that enough?
Update: the reason that this turn is even made, and why this is uncommon, is that there is a pin being avoided immediately to the left of the target pin and the router has found a path between it and the other obstacles.