Funnel Modifier Generates Sub-Optimal Paths

[dnomn8r]

We have been using a Funnel modifier on a high resolution recast graph. It is generating some strange results, and the errors seem to be based on world space directionality.

In the above image, you can see the paths that a funnel modifier provides in a completely empty area.
The yellow circles are target locations, the yellow lines are paths that are straight, and the red lines are paths which have a corner in them.

I’ve circled a particularly bad case in yellow.

Now in an empty area, we would expect all lines to be yellow, as the paths should all be straight. We see that in the bottom right quadrant, but less so in other quadrants. This suggests something weird (floating point error?) is going with the algorithm.

Similar locations yield the same results, which show it’s not an issue with the graph itself. (see below)

My settings for these results are:

and the funnel/seeker setup is:

We have tried playing with all the different settings (“Split At Every Portal”, “Start/End Modifiers”, etc), all with similar results.

The problem is even worse for larger agents. Here are the results for a recast graph of an agent of size 5.

setup for agent of size 5.

[aron_granberg]

Hi

The funnel modifier will try to simplify the path quite a lot. I think in your case it doesn’t quite manage in many cases, because you have so many tiny tiles. I think you’ll get better resoluts with a larger tile size. I recommend somewhere between 64 and 256 for most scenarios.

Pathfinding in itself on recast graphs is not 100% isotropic. It uses some heuristics internally to do pathfinding quickly, and this can lead to some corners even in open areas. The funnel modifier usually removes all of these.

I am confused, however, because the funnel modifier literally has code to see if the path can be simplified to a single line, using a graph raycast. Are you using any tags or penalties that could be interfering?

[dnomn8r]

I am not using any tags or penalties. And unfortunately, using larger tiles causes other issues, especially near ramps. (it does help with the funnel stuff though)

This is what a ramp looks like at tile size 64.

and here it is at tile size 10 (which is what we are trying to use)

As you can see at tile size 64, the surface does not hug the geometry when going up, and also when going down, making the generated path be in the air. (the colliders match the visuals in this example)

I’d much prefer to use tile size 64 (it bakes much faster), but this ramp issue makes that not really be an option. Is this ramp behaviour expected, or are we doing something wrong?

[aron_granberg]

Hi

The navmesh is not designed to be super accurate on the y axis. Typically you’ll use a physics raycast to position the agent on the ground. The movement scripts can handle small deviations from the real surface.

[dnomn8r]

The problem with that, is that the path length returned will then be incorrect, and since we’re trying to limit movement of a unit (this is a turn based, x-com like game), by path length, (as in it can’t move to tiles further than X away), it can cause issues.

I guess I may be able to use the inaccurate Y axis results, possibly do a raycast downwards, along the path nodes, and reconstruct a path that DOES hug the terrain, and then do a path length on that result.

We can’t use the provided movement scripts, because we need to preview the potential path the agent would take, which is why we need an accurate path ahead of time

[aron_granberg]

Ah, I see.

@dnomn8r

I guess I may be able to use the inaccurate Y axis results, possibly do a raycast downwards, along the path nodes, and reconstruct a path that DOES hug the terrain, and then do a path length on that result.

Yeah, this is what I would recommend in that case. Sample it with even spacing, and do a raycast from every point.

Alternatively, you may choose to not care about the y coordinate at all, and just measure the distance from a top-down view. But that might not suit your game.

[dnomn8r]

I have tried this approach, and it “mostly” works. However, I had to do two things. First, I had to figure out the destination point (which needs to be on/near the graph).

