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.

How does one algorithm solve both these problems? Let's start with a brief description of how A * works.

Algorithm A * finds

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

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

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

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.

The edges of the transition between a pair of circles are segments of straight lines that barely touch both circles; such segments are called

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

As it turned out, for circles with centers $$ and $$ and radii $$ and $$ whose centers are $$ :

$$

Having defined $$ we can easily find the points $$ , $$ , $$ and $$ .

When constructing external tangents (this is the

For external tangents, we can find $$ as follows:

$$

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.

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

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 $$ on $$ :

$$

Distance $$>/math> from $$ to $$ is the distance from $$ to $$ :

$$

Since $$ , the circle blocks the line of sight from $$ in $$ , and the edge must be discarded. If $$ , then the line of sight from $$ in $$ exists, and the edge should be left.

The nodes of the graph connect the edge of the transition with the envelope edge. In the previous sections, we generated transition edges. To generate edge envelopes, we start at the end point of the transition edge, circle the circle, and end at the end point of the other transition edge.

To find the set of envelopes of the edges of a circle, we first find all the transition edges that relate to the circle. Then create the edge envelopes between all the end points of the transition edges on the circle.

By generating transition edges, enveloping edges and nodes, and then discarding all overlapping transition edges, we can create a graph and start searching for a path using the A * algorithm.

The graph generation procedure considered by us works quite well to explain the algorithm, but in many aspects can be improved. Such improvements will allow the algorithm to spend less processor and memory resources, as well as handle more situations. Let's look at some of the situations.

You may have noticed that in the examples shown above, round obstacles did not overlap or even touch. If we assume that the circles can touch each other, then this slightly complicates the task of finding the way

Recall that tangents to two points can be found using this formula for internal tangents:

$$

and formulas for external tangents:

$$

When two circles touch each other or intersect, there are no internal tangents between them. In this case, $$ greater than one. Since the arc cosine value is outside the definition area $$ is not defined, it is important to check the intersection of circles before finding the arc cosine.

Similarly, if one circle is completely located in another, then there will be no external tangents between them. In this case, $$ is outside the range $$ , that is, does not have arc cosine.

If we allow the possibility of touching or crossing obstacles, then new cases arise in the calculations of the line of sight of the transition edges.

Recall the calculation $$ - the part of the distance along the transition edge, where the perpendicular to the point touches the edge. If touching the circles is not allowed, then the value of $$ is outside the interval $$ , that is, the circle cannot touch the edge, because for this it would need to touch one of the end points of the edge. This is not possible because the end points of the edge are already tangent to other circles.

However, if we allow the possibility of overlaying circles, then the values of $$ outside the interval $$ can overlap the line of sight along the edge. This corresponds to the cases when the circle is located beyond the end of the transition edge, but overlaps the end point or touches it. To track such cases mathematically, we

$$

When obstacles can touch each other or intersect, the edges of the edges can be blocked by obstacles as well as the edges of the transition. Consider the envelope edge in the figure below. If there is another obstacle around the edge, the edge is blocked and must be discarded.

To determine if the envelope of the edge is blocked by another obstacle, use the following method to determine the points at which two circles intersect. If the circles have centers at the points $$ and $$ and radii $$ and $$ , where $$ - the distance between $$ and $$ , then we first need to check a few cases. If the circles do not touch each other (i.e. $$ ),

are one inside the other ($$ ) or match ($$ and $$ ), the circles cannot influence the envelopes of each other's edges.

If none of these conditions are met, then the circles intersect at two points; if the circles are touching each other, then these two points coincide. Consider the

$$

Finding $$ we can find the angle $$ :

$$

If $$ is zero, the circles are tangent at the point $$ . Otherwise, there are two intersection points corresponding to the positive and negative $$ .

Next, we determine whether any of the intersection points between the start and end points of the envelope edge. If so, then the obstacle blocks the envelope of the edge, and we must drop this edge.Notice that we do not need to consider the case when the envelope edge is entirely inside the obstacle, because the cut-off line of sight for the transition edges has already dropped this edge.

After making changes to the computation of the tangents to two points and the line of sight for the transition edges and the envelopes of the edges, everything works correctly.

When calculating the navigation of a circular object in the world of circular obstacles, observations can be taken into account to simplify the solution of the problem. First, you can simplify the work by noting that the movement of a circle with a radius of

In general, the graph for the forest from $$ obstacles contains $$ transition edges, but since each of them needs to be checked for the line of sight with $$ obstacles, the total graph generation time is $$ . In addition, a pair of transition edges can lead to the creation of envelopes of edges, and each of them must be checked with each obstacle on the line of sight. However, due to the high efficiency of the A * algorithm, it usually looks only part of this large graph to create the optimal path.

We can save time by generating small parts of the graph on the fly during the execution of the A * algorithm, rather than doing all the work in advance. If A * finds the path quickly, then we will generate only a small part of the graph. We do this by moving edge generation to the

` neighbors () `

function. There are several cases. At the beginning of the algorithm, we need the neighbors of the starting point. These are the edges of the transition from the starting point to the left and right edge of each obstacle.

The next case is when A * just got to the point $$ on the edge of the obstacle $$ along the transition edge:

` neighbors () `

should return envelopes leading from $$ . To do this, we will determine which transition edges get out of the obstacle by calculating the tangents to two points between $$ and all other obstacles, discarding all those that are not on the line of sight. Then find all the envelope edges that connect $$ with these transition edges, discarding those that are blocked by other obstacles. We return all these edges around the envelope, saving the transition edges to return in a subsequent call to ` neighbors () `

.The last case was when A * went around the envelope edge along the obstacle $$ and he needs to leave $$ along the transition edge. Since the previous stage calculated and saved all the edges of the transition, you can simply find and return the correct set of edges.

The bends around the edges connect the transition edges relating to one circle, but it turns out that many of these edge envelopes are not suitable for use in an optimal way. We can speed up the algorithm by eliminating them.

The optimal path through a forest of obstacles always consists of alternating transition edges and envelopes of edges. Suppose we are entering the $$ and decide how to get out of it:

Log in via $$ means we're moving

First, note that A * handles each undirected edge $$ as two oriented edges, $$ and $$ . We can use this by marking the edges and nodes with orientation.

- Nodes $$ become nodes with orientation - clockwise ($$ ) or counterclockwise ($$ ) arrows.
- Non-oriented transition edges $$ become oriented edges $$ and $$ , where $$ and $<\; img\; alt\; =\; "\$\; q\; \$"\; data-tex\; =\; "inline"\; src\; =\; "https://habrastorage.org/getpro/habr/formulas/d68/cc4/926/d68cc4926bf74bae8fa3b51ca4a09ec8.svg"/>$ - this orientation and $$ means the opposite direction $$ .
- Non-oriented edges envelopes $$ become oriented edges $$ and $$ . This is where the filtering happens: we
*do not*turn on $$ and $$ "src =" https://habrastorage.org/getpro/habr/formulas/25d/534/1cb/25d5341cb2af330b3d0433fa55f5f537.svg "/> because the change of direction creates excesses ($$).

In our scheme, the node $$ turns into two nodes, $$ and $$ , it has an incoming transition edge $$ and outgoing transition edge $$ . If we hit the path via $$ , then you must go through the $$ , which will be either a transition edge $$ (via the envelope $$ ), or $$ (through the $$ ). We cannot exit By $$ because the direction of rotation changes this way, and we filter the envelope edge $$ .

Filtering out these sharpened edge envelopes from the graph, we increased the efficiency of the algorithm.

You can cut off partial paths, the last edges of which intersect the last but one edge of the transition.

See Game Programming Gems 2 , Chapter 3.10, Optimizing Points-of-Visibility Pathfinding, written by Thomas Young. This chapter deals with the clipping of nodes, not for circles, but for polygons.

Source text: [Translation] Search for the way among the round obstacles