Diagram Lines: Finding the Path

This is the second blog post in our series on how we improved our diagramming lines feature. We recently improved this feature by allowing users to pick the edge of an object they want their diagramming line to connect to. In the first blog post we examined how we can select a candidate set of points through which we can route a diagramming line. The first blog post isn’t a prerequisite to reading this one but I’d highly recommend reading it first if you haven’t already. At the end of that post we found our candidate set of points as pictured below.

Now that we have our candidate set of points, how do we go about finding the correct path? Can we use an existing path-finding algorithm like Djikstra’s or A*? Besides just finding the correct path, we need to be mindful to do it in a fast, efficient, and memory-conscious way. This blog post answers these questions and examines how we can find our path.

What’s in a Path?

Now that we have a set of candidate points we first need to define the requirements of our path. First, we know that a point can only connect to those points that are directly beside it along the x and y axis. For example, in the following diagram point A has valid neighboring points B and D. Points C, E, and F are invalid neighboring points of A. From A we can’t go to C since we’d pass through B and we can’t navigate to E and F since we’d have to cross diagonally.

Additionally, a point cannot connect to another point if the path goes across an entity.

Let’s Build a Graph

Now that we have requirements for our path, let’s look at how we can find the path. Unfortunately, traditional path-finding algorithms don’t quite work for our use case. For example, Djikstra’s algorithm could find the red path when we really want the black path.

Additionally, the A* algorithm doesn’t quite fit our use case either since we don’t have a heuristic function to tell us where to go.

If we take a step back and think about the problem we’re trying to solve there are two facts that we can leverage to design an algorithm to find the path. First, we always know the starting direction the path must take. For example, if our connector is connected to the left side then we know the path must start in the left direction. Secondly, once we’ve gone forward we can’t go backward on the path. Given these two facts, we can use a flooding algorithm to build a connected graph, G, of the possible paths that we could take to reach our destination. Keeping with our mapping analogy G will give us the possible routes we can take to get from the starting point to the end point.

The algorithm is as follows. We keep a list of points that we need to find neighbors for and a list of points that we’ve already visited. Remember, we can’t go backward once we’ve gone forward. We’ll initialize the points that we need to find neighbors for with our starting point. While we have points that we need to find neighbors for, we’ll iterate through each of the points, find and store each point’s neighbors, and create a new list of points that we need to find neighbors for. After we find neighboring points for a point, we’ll mark the point as visited. In this way, the algorithm floods outwards from the starting position until we find all neighboring points of each and every point.

The algorithm floods outwards from the starting point to build the graph of neighboring points for each point.

The pseudocode of the algorithm is as follows.

points = [start]
 
while points.length:
  new_points = []
 
  for point in points:
    if bottom_neighbor & not_visited(bottom_neighbor):
      store_bottom_neighbor(point, bottom_neighbor)
      new_points.push(bottom_neighbor)
    if top_neighbor & not_visited(top_neighbor):
      store_top_neighbor(point, top_neighbor)
      new_points.push(top_neighbor)
    if left_neighbor & not_visited(left_neighbor):
      store_left_neighbor(point, left_neighbor)
      new_points.push(left_neighbor)
    if right_neighbor & not_visited(right_neighbor):
      store_right_neighbor(point, right_neighbor)
      new_points.push(right_neighbor)
 
    mark_as_visited(point)
 
  points = new_points

Walk the Graph

At this point, we’ve taken our candidate points and we’ve built a connected graph G that tells us the possible paths that we can take to get from our starting point to the destination point. Imagine you’ve just punched in a new location into your GPS, we now have the possible paths we can take to get from our starting point to our end point. So how do we find the correct path to take?

One of the things that I really like to do when solving a hard problem is to first solve it by hand. If we try to find the path from our graph a couple of times by hand, a few patterns emerge that will help us design an algorithm. First, the path should minimize turns. For example, the red path in the following image is incorrect since the path should have continued straight.

Secondly, looking at our connected graph G we know that there are going to be points that are dead ends. You can think of dead ends like a street with no outlet, there are no more neighboring points that we can visit. What happens when we reach a dead end? If we were actually driving down a street that’s a dead end we would go backward and mark that street as a dead end and that’s exactly what our algorithm will do.

Lastly, we should always prioritize going in the same direction if possible. Since we know the starting point and the side that starting point is on we know the direction that the path must start in. For example, if our starting point is on the right side we know that the path must start in the right direction. For our algorithm we need to track points that are dead ends, we need to keep track of the path we’re building and we need to store the previous direction that we were going in so we can continue moving in that direction if possible.

The algorithm works as follows. Beginning at the starting point we continue to find the next point in the path using the connected graph G until we’re at the end point. When we’re finding the next point we always choose the point that’s in the same direction until we can’t go any further in that direction. If we can’t continue in the same direction we try to go toward the end point. If we can’t continue towards the end point we try to go towards any other available neighboring point. If there aren’t any neighboring points to go towards we mark the current point as a dead end, pop off the current point from the path, and continue onwards from the last point in the path.

The current path is marked as black above and dead ends are marked as gray. Notice the algorithm continues to back track until another neighboring point is found.

The pseudocode for the algorithm is as follows.

path = [start_point]
completed = false
previous_direction = get_direction(start_point)
while !completed:
  current_point = path[path.length - 1]
  next_point = null
  if point_in_same_direction and not_dead_end(point_in_same_direction):
    next_point = point_in_same_direction
  else if point_towards_end_point and not_dead_end(point_towards_end_point):
    next_point = point_towards_end_point
  else if remaining_neighbor_point and not_dead_end(remaining_neighbor_point):
    next_point = remaining_neighbor_point
previous_direction = get_direction(next_point)
if next_point == null:
  mark_as_dead_end(current_point)
  path.pop()
else:
  if next_point == end_point:
    completed = true
  path.push(next_point)

What’s Next?

That’s path-finding! We’ve built a connected graph G of the possible paths we can take from our starting point to our end point. And we’ve defined how we can walk G to find our path. In the next and last blog post in this series, we’ll look at how we can evaluate candidate paths.