I’ve recognized an issue and a doable resolution associated to navmesh-based pathfinding. Earlier than diving in, I will preface my publish with some questions to bear in mind as you learn:

• Is that this a recognized downside that folks have solved earlier than?
• Is there a time period for the issue that might assist me seek for data associated to it?
• Is the answer I got here up with an present thought? If that’s the case is there a reputation for the algorithm or another search time period I may use to search out extra data?
• Is there a greater resolution? If that’s the case, please level me to it.

For reference, I am utilizing pictures from http://jceipek.com/Olin-Coding-Tutorials/pathing.html#navigation-meshes and usually following the recommendation laid on the market.

tl;dr of that weblog publish is

Decompose your walkable space right into a navmesh, treating convex polygons as nodes and their borders as edges as a way to carry out an A* search to get from level A to level B. To translate from “node ids” again to actual factors, use string-pulling.

This is a replica of the instance area:

And an instance generated path after performing string pulling:

Thus far so good.

However I noticed this strategy generates a clumsy path in a scenario like this:

On this scenario, a trio of nodes are all adjoining to one another, and so the A* will usually select a path immediately from the beginning node to the ending node, regardless of an intuitive understanding that the agent can transfer in a straight line from A to B which travels by a special polygon.

I have been engaged on an answer to this downside and to date my greatest thought is to use a metamorphosis to the nav mesh. My description of this shall be just a little hazy as I am making up terminology to explain the strategy…

• Outline a shared edge as a line phase that’s shared by two convex polygons within the navmesh. Perhaps a.ok.a. a “portal” for string-pulling functions.
• Outline an interior vertex as a vertex within the navmesh for which all hooked up line segments are “shared edges”. The vertex within the middle of the three polygons within the picture above is an interior vertex.
• Establish an interior vertex. Comply with its hooked up shared edges to what I will name neighbor vertex. (doable enchancment; If the neighbor vertex can also be an interior vertex, recurse to its neighbors till the entire neighbors are non-interior.)
• Take away all shared edges from the navmesh that had been traversed within the earlier step, forming a brand new polygon whose border is outlined by the neighbor vertices within the earlier step. Redefine the perimeters accordingly (I will hand-wave that)
• Repeat till no interior vertices stay.

The results of this on the instance above ought to end result on this:

And with the identical A-B path from earlier than, the string-pulling ought to now end in a straight line:

I consider that so long as the navmesh has no interior vertices, all paths generated with the strategy described within the linked weblog publish ought to appear “pure” and never have any shock corners in what looks like open area.

Per my questions at first of this publish, I am searching for extra data, e.g. has anyone else solved this downside earlier than, is there a greater approach to do it, and is there even a reputation/time period for this downside?