Seeker.StartPath returns wrong path

[Wildcard]

I’m once again ironing out kinks in the pathfinding in my game and it looks like I have hit a bit of a wall.

I’m building a tower defense game where the player can build walls, that (through navmesh cuts) restrict the path that the enemies can take. The player has to leave a path of a certain width open. I test this by having a seeker component on each spawn point, and by checking if every seeker has a valid path to my base.

Dummycode for starting this check:

AstarPath.active.navmeshUpdates.ForceUpdate();
AstarPath.active.FlushGraphUpdates();

for each spawnpoint {_seeker.StartPath(transform.position, target.position, OnPathCallback)}

And the in OnPathCallback I check the distance between ABPath.endPoint and originalEndPoint, if it’s smaller than 4 meters, that’s a success.

Works quite well, until it doesn’t. If you look at the picture below, the purple line is a simplified representation of the path that the agents that spawn at my spawner on the right take. It takes them a long time, but they manage to go all the way to my base. They do the right thing.

However, when I ask the seeker that sits on that very spawnpoint on the right, the StartPath doesn’t bother to take a big detour. It simply decides that it’s good enough to get to a point 10m away from the target and call it a day. See the tiny white sphere, that’s the ABPath.endPoint as delivered in the StartPath’s callback.

How can I get the Seeker to do a proper job?

[Wildcard]

Also, as a secondary question: You can see lots of areas that are not blue. I’m not talking about the cuts around e.g. the big rock or all the barricades, but for example to the left of the oil pump there’s a big, vaguely “<”-shaped patch, that’s not blue. Same with the ridge on the right.

I have loads of areas like that, most of them are where the ground (not terrain, but meshes) is a little higher. I’ve noticed that the agents generally traverse these areas with no issue, so it’s probably fine, but it makes debugging and tuning the graphs very hard if I can’t be sure that everything that’s not blue is not traversable. Is that probably just an issue with the nav meshes gizmos not drawing on top of everything?

[Wildcard]

It appears at least part of my problem is that I have teeny tiny bumps in my road, like here:

So my agents cannot traverse here because of that tiny sliver. At this point, I have already set the cell size to 0.05, and the WalkableClimb to 2m and the MaxSlope to 72. And still the agent can’t get over this.

Only when I increas the MaxSlope all the way to 90 does the gap close.

I went through the forum and found a post that was similar:

Issue with Recast Graph generating graphs

Hi Try using a tiled graph, that will reduce the memory consumption a lot. It might actually. Since the world is voxelized (think minecraft, but with smaller blocks), it might happen that the ground is placed a bit further up because the resolution was small, and the top of the box was rounded down to a value slightly lower than the real one. Since the y-resolution (cell height) is 0.4, there is a high probability that you will get some rounding errors since the max climb is 0.5 meters. Try…

But all the tipps there didn’t help. CellHeight is no long changeable but calculated. I tried reducing my graphs height, which was set too high anyway, in the hope that that would decrease the CellHeight and therefore maybe fix my issue, but no luck.

[aron_granberg]

It appears at least part of my problem is that I have teeny tiny bumps in my road, like here:

I don’t think that’s the issue.
In the screenshot it looks like the navmesh is just slightly below the terrain at that point, so it looks faded out. All connections look good though and the agents should be able to move across that bump.
You can adjust the opacity of the navmesh behind objects in the A* Inspector → Settings → Colors.

@Wildcard

Also, as a secondary question: You can see lots of areas that are not blue. I’m not talking about the cuts around e.g. the big rock or all the barricades, but for example to the left of the oil pump there’s a big, vaguely “<”-shaped patch, that’s not blue. Same with the ridge on the right.

What is your A* Inspector → Settings → Graph Coloring Mode set to? If it is set to Areas then each colored area is a connected component. Meaning, agents in one colored area can move anywhere in that area, but they cannot move to an area of a different color, because of some obstacle.

@Wildcard

for each spawnpoint {_seeker.StartPath(transform.position, target.position, OnPathCallback)}

