Circular Obstacle Pathfinding

View on GitHub Pathfinding around a set of circular obstacles

Mar 2017

Navigating a forest

The A* pathfinding algorithm is a powerful method for quickly generating optimal paths. Typically, people demonstrate A* navigating grid-based maps, but A* isn’t just a grid algorithm! It can work on any graph. We can use A* to find a path through this world of round obstacles.

How does the same algorithm solve both problems? Let’s start with a review of how A* works.

A* algorithm

The A* algorithm finds the optimal path from the start point to the end point, avoiding obstacles along the way. It does this by gradually expanding a set of partial paths. Each partial path is a series of steps from the start point to some intermediate point on the way to the goal. As A* progresses, the partial paths get closer and closer to the goal point. The algorithm terminates once it finds a complete path that it can prove to be better than any of the remaining possibilities.

At each step in the algorithm, A* evaluates the set of partial paths and generates some new paths by expanding the most promising path in the set. To do this, A* keeps the partial paths in a priority queue, sorted by estimated length—the actual measured length of the path so far, plus a guess of the remaining distance to the goal. This guess must be an underestimate; that is, the guess can be less than the actual distance, but not greater. In most pathfinding problems, a good underestimate is the geometric straight-line distance from the end of the partial path to the goal. The actual best path to the goal from the end of the partial path might be longer than this straight line distance, but it can’t be shorter.

When A* begins, the priority queue contains just one partial path: the start point.

The algorithm works by repeatedly removing the most promising path from the priority queue, that is, the path with the smallest estimated length. If this path ends at the goal point, the algorithm is done—the priority queue ensures that no other path could possibly be better. Otherwise, starting from the end of the partial path it removed from the queue, A* generates some new paths by taking single steps in all possible directions. It places these new paths back into the priority queue and begins the process again.

Graph

A* works on a graph: a collection of nodes connected by edges. In a grid-based world, each node represents an individual grid location, while each edge represents a connection to a neighboring location to the north, south, east or west.

Before A* can run on the forest of round obstacles, we need to convert it into a graph. All the paths through the forest consist of alternating line segments

and arc sections

.

These are edges in the path graph. The endpoints of these edges become nodes

.

A path through the graph is a series of nodes connected by edges:

Both segments and arcs act as edges in the graph. We’ll call the segments surfing edges, because the path uses them to surf between obstacles. The arcs we’ll call hugging edges, as their purpose in the path is to hug the sides of the obstacles.

Next we’ll explore a simple way to turn the obstacle forest into a graph: generate all of the possible surfing and hugging edges.

This is called a tangent visibility graph. Generating surfing edges

The surfing edges between a pair of circles are the line segments which just barely kiss both circles; these segments are known as bitangents, and there are four of them for each pair of circles.

The bitangents which cross between the circles are the internal bitangents, while the ones which go along the outside are the external bitangents.

Internal bitangents

Historically, internal bitangents were important for calculating the length of a belt which crosses over two different sized pulleys, and so the problem of constructing internal bitangents is known as the belt problem. To find the internal bitangents, calculate the angle \(\theta\) in the diagram below.

Overlapping circles have no bitangents

It turns out that, given circles centered on points \(A\) and \(B\) with radii \(r_A\) and \(r_B\), and centers separated by distance \(d\): \[\theta = \arccos{{r_A+r_B}\over{d}}\] Once \(\theta\) is known, it's easy to find points \(C\), \(D\), \(E\) and \(F\).

External bitangents

Constructing external bitangents—the pulley problem—uses a similar technique.

Smaller circle entirely contained in larger one

For external bitangents we can find \(\theta\) like this: \[\theta = \arccos{{\lvert r_A - r_B \rvert} \over d}\]

It doesn’t matter whether circle A or B is bigger, but as shown in the diagram, \(\theta\) appears on the side of A toward B, but on the side of B away from A.

Line of sight

Taken together, the internal and external bitangents between two circles constitute surfing edges between the circles. But what if a third circle blocks one or more of the surfing edges?

Circle blocks line of sight A and B visible from each other

If a surfing edge is blocked by another circle, we need to throw the edge out. To detect this case, we use a simple point-line-distance calculation. If the distance from the surfing edge to the obstacle’s center is less than the obstacle’s radius, then the obstacle blocks the surfing edge, and we should throw the edge away.

To calculate the distance from point \(C\) to line segment \(\overline{AB}\), use the following method: First, compute \(u\), the fraction of the distance along segment \(\overline{AB}\) at which a perpendicular ascender hits point \(C\):

\[ u = {(C - A) \cdot (B-A) \over (B-A)\cdot(B-A)} \]

Then compute the position \(E\) on \(\overline{AB}\): \[ E = A + \mathrm{clamp}(u, 0, 1) * (B - A) \] 0

1 u={{Math.round(100*(C.x-A.x)/(B.x-A.x))/100}} d r

The distance \(d\) from \(C\) to segment \(\overline{AB}\) is the distance from \(C\) to \(E\):

\[d = \|E - C\|\]

Since \(d < r\), the circle blocks the line of sight from \(A\) to \(B\), and the edge should be thrown out. \(d \ge r\), there is line of sight from \(A\) to \(B\), and the edge should be kept. Try moving the circle to see the case where \(d \ge r\) \(d < r\).

Generating hugging edges

The graph nodes connect a surfing edge to a hugging edge. We generated the surfing edges in the previous sections. To generate the hugging edges we start at the endpoint of a surfing edge, traverse around the circle, and terminate at the endpoint of a different surfing edge.

To find the set of hugging edges for a circle, first find all the surfing edges that touch the circle. Then, create hugging edges between all the surfing edge endpoints on the circle.

Putting it all together

Given the generation of surfing edges, hugging edges and nodes, and the culling of blocked surfing edges, we can produce a graph and run pathfinding using the A* algorithm.