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?
