May 15, 2019 at 12:05

Finding a Way Among Round Obstacles

Original author: Amit Patel
  • Transfer

Forest navigation


A * Path Finder Algorithm is a powerful tool for quickly generating optimal paths. Usually A * is shown 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 your way in the world of round obstacles.


In the original article, all images are interactive.

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

Algorithm A *


Algorithm A * finds the optimal path from the start to the end point, avoiding obstacles along the way. He realizes this, 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, which is better than the remaining options, and this can be proved.

At each step of the algorithm, A * evaluates the set of partial paths and generates new paths, expanding the most promising path out of the set. To do 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 underestimated ; that is, the approximation may be less than the true distance, but not greater than it. In most path finding 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 the goal from the end of the partial path can be longer than this straight line distance, but cannot be shorter.

When A * starts, the priority queue contains only one partial path: the starting point. The algorithm repeatedly removes the most promising path from the priority queue, that is, the path with the smallest approximate length. If this path ends at the endpoint, 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 removed from the queue, A * generates several more new paths, taking unit steps in all possible directions. He puts these new paths back into the priority queue and begins the process again.

Graph


A * works with a graph : a set of nodes connected by edges . In a grid-based world, each node denotes a separate mesh cell, and each edge is a connection to neighboring cells to the north, south, east, or west.

Before we can run A * for the forest from round obstacles, we need to convert it to a graph. All paths through the forest consist of alternating segments of lines and arcs. They are the edges of the path graph. The endpoints of these edges become nodes.

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


Both segments and arcs are edges of the graph. We will call the segments the transition edges , because the path uses them to move between obstacles. We call arcs the enveloping edges , because their task along the way is to go around the sides of the obstacles.

Next, we will explore a simple way to transform a forest with obstacles into a graph: we will generate all possible transition edges and envelopes of the edges.


Transition Edge Generation


The edges of the transition between a pair of circles are line segments that barely touch both circles; such segments are called tangents to two points , and for each pair of circles there are four such tangents. Tangents to two points that intersect between the circles are called internal tangents to two points , and those that pass outside are called external .

Inner tangents to two points


In the past, the search for internal tangents was important for calculating the length of the belt connecting two pulleys of different sizes, so the task of creating internal tangents to two points is called the problem of belts . To find the internal tangents to two points, you need to calculate the angle$ \ theta $ in the drawing below.


As it turned out, for circles with centers $ A $ and $ B $ and radii $ r_A $ and $ r_B $whose centers are at a distance $ d $:

$ \ theta = \ arccos {{r_A + r_B} \ over {d}} $


Defining $ \ theta $we can easily find the points $ C $, $ D $, $ E $ and $ F $.

External tangents to two points


When constructing external tangents (this is the task of pulleys ), a similar technique is used.


For external tangents we can find $ \ theta $ in the following way:

$ \ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d} $


It doesn't matter which of the circles is bigger, A or B, but as you can see from the picture, $ \ theta $ laid on side A closest to B, but on side B farthest from A.

Line of sight


Taken together, the internal and external tangents to 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 transition edge is overlapped by another circle, then we need to discard this edge. To recognize such a case, we use a simple calculation of the 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, so we must discard it.

To calculate the distance from a point$ C $ to a straight line segment $ \ overline {AB} $we use the following method :

First, we calculate$ u $ - part of the distance along the segment $ \ overline {AB} $where the perpendicular intersects the point $ C $:

$ u = {(C - A) \ cdot (BA) \ over (BA) \ cdot (BA)} $


Then we calculate the position $ E $ on the $ \ overline {AB} $:

$ E = A + \ mathrm {clamp} (u, 0, 1) * (B - A) $




Distance $ d $ from $ C $ to cut $ \ overline {AB} $ Is the distance from $ C $ before $ E $:

$ d = \ | E - C \ | $


Because $ d <r $, the circle overlaps the line of sight of $ A $ in $ B $, and the edge must be discarded. If$ d \ ge r $then the line of sight of $ A $ in $ B $ exists and the rib should be left.

Edge Envelope Generation


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


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

Putting it all together


Having generated transition edges, envelopes of edges and nodes, and then discarding all overlapped transition edges, we can create a graph and start searching for the path using the A * algorithm.


Enhancements


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

Obstacles that concern each other


You may have noticed that in the examples shown above, round obstacles did not overlap and did not even touch. Assuming that the circles can touch each other, this complicates the task of finding the path

Two point tangents


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

$ \ theta = \ arccos {{r_A + r_B} \ over {d}} $


and formulas for external tangents:

$ \ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d} $


When two circles touch each other or intersect, then there are no internal tangents between them. In this case$ {r_A + r_B} \ over d $more than one. Since the value of the arccosine is outside the domain of definition$ [- 1, 1] $not defined, it is important to check the intersection of circles before finding the arccosine.

Similarly, if one circle is completely located in another, then there will be no external tangents between them. In this case$ {r_A - r_B} \ over d $ out of range $ [- 1, 1] $, that is, it does not have an arccosine.


Line of transition edge visibility


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

Recall the calculation$ u $- part of the distance along the edge of the transition at which the perpendicular to the point touches the edge. If touching the circles is not allowed, then the value$ u $ out of range $ [0,1] $, that is, the circle cannot touch the edge, because for this it would have to touch one of the end points of the edge. This is not possible because the endpoints of an edge are already tangent to other circles.

However, if we allow the possibility of overlapping circles, then the values$ u $ out of range $ [0,1] $can overlap the line of sight along the edge. This corresponds to cases where the circle is located beyond the end of the transition edge, but overlaps or touches the end point. To track such cases mathematically, we will limit$ u $ interval $ [0,1] $:

$ E = A + clamp (u, 0, 1) * (B - A) $


