Algorithm to lay out orthogonal connector lines without overlap

Question

I'm drawing a graph of nodes connected by orthogonal edges with corners. The nodes are laid out on a grid, and the edges (conceptually) follow the grid lines. The paths the edges take are laid out with an A* pathfinder, and I'd like to keep those paths. However, obviously some edges will overlap -- that is, cover the same lines on the grid. A naive approach to laying out the edges just has them on top of one another (as in the left-hand diagram below). I would like to take a "metro map" approach (similar to the London Underground map, etc) where edges are slightly offset from the grid lines exactly in order that edges do not overlap. Is there an existing algorithm for laying out such edges?

Answer 1

I don't know about existing algorithms, but I would implement a solution to your problem something like the following.

Create a data structure to store, for each section of grid line, which path segments follow it, where each segment is placed on its own "track". Then for each path segment, find the next track that is available for all the required grid line sections.

Something like this:

calc a* paths
split paths at their corners into segments
keep a list of "tracks" for each section of grid line

for each segment:

    # find next empty track
    while true: (track loop)

        # check track empty for all line sections
        for each grid line section covered by segment:
            if track not empty:
                next track
                continue track loop

        break track loop

    # record line segment in track
    for each grid line section covered by segment:
        record segment in line section's track

render line segments by offsetting from grid line 
  according to track number