The pathfinding algorithm A * is a powerful tool for fast generation of optimal paths. Usually, A * is demonstrated when navigating maps from grids, but it can be used not only for grids! It can work with any graphs. You can use A * to find the way in the world of round obstacles.
In original article all images are interactive.
How does one algorithm solve both these problems? Let's start with a brief description of how A * works.
Algorithm A *
Algorithm A * finds the best path
from the starting point to the ending point, avoiding obstacles along the way. He realizes this by gradually expanding many partial paths
. Each partial path is a series of steps from the starting point to some intermediate point on the road to the goal. In the process of working A *, partial paths are getting closer to the end point. The algorithm stops working when it finds the full path that is better than the remaining options, and this can be proved.
At each step of the algorithm, A * evaluates many partial paths and generates new paths, extending the most promising of many paths. For this, A * stores partial paths in a priority queue, sorted by approximate length
—the true measured path length plus the approximate remaining distance to the target. This approximation should be an underestimation
; that is, the approximation may be less than the true distance, but not more. In most pathfinding tasks, a good understated estimate is the geometric distance in a straight line from the end of the partial path to the end point. The true best path to a target from the end of a partial path may be longer than this straight line, but cannot be shorter.
When A * starts, the priority queue contains only one partial path: the starting point. The algorithm repeatedly deletes the most promising path from the priority queue, that is, the path with the shortest approximate length. If this path ends at the end point, then the algorithm has completed the task — the priority queue ensures that no other path can be better. Otherwise, starting from the end of the partial path that he deleted from the queue, A * generates several more new paths, making single steps in all possible directions. He puts these new paths back into the priority queue and starts the process again.
A * works with the graph
: a set of nodes
connected by edges
. In a grid-based world, each node represents a separate grid cell, and each edge represents a connection with neighboring cells to the north, south, east, or west.
Before you can run A * for a forest of round obstacles, we need to convert it to a graph. All paths through the forest consist of alternating segments of straight lines and arcs. They are the edges of the path graph. The end points of these edges become nodes.
The path through the graph is a series of nodes connected by edges:
Both segments and arcs are edges of a graph. We will call the transition edges
because the path uses them to transition between obstacles. The arcs will be called edge envelopes
, because their task along the way is to round the sides of the obstacles.
Next, we explore a simple way to transform a forest with obstacles into a graph: we will generate all possible transition edges and envelope edges.
Transition edge generation
The edges of the transition between a pair of circles are segments of straight lines that barely touch both circles; such segments are called tangents to two points
, and for each pair of circles there are four such tangents. The tangents to two points intersecting between the circles are called internal tangents to two points
, and those passing outside are called external
Internal tangents to two points
In the past, the search for internal tangents was important for calculating the length of a belt connecting two pulleys of different sizes, so the task of creating internal tangents to two points is called the belt task
. To find the inner tangents to two points, you need to calculate the angle
in the drawing below.
As it turned out, for circles with centers
whose centers are
we can easily find the points
Outer tangents to two points
When constructing external tangents (this is the pulley problem
), a similar technique is used.
For external tangents, we can find
It does not matter which of the circles is larger, A or B, but as can be seen from the figure,
is deposited on side A, closest to B, but on side B, furthest from A.
Line of sight
Taken together, the inner and outer tangents to the two points between the two circles form the edges of the transition between the circles. But what if one or more transition edges closes the third circle?
If the edge of the transition is blocked by another circle, then we need to drop this edge. To recognize this case, we use a simple distance between a point and a line
. If the distance from the transition edge to the center of the obstacle is less than the radius of the obstacle, then the obstacle overlaps the transition edge, therefore we must discard it.
To calculate the distance from the
to the line segment
use in the following way
First, let's calculate
is the fraction of the distance along the
in which the perpendicular intersects the point
Then we calculate the position