The World is Not A Round, Spherical Place

AI characters need a way to get around the world, and we considered three ways to let them do this. The first was local avoidance, but this can very easily devolve into dithering unless the level is specifically designed to prevent it. As such we decided to do actual path finding, the only decision left being whether to use a node graph or a navigation mesh. We decided to go with a navigation mesh based on the recommendations of this article. I'll summarize the relevant points here.

Using path nodes would require the traversable space of the world to be defined either by 1-dimensional points or circular areas defined as radii from a 1-dimensional point. Which means an area like this:
Would have to be defined either like this:
or like this:
I'm not even going to try to draw all the edges on that one. The problem with the second method should be obvious: there are far too many path nodes. But using so many overlapping path nodes is the only way to cover all the space that we want to be traversable using circles. The packing efficiency of circles sucks. And if there are too many nodes, there are way, way too many edges. The problem with the first solution is that it doesn't cover all the traversable terrain (again, packing efficiency sucks). Which means, even if we let the AI off of pathfinding when it is in radius of a path node, there is still plenty of space where it is stuck on a single line path.

Now, the same area defined with a navigation mesh would look like this:
Our navigation mesh has 36 polygons, and covers much more of the traversable area than our many path nodes method, which had 44 path nodes. And as long as we only use convex polygons it's almost trivial to determine if the AI is within a polygon, and which one. We can still do all the interesting stuff that path nodes can, such as applying weight modifiers to certain polygons or running A* on it, pretty much anything we can do with path nodes we can do with a navigation mesh. We can even put paths within the navigation mesh that may have affinity modifiers, such as a sidewalk that people may prefer to walk on rather than the grass, which would reduce the cost of the using those polygons in an A* algorithm.