Pathfinding returning suboptimal paths

I’ve been seeing strange results of pathfinding, where the calculated path seems to want to avoid crossing certain polygons on the navmesh, and as such takes long routes going via polygon vertices when it should be evaluating to a straight line. See for example the image below.

http://puu.sh/rjmPh/0ccc9e1173.jpg

The green line is the calculated path. I’m not using any nav areas or cost alterations of any kind. This appears to happen regardless of whether Regular or Hierarchical pathfinding is used. I actually noticed this back around 4.10/4.11, but haven’t touched this project since then. I’ve now updated to 4.13 and the issue persists.

Any ideas? This surely can’t be expected behavior.

Hey kamrann,

I’ve performed a couple of tests and noticed a slight issue with the pathfinding but nothing to the extent of what you’re seeing.

Would you mind zipping up your project and uploading it to Drive or Dropbox and providing me with a link so I can take a closer look at your setup? You can PM me the link on the forums: https://forums.unrealengine.com/member.php?160394-Sean-Flint

Thanks for providing a test project.

Try decreasing your Tile Size setting in Edit->Project Settings->Navigation Mesh and see if you get more accurate results.

I’d be interested to hear if that makes a difference in your actual project.

It makes the issue a little less obvious at the same scale, but it doesn’t fundamentally change anything. There are still cases where it seems to want to plot a path that passes directly through a tile vertex, when a more direct path exists.

I realize there will be some limits to the search algorithm to allow it to be fast enough, but this doesn’t look to me like it’s just expected behavior. Seeing an AI walk an angled path when there is nothing preventing it from walking in a straight line is going to be extremely obvious.

I’m not actively after a workaround or anything, this is just a prototyping project. But obviously if there’s an engine bug here I’d like it to be addressed.

Hey kamrann,

After speaking to our developers, I have a concrete answer for you:

This is technically not a bug. What’s happening is the path is straightened along the navigation corridor. If you have a tiled navmesh you end up with navpoly corners in empty, flat areas sometimes.

Currently, these are the types of paths you’re going to get on large empty areas.

There are two ways you can work around this behavior:

  1. Have more obstacles on your map. This will result in paths wrapping around the actual obstacles, not the ones artificially created to sub-divide the navmesh.
  2. This will only work in C++. Override UPathFollowingComponent::SetMoveSegment and whenever it is called do visibility or navmesh raycast tests to other points on the path to see if some of the segments can be skipped.

Hope that helps, and have a great day!

Thanks for looking into it Sean.
So it sounds like it’s the nature of my prototyping map that is making this issue apparent. I can certainly see that in most practical cases the terrain would be more complex and undulating.

That said, it still seems like a potential problem for cases such as interior environments, where the navigable area is necessarily flat. Anyway, I’m happy to ignore it for now and see if it becomes a non-issue once I’m working with more fleshed out levels.

Just to add a note about solution #2: If you are going to do this, you will want to make sure there is something for the raycast to hit over holes in the floor/navmesh.

Shocked that this quirk is still in the engine.