Envelope line of sight


When obstacles can touch each other or intersect, the envelopes of the edges can be blocked by obstacles in the same way as the transition edges. Consider the envelope edge from the figure below. If the envelope of the rib touches another obstacle, then the rib is blocked and must be discarded.


To determine if the envelope of the edge is blocked by another obstacle, we use the following method to determine the points at which two circles intersect. If circles have centers at points$ A $ and $ B $ and radii $ r_A $ and $ r_B $where $ d $ - distance between $ A $ and $ B $, for starters, we need to check several cases. If the circles do not touch each other (i.e.$ d> r_A + r_B $),
are one inside the other ($ d <| r_A - r_B | $) or match ($ d = 0 $ and $ r_A = r_B $), then circles cannot affect each other's envelopes.

If not one of these conditions is met, then the circles intersect at two points; if the circles touch each other, then these two points coincide. Consider the radical axis connecting the intersection points; it is perpendicular to the line connecting$ A $ and $ B $at some point $ C $. We can calculate the distance$ a $ from $ A $ before $ C $ in the following way:

$ a = {r_A ^ 2 - r_B ^ 2 + d ^ 2 \ over 2d} $


Finding $ a $we can find the angle $ \ theta $:

$ \ theta = \ arccos {a \ over r_A} $


If $ \ theta $ is zero, then the circles touch at $ C $. Otherwise, there are two intersection points corresponding to positive and negative$ \ theta $.


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

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

Variable actor radius and Minkowski extension


When calculating the navigation of a round object in the world of circular obstacles, one can take into account observations that simplify the solution of the problem. First, one can simplify the work by noting that the movement of a circle of radius r through the forest is similar to the movement of a point through the same forest with a single change: the radius of each obstacle increases by r . This is an extremely simple case of applying the Minkowski sum . If the radius of the actor is greater than zero, then before starting, we simply increase the size of the obstacles.

Deferred Edge Generation


In general, a graph for a forest from $ n $ obstacles contains $ O (n ^ 2) $ transition edges, but since each of them needs to be checked for line of sight with $ n $ obstacles, then the total graph generation time is $ O (n ^ 3) $. In addition, pairs of transition edges can lead to the creation of envelope edges, and each of them must be checked with each obstacle for the line of sight. However, due to the high efficiency of the A * algorithm, it usually looks at 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 a function neighbors().

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

The next case is when A * just got to the point$ p $ on the edge of an obstacle $ C $along the transition edge: neighbors()should return the envelopes of the edges leading from$ p $. To do this, we determine which transition edges go out of the obstacle by calculating the tangents to two points between$ C $and all other obstacles, discarding all those that are not in line of sight. Then we find all the envelopes of the edges connecting$ p $with these transition edges, dropping those that are blocked by other obstacles. We return all these envelopes of the edges, saving the transition edges for return in a subsequent call neighbors().

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

We cut off the pointed envelopes of the ribs


Envelope ribs connect transition edges touching one circle, but it turns out that many of these envelope ribs are not suitable for use in an optimal way. We can speed up the algorithm by eliminating them.

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


Login through $ A $means we are moving clockwise ($ \ circlearrowright $) We must exit through the node, which allows us to continue to move clockwise ($ \ circlearrowright $), that is, we can only exit through the node $ B $ or $ D $. If you exit through$ C $then an inflection ($ \ curlywedge $) ways that will never be optimal. We need to filter out such pointed edges.

First, note that A * processes each non-oriented edge anyway.$ P \ longleftrightarrow Q $ like two oriented edges $ P \ longrightarrow Q $ and $ Q \ longrightarrow P $. We can take advantage of this by marking the edges and nodes with orientation.

  1. Knots $ P $ become nodes with orientation - clockwise ($ P \ circlearrowright $) or counterclockwise ($ P \ circlearrowleft $) arrows.
  2. Unoriented transition edges $ P \ longleftrightarrow Q $ become oriented edges $ P, p \ longrightarrow Q, \ hat {q} $ and $ Q, q \ longrightarrow P, \ hat {p} $where $ p $ and $ q $ Are orientations, and $ \ hat {x} $ means the opposite direction $ x $.
  3. Unoriented Rib Envelopes $ P \ longleftrightarrow Q $ become oriented edges $ P \ circlearrowright \ longrightarrow Q \ circlearrowright $ and $P\circlearrowleft \longrightarrow Q\circlearrowleft$. This is where filtering occurs: we do not enable$P\circlearrowright \longrightarrow Q\circlearrowleft$ and $P\circlearrowleft \longrightarrow Q\circlearrowright$, because a change in direction creates kinks ($\curlywedge$)

In our circuit, the node $A$ will turn into two nodes, $A\circlearrowright$ and $A\circlearrowleft$it has an incoming transition edge $\longrightarrow A\circlearrowright$ and outgoing transition edge $A\circlearrowleft \longrightarrow$. If we hit the road through$A\circlearrowright$then should exit through the node $\circlearrowright$which will be either a transition edge $B\circlearrowright \longrightarrow$ (through the envelope edge $A\circlearrowright \longrightarrow B\circlearrowright$), or transition edge $D\circlearrowright \longrightarrow$ (through the envelope edge $A\circlearrowright \longrightarrow D\circlearrowright$) We can not get out through$C\circlearrowleft \longrightarrow$, because the direction of rotation will change this way, and we filtered the envelope of the edge $A\circlearrowright \longrightarrow C\circlearrowleft$.

By filtering out these pointed envelopes of edges from the graph, we increased the efficiency of the algorithm.

Cutting off intersecting edges


Partial paths can be cut off, the last edges of the transition of which intersect the penultimate edge of the transition.

Polygonal obstacles


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

Reference materials


Tags:

Also popular now: