Optimize AStarRouter and FindExtendedRoute

[Svyatoslav]

Hi. I use AStarRouter and FindExtendedRoute. But if the diagram contains many items, it takes a very long time to load. This is especially noticeable when overlaying text on connectors. How I can optimize AStarRouter, for example, by reducing the number of search iterations? Or how I can catch a connection that takes a lot of time in FindExtendedRoute?

[Petar Mladenov]

Hello Svyatoslav,

By default the AStarRouter has AvoidShapes property set to True. In your case, if you add the text as TextShapes - router will try to avoid them.  You can try to disable this and test if it has positive impact on the performance. Generally the router has a lot of settings - via properties and via DiagramConstants class. Some of them (for example RoutinggridSize) can improve the performance but also there will be a quality loss. 
Regarding labels, I would suggest you add them as Content of the connections or somehow integrated in the shapes or connectors instead of adding them as a shapes since this will make the routing algorithm slower.

Regards,
Petar Mladenov
Progress Telerik

[Svyatoslav]

Is there any way to set the maximum number of iterations for finding a path in AStarRouter? And, if the number of iterations exceeds the specified value, use another algorithm instead of AStarRouter, for example, InflatedRectRouter or edit settings of AStarRouter ( AvoidShapes  for example)?

Also, do you have any ideas in the future to transfer the search for a path in AStarRouter to the background thread?
Now the main problem is in the diagram.Load(): this function is slow (if i use AStarRouter) and takes up the entire main thread, I cannot even provide the user with an animation of the load on the working field.

[Petar Mladenov]

Hello Svyatoslav,

AStarRouter does not provide property for maximum iterations during a route finding traversal. It is an A* algorithm which uses heuristic function which adds possible weighted paths in a sorted queue. There is an internal function which indicates that a path is too long and does not add in in the queue (or adds it as failure, non-orthogonal path) and this plays the role of "cutting" the algorithm. Even if we make the this method protected there is no easy way to override it easily:

/// <summary>
        /// Calculates whether to cut the algorithm if no path is found in reasonable time or with reasonable distance.
        /// Using the heuristic function to determine if the searched path is getting AWAY from the target (happens when algorithm keeps missing the target).
        /// Not using total path cost, because there is no obvious relation between total path cost and start-end distance (getting through walls and bends).
        /// Adding a base value for short paths (start-end distance is small).
        /// </summary>
        private static bool IsPathDivergent(AStarNode node, AStarNode startNode, double gridSize)
        {
            return node.H > (startNode.H * 10) + (gridSize * 10);
        }

because H is previously computed distance :

/// <summary>
        /// Gets or sets the heuristic distance to the endpoint or goal. The smaller the value the closer to the goal.
        /// </summary>
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1704:IdentifiersShouldBeSpelledCorrectly", MessageId = "H")]
        public double H { get; set; }

Generally the property which speeds up the algorithm is DiagramConstants.RoutingGridSize which is actually the step (the step distance) which is added to every segment of a possible path. AvoidShapes - false and AvoidConnectionsverlap (false) might also speed up the performance in scenarios with too many shapes and connections in small viewport.

We haven't considered AsyncRoute kind of function before (or RoutingFinished event) (per connection or per diagram). You can submit a feature request in our feedback portal where we will review it, discuss it internally and eventually approve it.



Regards,
Petar Mladenov
Progress Telerik