Automated circuit layout with routing of wires

[danilovesky]

A layout tool is required that intelligently places the circuits components and automatically routes all the wires.

Note that currently implemented routing algorithm recalculates the shape of all wires and cannot be applied to a subset of wires.

[sgaflv]

Just rerouting a single wire would be inconsistent, as the routing output depends on the order in which wires are routed (explicit wire route order sorting will be needed to make routing more stable, at least for the starter version). The obstacles class is used to completely define the routing task. If something was changed in the obstacles, then rerouting is necessary and will take place.

It will still be possible to route wires under condition, that part of the routes are manually prerouted, such routes will be consequently registered in the obstacles class.

Both start options are valid: manual router start is needed, when automatic routing is off or when there are too many objects, and router takes long, which becomes inconvenient.

Interactive routing is good when you add a new connection, or when you want to move gates around.

[danilovesky]

Just to document it for future -- there seems to be a problem with routing cache.

To reproduce:

1. Open circuit-celement-decomposed-hazard.work
2. Activate routing tool -- the routes are built fine.
3. Activate selection tool and remove input in2 and gate g1.
4. Activate routing tool again -- an exception is thrown:

Exception in thread "AWT-EventQueue-0" java.lang.NullPointerException
    at java.util.Collections$UnmodifiableCollection.<init>(Collections.java:1026)
    at java.util.Collections$UnmodifiableSet.<init>(Collections.java:1128)
    at java.util.Collections.unmodifiableSet(Collections.java:1118)
    at org.workcraft.dom.NodeContextTracker.getPostset(NodeContextTracker.java:144)
    at org.workcraft.dom.AbstractModel.getPostset(AbstractModel.java:139)
    at org.workcraft.plugins.circuit.routing.RouterClient.registerObstacles(RouterClient.java:83)
    at org.workcraft.plugins.circuit.VisualCircuit.draw(VisualCircuit.java:392)
...

Note that if step 2) is skipped, then there is no exception, therefore I think the problem is because the routing cash was not updated properly after removal of circuit nodes.

Also exceptions are thrown if a circuit has a Joint, but that is fine, as the circuit we decided to allow routing only without joints. Maybe later we can improve it a bit and add joints, e.g. making them like a combination of an input and output port.

Sometimes the route can be significantly improved by moving a couple of turn-points, e.g.:

a) In circuit-celement-cg.work the route from in2 to pint g0/B could be improved, by assign a penalty for new intersections from the same source.

b) In circuit-buck-cg-feedback.work the self-loop on inst_gp gate is going long way on top around inputs, even though there is a short way at the bottom. It feels like some threshold prevents the connection to go directly to the input pin and forces a long polyline section before the input pin.

circuit-buck-cg-feedback.work.zip
circuit-celement-cg.work.zip
circuit-celement-decomposed-hazard.work.zip

[danilovesky]

@sgaflv I have (almost) integrated this router into the master branch and it works great most of the time!

Form time to time I observe unrouted wires in situations where routing seems to be obvious. I managed to cupture this problem in a simplified example with a single fork (remove.zip) fork.work.zip

Basically, if you move in0 port up/down there is a place (usually just when two fork branches become symmetrical) where one of the branches is not routed. Could you have a look please? If it is something simple, please fix, otherwise I will try to debug myself...

[danilovesky]

For interactive graphical debug information about routing please switch on the Layout->Circuit->Debug routing option in global Preferences. There are also several threshold values that influence the routing.

[danilovesky]

@sgaflv: Strange routing behaviour of the routing algorithm (enable Debug routing to interactively visualise the routes).

A snail shape route is created when there is a simpler route available -- see
circuit-bad.work.zip

Interestingly, if the whole circuit is moved a little horizontally (so the relative position of all components remain unchanged) the routing becomes correct -- see
circuit-good.work.zip

Update: This example moved to issue #821.

[danilovesky]

@sgaflv Here the other strange routing decision I mentioned the other day, now isolated into a small circuit:
circuit-strage.work.zip

Notice that in1port is connected to the topmost pin (not to the second pin), and what looks like wire intersection is in fact two wires touching each other at the corners...

Update: This issue has been fixed.