Because the graph is not accurate on the y axis, the point received from physics raycast is too far from the graph (that is deep underground), and so to get the end point on the graph, you have to do the following (set the distance metric to be “ClosestAsSeenFromAbove”:

if (Physics.Raycast(new Ray(potentialPos + new Vector3(0, 10, 0), Vector3.down), out info, 100.0f, mask)) {

	NNConstraint constraint = new NNConstraint();
	constraint.tags = seeker.traversableTags;
	constraint.graphMask = seeker.graphMask;
	constraint.distanceMetric = DistanceMetric.ClosestAsSeenFromAbove();

	Vector3 pos = AstarPath.active.GetNearest(info.point, constraint).position;

	potentialPoints.Add(pos);
}

Now, this works to get the destination point. However, I did have to adjust the code inside in OffmeshLinks.cs to

bool ClampSegment (Anchor anchor, GraphMask graphMask, float maxSnappingDistance, out Anchor result, List<GraphNode> nodes) {
	var nn = cachedNNConstraint;
	//nn.distanceMetric = DistanceMetric.Euclidean;
	nn.distanceMetric = DistanceMetric.ClosestAsSeenFromAbove();
	nn.graphMask = graphMask;

otherwise, the NodeLink2 script will not connect the graph if the ends of it are at floor level (since the graph is actually well below floor level)

The links look like this from above

but from the side, it looks like this (not that the circled link is green after my code change)

My question is, is this an OK change? Is it ok to change it to DistanceMetric.ClosestAsSeenFromAbove() from Euclidean? It feels like a bit of a hack.

Thanks for your time.

[aron_granberg]

It will work, but it’s perhaps not great.

Can you try changing the Max Border Edge Length setting, or perhaps the Max Edge Simplification Error in the recast graph settings? To get some more detail there.

[dnomn8r]

I tried, and it helps sometimes. For example, it helps in this case where the original looks like

(the darker areas are the “depressions” in the graph)

if I reduce the max edge error from 50 to 2 and max edge error from 5 to 1, I get

which helps, but there is still a huge triangular depression in the middle

(here is a side view)

I’ve played with the settings, but I haven’t been able to get rid of this without reducing tile size significantly. (which brings back the original funnel inaccuracy problem at the start of this thread)

for example, if tile size goes to 64, we get really weird “breakages” in the graph. (circled in yellow)

[aron_granberg]

Typically, there are various obstacles that break up the navmesh and force it to add detail. With your open areas, this doesn’t happen.
Maybe a grid graph would be a better fit for you? Have you tried this?

[dnomn8r]

I have tried a grid graph. And it works great for 1x1 units.

It looks like this.

However, it doesn’t work with larger sizes. The following is for using a 1x1 grid graph with a agent of size 3. It uses the example traversal provider you have in Multiple agent types - A* Pathfinding Project .

as you can see, it properly keeps the larger 3x3 agent away from obstacles, however, it doesn’t handle edges of platforms, or ramps. A 3x3 unit standing at the edge of a platform would be poking over the edge. (or standing next to one, would be half inside the wall)

Here is what it looks like in a recast graph for a 3x3 unit. And that is the desired behaviour.

[aron_granberg]

Ah, yeah that’s a limitation of the traversal provider approach on that page. Checking all the connections in the ITraversalProvider is also possible, but it adds some extra code.
But you can do a similar thing that you do with recast graphs, and just have 2 grid graphs for the different agent sizes.

[dnomn8r]

That approach was what I tried initially (since the game is grid based, it made sense). However, the grid graph that is generated for a larger agent does not generate a similar result as a Recast graph for an agent of the same size.

Here is what a grid graph with an agent size of 3 looks like.

If you compare it to the 3x3 recast graph in my previous answer, you can see that the recast graph properly keeps the graph away from the walls/edges (circled in yellow). However, a grid graph for agents of size 3 goes all the way to the edges of the platform, and does not prevent an agent of size 3 from going up a ramp (while the recast graph proper does prevent it)

[aron_granberg]

Hi

You can use the erosion option instead. One erosion iteration will remove all nodes that are adjacent to any obstacles.

[dnomn8r]

Unfortunately, that doesn’t work.

A 2 wide ramp then becomes unwalkable for a 2x2 unit with erosion setting set to 1.

And offsetting the grid by 0.5 to make the ramp walkable creates issues elsewhere, as the rest of the level is grid aligned to a 0 offset.