This seems like it could be an issue. The Seeker is designed to only handle one path request at a time. If you send a path request and then immediately send another one, it will cancel the first one.

You might be interested in using the PathUtilities.IsPathPossible function instead. See PathUtilities - A* Pathfinding Project

[Wildcard]

Thanks for the quick reply and sorry for my late answer (I was knocked out sick for a couple of days).

I’m now using PathUtilities.IsPathPossible instead of Seeker.StartPath and so far that seems to work, is a lot quicker and seems to have resolved some issues.

For reference, I currently have the agent radius set to 1m, which requires the player to leave a gap of 2 units (which are 1.5m in my game) which generally works great.

However I still have the trouble with this particular bump.

Here, the player is able to place down a new barricade. The path can go around the cutout that was created for the small bump:

But here, the player can’t place the barricade, because the path to the player is interrupted by the little bump:

When bumping up the “Opacity behind objects” to 1 (which I seem to have to do at runtime, it’s always reset at scene start), I can now see that some areas are just hidden by geometry as you suggested, but at the bump there definitely is no nav mesh:

The bump remains cut out whether I rasterize meshes or colliders.

[Wildcard]

I tried working around it which seems to work, but I’d rather only do that if there’s no other way. Maybe showing you my workaround can explain what’s happening here?

This is the spot after starting the game and scanning the graph:

I then place a 2x2x2 cube right on top of my hole in the graph:

And then I scan the graph again. As you can probably see, there’s no hole anymore:

Hiding the cube to show there really is a nice solid nav mesh now:

I can workaround this issue as long as there are only a few instances like that in my maps, but if there’s any explanation that could fix the root issue that would be very much appreciated.

[Djebedia]

Hey! Have you solved your problem with inaccurate path provided by the seeker? I’ve got the same problem - it just decides that its fine to stop 100+m away from the target

[Wildcard]

In my case it seems to have been mostly down to certain areas not being properly covered by the graph.

As per my last post, I’m currently working around these issues:

• Applying “patches” (cubes) to wherever the graph has holes.
• Scanning the graph at start of the scene.
• Afterwards removing theses patches so they’re not actually visible.

From what I can see on your screenshot, you probably have a different issue. Good luck anyway

[Djebedia]

Oh, thanks for an instant reply )
And also have a good luck )

[aron_granberg]

Hi

Hmm. So I think what’s going on is that this small bumb has a large enough slope that the agent thinks it cannot stand there (exceeds the max slope on the recast graph settings), and therefore it marks that whole region as non-traversable.

[Wildcard]

It seems to be something like this, yes. The problem pops up in quite a few places, like here with the sidewalk gutter:

To better visualize how small the gap/slope actually is:

MaxSlope is set to 45 degrees, WalkableClimb to 0.4. When setting MaxSlope to 90, the problem disappears (just for demonstration, obviously this is not a solution):

Considering the slope is less than 0.2 high, and the Recast Graphs WalkableClimb is set to 0.4, should the character not be able to simply step over it? Setting the WalkableClimb to a higher value (2) doesn’t change a thing.

Does A* really consider any slope at an angle that’s steeper than MaxSlope as “not traversable”, no matter how tiny it is?

[aron_granberg]

@Wildcard

Does A* really consider any slope at an angle that’s steeper than MaxSlope as “not traversable”, no matter how tiny it is?

Yes, that’s correct. As long as it’s wider than one voxel/cell I think.
I have some ideas for how to change the rasterization process to ignore these tiny ledges, but it will take some experimentation. If you have separate collision meshes, I would recommend that you make those steps be a bit more like slopes, as a workaround.

Btw, which version of the package are you using?

[Wildcard]

Oh alright, that would absolutely explain it. I assumed slopes are ignored if the agent could just step over them. But I appreciate how complex the whole topic is (which is why I bought A* and didn’t even think of implementing my own pathfinding).

I’m using the most recent version straight from your website (4.3.48).

[aron_granberg]

Okay. I think it’s possible that a bug in previous versions had a side effect of making this case more manageable, because it made unwalkable surfaces walkable if they were only slightly above another walkable surface.