|Re: Manhattan Connection routing [message #1067971 is a reply to message #1067830]
||Thu, 11 July 2013 13:38
| Robert Brodt
Registered: August 2010
Location: Colorado Springs, CO
The existing manhattan router is a bit primitive because it tries to blindly calculate a route without prior knowledge of shapes and connections that may cause collisions or intersections. It works well enough for now, but I'm still working on a different algorithm which will be robust enough to navigate any topography and find routing solutions. This will eventually become what I hope to contribute to Graphiti.
This new router (the RouteSolver and RoutingNet classes) is still experimental and takes a different approach: it first calculates a navigable net of "empty space" (rectangles) between shapes, and then finds one or more optimal solutions that represent a minimal chain leading from the source to the target shape. The screen capture here illustrates what I mean:
The green rectangles are the empty spaces that are adjacent to the source shape, red are those adjacent to the target shape and light gray is everything in between. The light blue arrows are the navigable links that connect all of the empty spaces. All that needs to be done is to determine an optimal solution, and then route the connection inside the empty spaces that form this solution. The connection could consist of either orthogonal (manhattan) line segments, or diagonals (direct routing) depending on preference; the resulting connection would avoid shape collisions and intersections with other connections.
As I mentioned, this route solver can handle any topography, and will be able to find a solution for, e.g. the case where the target shape is "hidden" inside the "U" shape formed by the 3 tasks. Of course, if a shape is completely surrounded by other shapes, there is no solution.
If anyone is interested in helping expand on this idea (or if there are better ideas out there) I'm open to suggestions
BTW, the RoutingNet class has Graphiti features to draw the emtpy spaces and links and I've been using this to visualize an optimal solution to the routing problem.
Powered by FUDForum
. Page generated in 0.02572 seconds