# Navmesh awkward path generation with string pulling due to "inner" vertices

I've identified a problem and a possible solution related to navmesh-based pathfinding. Before diving in, I'll preface my post with some questions to keep in mind as you read:

• Is this a known problem that people have solved before?
• Is there a term for the problem that could help me search for information related to it?
• Is the solution I came up with an existing idea? If so is there a name for the algorithm or some other search term I could use to find more information?
• Is there a better solution? If so, please point me to it.

For reference, I'm using images from http://jceipek.com/Olin-Coding-Tutorials/pathing.html#navigation-meshes and generally following the advice laid out there.

tl;dr of that blog post is

Decompose your walkable area into a navmesh, treating convex polygons as nodes and their borders as edges so that you can perform an A* search to get from point A to point B. To translate from "node ids" back to real points, use string-pulling.

Here's a copy of the example space:

And an example generated path after performing string pulling:

So far so good.

But I realized this approach generates an awkward path in a situation like this:

In this situation, a trio of nodes are all adjacent to each other, and so the A* will generally choose a path directly from the starting node to the ending node, despite an intuitive understanding that the agent can move in a straight line from A to B which travels through a different polygon.

I've been working on a solution to this problem and so far my best idea is to apply a transformation to the nav mesh. My description of this will be a little hazy as I'm making up terminology to describe the approach...

• Define a shared edge as a line segment that is shared by two convex polygons in the navmesh. Maybe a.k.a. a "portal" for string-pulling purposes.
• Define an inner vertex as a vertex in the navmesh for which all attached line segments are "shared edges". The vertex in the center of the three polygons in the image above is an inner vertex.
• Identify an inner vertex. Follow its attached shared edges to what I'll call neighbor vertex. (possible improvement; If the neighbor vertex is also an inner vertex, recurse to its neighbors until all of the neighbors are non-inner.)
• Remove all shared edges from the navmesh that were traversed in the previous step, forming a new polygon whose border is defined by the neighbor vertices in the previous step. Redefine the edges accordingly (I'll hand-wave that)
• Repeat until no inner vertices remain.

The result of this on the example above should result in this:

And with the same A-B path from before, the string-pulling should now result in a straight line:

I believe that as long as the navmesh has no inner vertices, all paths generated with the approach described in the linked blog post should seem "natural" and not have any surprise corners in what seems like open space.

Per my questions at the beginning of this post, I'm looking for more information, e.g. has anybody else solved this problem before, is there a better way to do it, and is there even a name/term for this problem?

The string pulling algorithm should use the walls as the borders, not the corners of Nav-Mesh intersections.

It's still possible to get a non-optimal path when eg. the pathfinder goes around an obstacle in a non-optimal way. This non-optimal nature of string-pulling is just something game developers need to live with. There are optimal algorithms, but they tend to be much slower.

Of note, there are also other fast approximation algorithms that don't rely on string-pulling.

• Can you walk us through the steps of the string-pulling algorithm you recommend here, including which walls should be provided to it as input? Commented Jun 1, 2020 at 19:36
• In order to use the walls as borders, doesn't that necessarily mean performing a raycast or some kind of graph iteration operation at each step of the path? If not that, how do I identify the walls to use for the string pulling? FWIW I'm not so much concerned with finding an optimal path as I am avoiding having the agent navigate around a corner that doesn't exist. Commented Jun 2, 2020 at 4:44
• @Dylan Yes, you use raycasts in string-pulling. Looking closer at the link, the algorithm they describe is not string pulling but "Simple Stupid Funnel". If you follow the link they give, the top comment in that article describes exactly the problem you're talking about here. In your linked article, they allude to it at the bottom and mention you should use steering behaviors to work around it. Commented Jun 2, 2020 at 5:09
• Ok I see digestingduck.blogspot.com/2010/03/… and the solution the author gives is to add a post-processing step to the A* which I presume would use raycasting to determine if it can skip nodes along the A* path. Commented Jun 2, 2020 at 23:31

This is not a problem with string pulling algorithm, but with A* algorithm.

For this non-grid graph, using midpoints of edges to calculate the distance(cost) is better than using midpoints of polygons.