Circular Obstacle Pathfinding
Mar 2017
Navigating a forest
The A* pathfinding algorithm is a powerful method for<br>quickly generating optimal paths. Typically, people<br>demonstrate A* navigating grid-based maps, but A* isn’t just<br>a grid algorithm! It can work on any graph. We can use A* to<br>find a path through this world of round obstacles.
How does the same algorithm solve both problems? Let’s start<br>with a review of how A* works.
A* algorithm
The A* algorithm finds the optimal path from the start point<br>to the end point, avoiding obstacles along the way. It does this by<br>gradually expanding a set of partial paths. Each partial path<br>is a series of steps from the start point to some intermediate point<br>on the way to the goal. As A* progresses, the partial paths get<br>closer and closer to the goal point. The algorithm terminates once it<br>finds a complete path that it can prove to be better than any of the<br>remaining possibilities.
At each step in the algorithm, A* evaluates the set of<br>partial paths and generates some new paths by expanding the<br>most promising path in the set. To do this, A* keeps the<br>partial paths in a priority queue, sorted by estimated<br>length—the actual measured length of the path so<br>far, plus a guess of the remaining distance to the<br>goal. This guess must be an underestimate; that is,<br>the guess can be less than the actual distance, but not<br>greater. In most pathfinding problems, a good underestimate<br>is the geometric straight-line distance from the end of the<br>partial path to the goal. The actual best path to the goal<br>from the end of the partial path might be longer than this<br>straight line distance, but it can’t be shorter.
When A* begins, the priority queue contains just one partial<br>path: the start point. The algorithm works by repeatedly<br>removing the most promising path from the priority queue,<br>that is, the path with the smallest estimated length. If<br>this path ends at the goal point, the algorithm is done—the<br>priority queue ensures that no other path could possibly be<br>better. Otherwise, starting from the end of the partial path<br>it removed from the queue, A* generates some new paths by<br>taking single steps in all possible directions. It places<br>these new paths back into the priority queue and begins the<br>process again.
Graph
A* works on a graph: a collection of nodes connected<br>by edges. In a grid-based world, each node represents<br>an individual grid location, while each edge represents a<br>connection to a neighboring location to the north, south,<br>east or west.
Before A* can run on the forest of round obstacles, we need<br>to convert it into a graph. All the paths through the forest<br>consist of alternating line segments
and arc sections
These are edges in the path graph. The endpoints of these<br>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<br>segments surfing edges, because the path uses them to surf between<br>obstacles. The arcs we’ll call hugging edges, as their purpose in<br>the path is to hug the sides of the obstacles.
Next we’ll explore a simple way to turn the obstacle forest into a<br>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<br>which just barely kiss both circles; these segments are known as<br>bitangents, and there are four of them for each<br>pair of circles. The bitangents which cross between the<br>circles are the<br>internal bitangents, while the ones which go along the outside are<br>the external bitangents.
Internal bitangents
Historically, internal bitangents were important for calculating the<br>length of a belt which crosses over two different sized pulleys, and<br>so the problem of constructing internal bitangents is known as the belt<br>problem. To find the internal bitangents, calculate the angle \(\theta\)<br>in the diagram below.
Overlapping circles have no bitangents
It turns out that, given circles centered on points \(A\)<br>and \(B\) with radii \(r_A\) and \(r_B\), and centers<br>separated by distance \(d\): \[\theta =<br>\arccos{{r_A+r_B}\over{d}}\] Once \(\theta\) is known, it's<br>easy to find points \(C\), \(D\), \(E\) and \(F\).
External bitangents
Constructing external bitangents—the pulley problem—uses a<br>similar technique.
Smaller circle entirely contained in larger one
For external bitangents we can find \(\theta\) like this:<br>\[\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<br>the diagram, \(\theta\) appears on the side of A toward B,<br>but on the side of B away from A.
Line of sight
Taken together, the internal and external bitangents between two<br>circles constitute surfing edges between the circles. But what if a<br>third circle blocks one or more of the surfing edges?
Circle blocks line of sight<br>A and B visible from each other
If a surfing edge is blocked by another circle, we...