WPF Diagrams: Improved path routing

Our WPF Diagrams framework includes a few connection routing algorithms each with different speed and collision-detection preferences. The most impressive router of them all is the AStarPathfinder. As the name suggests, this pathfinder uses the well known A* algorithm to route the connections around all the nodes in the diagram. This algorithm is paired with a custom built data collection which functions similar to a quad-map to minimize the collision detections and thus improve performance.

The first version that was released a couple of years ago performed very well and was great at routing connections while avoid collisions with nodes and minimizing the number of bends in each connection. The main thing that it was missing however is that it did not consider parallel connection collisions. This can easily occur when there are multiple connections on a single node that follow the same path as seen in the image below. This makes it difficult for the user to follow the connections in this kind of diagram.

Old Connection Paths

A little later, we upgraded this path router to consider parallel connections. This was done by updating the A* algorithm to think of clusters of connections as obstacles to route around. This feature is enabled by passing a number into the constructor to specify the desired distance between parallel connections. This produced great results for the customer who requested this feature.

New Connection Paths

Although the results were great, the performance for much MUCH larger diagrams was almost unusable. There were also some bugs around the ordering of the connections which could cause lots of perpendicular overlaps. Considering each connection cluster as an obstacle to route around was just too much for the algorithm to handle. So we reverted the connection considerations and did some research into a 3-phase routing algorithm:

  • Phase 1: Create an imaginary grid of horizontal and vertical lines around the nodes.
  • Phase 2: For each connection, run the A* algorithm on the grid from phase 1.
  • Phase 3: Iterate through each cluster of parallel connections and order/separate them.

The first 2 phases were already in our pathfinder. The problem with the 3rd phase is that it requires the first 2 phases to have already been applied to the entire diagram in order for it to work. This would cause bad performance when dragging a node because all 3 phases would need to be re-run on the whole diagram model. We managed to solve this issue be implementing another custom data collection that could cache the post A* connection paths and very quickly return them for a given area of the diagram. This made it possible to run the 3rd phase only on the parts of the diagram that changed.

The result was a huge boost to both the performance and outcome of the AStarPathfinder on large diagrams such as the extreme case below. (Click on the image to get a better look at the magnitude of the diagram I was using for testing! :-).

Large Diagram

Got a diagram with lots of connection that needs a powerful path router? Grab these improvements right now from the current nightly build. Remember to pass in the desired connection separation value into the constructor of the AStarPathfinder your connections are using.

Thanks for reading! Happy coding :)

Tagged as WPF Diagrams

One Response to “WPF Diagrams: Improved path routing”

Archives

Join our mailer

You should join our newsletter! Sent monthly:

Back to Top