3
\$\begingroup\$

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: initial example area

And an example generated path after performing string pulling: example area with a completed path from A to B

So far so good.

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

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:

Transformed navmesh

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

Transformed navmesh with fixed path planning

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?

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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? \$\endgroup\$ – DMGregory Jun 1 '20 at 19:36
  • \$\begingroup\$ 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. \$\endgroup\$ – Dylan Jun 2 '20 at 4:44
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Jun 2 '20 at 5:09
  • \$\begingroup\$ 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. \$\endgroup\$ – Dylan Jun 2 '20 at 23:31

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.