42
\$\begingroup\$

I read in Unity's path-finding documentation that they use convex polygons because there won't be any 'obstruction' between 2 points. Then they add their vertices as nodes along with starting and ending points and traverse them using A* algorithm to reach the required destination.

However, I do not understand what they mean by "no obstruction between 2 points". I tried to check the differences between concave and convex polygons but only the angle differences come up (in convex the interior angles must be less than 180 degrees)

\$\endgroup\$
1
  • 3
    \$\begingroup\$ "no obstruction between two points" is the definition of convex \$\endgroup\$ – Hagen von Eitzen Sep 19 '20 at 14:47
79
\$\begingroup\$

A convex polygon has a very nice property:

The shortest path between any two points in the polygon, or anywhere on its edges, is just the straight line between those points, and that line segment lies wholly within the polygon. So if your polygon represents a section of your level known to be obstacle-free, then you're guaranteed you can do the very simplest thing, walk straight from point to point, and it will work.

For a concave polygon, this isn't always true. Here's an example:

Concave polygon with a line crossing through a notch cut out of it

Our intrepid navmesh agent just wanted to cross from one edge of the polygon to another, but the simplest and shortest path to do so takes it outside the polygon - into potentially uncharted territory! We can't guarantee that's a safe place to go. It could contain impassable obstacles or hazards or higher-cost terrain, or even game-breaking glitches.

We can't know for sure that it's safe without consulting other polygons in the mesh, or erring on the side of caution and taking a longer path that stays wholly inside the polygon. But such a path could itself be hard to compute, if the polygon has many of these concave notches that we have to navigate around. All this means extra computational expense we'd love to avoid if we can.

But on the plus side, any concave polygon can always be decomposed into a finite set of convex polygons, bringing us back to the easy case. Now we can just find a sequence of polygon-to-polygon hops that takes us to our destination, and within each polygon, just navigate straight from our entry edge to our exit edge, with no risk of wandering into unsafe territory:

Same polygon, split into two convex halves, which can be traversed in two straight point-to-point segments without going outside the polygons' area.

This way, we pay a little extra cost when setting up our navmesh, breaking it into convex parts wherever we find a concave corner, and storing some extra polygons as a result. This investment pays dividends every time we do a pathfinding query, because now it can just do the simplest and most obvious thing and get a correct, working result, without handling all the special cases that concave polygons require.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.