"Searched whole area but could not find target" error on simple pathfind

[Tony_Demetriou]

Hiya,
I’m loving A* Pathfinding - so much useful functionality!

I’m using a GridGraph, and quite often I’m getting “Searched whole area but could not find target” path errors. Often they’re really basic paths - the game world is very open, there are some slopes that need to be navigated around, but they’re relatively short. Some units are failing to find a path across open ground. It seems to be consistent, as in I can click on a specific spot and get this error each time I click, and then click on a nearby spot and get an immediately calculated path with everything working normally. After it starts moving, I can click on the first spot again, and it’ll often be able to find a path there without problems, presumably because it’s got a different starting point.

Looking at the graph, there’s nothing that should be blocking the units. I can see all the nodes are walkable, and I can see walkable edges. It’s obviously possible, since I can often get to the destination with a number of different clicks (often clicking further away just to get a valid path, then clicking back) - but in the end it reaches the exact point that was previously giving the error.

I’m using a procedurally generated terrain, and props with the “square obstacle”

I’m setting the units onto the navmesh with something like:
ai = GetComponent();
//ai.Teleport(transform.position, clearPath: true); return; // If I know they’re already somewhere walkable, because of procedural generation

var constraint = NNConstraint.None;
// Constrain the search to walkable nodes only
constraint.constrainWalkability = true;
constraint.walkable = true;

var info = AstarPath.active.GetNearest(transform.position, constraint);
var closestPoint = info.position; // I’d rather get the closest point, rather than the closest node, but this is good enough.
closestPoint += Vector3.up; // Lift by 1m, otherwise occasionally a unit will “fall through the ground”
ai.Teleport(closestPoint, clearPath: true);

Any hints would be greatly appreciated!

Thanks,
Tony

— Background, in case it’s useful —

We’ve recently swapped from using a Recast Graph to using a Grid Graph, because we’re using MapMagic2 to procedurally generate the game world as the player explores. The terrain doesn’t change shape during gameplay, but is only generated as the player approaches, so we can’t pre-bake the navmesh. We CAN bake the navmesh after the terrain is generated, either each time or the first time and cache or save it, but it doesn’t seem easy to incrementally update any of the graphs. I was having problems with the recast graph, where I couldn’t join new sections to the current navmesh, which is why I switched to the GridGraph.

It might be possible that I’m causing this problem, or can sidestep it by changing the type of graph or the way I’m initializing the units. I’m happy to do things differently if that’ll work better. I get the impression that both MapMagic 2 and Pathfinding are working really well, but making different assumptions about how we’ll use them, and I’m struggling to glue them together properly.

The GridGraph is correctly generating, and correctly rescanning as we move around the world - right now I’m just rescanning the whole grid, and I’ve looked at the procedural example, but for now I haven’t copied across the code to update just the edges like that. We’ve got other units in the world, so we’ll need a way to detect them so I can turn off their pathfinding as the grid moves away from them - ideas are welcome, otherwise I’ll write code to search for units in the area that’s being deactivated or just deactivate when they’re a certain distance away even if they’re still on the navmesh.

If there’s a way to generate a new “square” of navigation each time a square of terrain is generated, that would be perfect. Otherwise what I’m doing is working well enough, assuming I can figure out what’s causing this pathing issue.

I really liked the recast graph because it was able to tell me when the unit is at the “closest point” to the target - we have interactable items that are also obstacles, like a tree you can cut down, so it’s really useful to just set the target inside the tree and let the unit approach from any direction. That was nice, but I can find a manual solution using Grid Graph if needed.

Thanks!

[aron_granberg]

Hi

Do you happen to have a screenshot of your graph with annotations for where it happens?
It would also be useful to have a screenshot of the graph with the A* Inspector -> settings -> debug -> graph coloring set to ‘Areas’.

[Tony_Demetriou]

So of course, it’s working just well enough to make it difficult to get the examples!

I’ve got an “invisible” (visible with UI, not with a model) marker, and individual units that move around with the marker, but can move to specific targets.
I’ve listed an example of the error when I click to move the marker, as I’ve got more control over it than over the units.

When trying to move the marker to the water near the edge of the log.
Patherror: Searched whole area but could not find target

In scene:

In game:

When I clicked a bit further away, it worked, and you can see the in-game marker showing where I clicked.

This error reliably happened while I clicked on the ground near the log. Units can walk in the water (no pathfinding penalties for anywhere) and I’m not clicking on the log and can click in a relatively large area, from the ground around the end of the log through the foam in the pond. I’m not sure how large the area is because the error ends as soon as I click somewhere “valid” - from the scene view it looks like the “working” destination is still inside the same node.

(The other pathfinding targets are the units trying to walk inside the logs so they can collect them. Which doesn’t work, but usually pathfinds them to stand next to it. Occasionally they also error, whether or not they’re trying to move into an obstacle or to open ground.)

I find it somewhat perplexing, especially since it appears to be trying to pathfind from the same start and end node.

[Tony_Demetriou]

I can’t find any particular rhyme or reason - immediately after these examples, I could click on the point to make the marker move to the place that was originally failing. I can click around within this node without problems.
I can to move away to a different nearby node then back and sometimes get the same error, or sometimes get success. There doesn’t appear to be any difference when clicking in front of the obstacle or behind it, sometimes it’ll have trouble finding a straight line path to the near side of the log, other times it’ll easily zoom through (it doesn’t go around the log, no local avoidance for the marker, but units go around them)

I I’m 95% certain that I was getting this error before I put in any obstacles, and I can recreate the problem away from the obstacles (but usually where there are unwalkable slopes to make it trickier to navigate - yet still a viable path)

[Tony_Demetriou]

Here’s a good example of needing to do the “two step” pathfinding.

This was an open area of terrain, the slope is steep enough to force the pathfinding to go around, but it doesn’t look like a challenge to find a way up…

Clicking all around the target doesn’t work, in a fairly large area. I was clicking around that triangular rock, the left side is a different node and looks like it’s on a “break” that can’t be walked because of the slope. But clicking on the green area to the right or lower right also failed, and that looks like the middle of the walkable node.

But I can walk partway up the slope, then the rest of the way…

Once I’m up there, I still can’t move to the left of that triangular rock, you can see that I’m trying to travel across a slope that’s too steep, so it needs to go around.

Once again, I get the error when I click directly, but if I go partially around with one click, I can then go the rest of the way with a second click.

[aron_granberg]

I’m not sure…

It’s kinda hard to see the graph colors in those examples though, do you think you could enable ‘Show Surface’?

[Tony_Demetriou]

Sorry for the late reply, I didn’t see your reply earlier.

I’ve disabled the other units so there’s just the main marker moving, so we can better see where the pathfinding target is. You can see that the pathfinding target appears correctly where I’m clicking, but no line to show the path (because there isn’t a path) and the “Searched whole area but could not find target” error message is thrown.

I can click in other spots around that general location, usually with the same result.

Once I click in a “valid location”(??) it will pathfind correctly. I’m not sure what makes this location acceptable, as the previous screenshot looks like it’s closer to the target. We can also see that it’s picking a path that goes the wrong direction then loops back, which might be part of the issue (perhaps something to do with turning speed or going around corners, like how a vehicle might need to loop back if it can’t turn on the spot?)

Once I’ve travelled to this point, I can successfully pathfind to the original destination without problems

Another example of that “looping” effect where the units walk away from their target is when I first start the game. Three units are instantiated at the main marker, and given random destinations somewhere nearby. They usually walk directly there, occasionally they can’t find a path, but they also often find a long looping path that walks them far away then back even when they could have walked directly.

I think I see this with the starting units more just because it’s triggering three paths at the same time, so I’m three times as likely to see it. I don’t think there’s anything special about the way they’re being created or getting assigned the paths, because I do also see this effect at other times (such as when taking these screenshots, one time the pathfinder decided that it COULD get up there, by moving to the left and going around the other way, which is about 4 times longer.)

Here’s a wider shot of the terrain. The only thing that was stopping the pathfinder from going directly to the target is the slope of the hill.

Elsewhere, I’m also using square obstacles for some items like trees. Those little mushrooms do have a sphere collider trigger, but no square obstacles or non-trigger colliders. The pathfinder script does have collision testing turned on, but the mushrooms aren’t on the collision testing layer.

It’s worth mentioning that distance does not appear to be a problem - I’m generating a very large pathfinding map, and can click in the far distance and have it travel all the way there, around mountains and navigate between these different slopes. Other times I get this error because it fails on smaller seemingly simple paths. This spot where I did the example seems to reliably fail from this starting location to that target (and it’s easy to position between the mushrooms and aim for the triangular rock to recreate the problem) - it happens elsewhere, but is harder for me to remember the exact positions.

I’ve never seen a message about pathfinding failing when re-pathing an existing path. Sometimes a unit will walk one direction, then repath and walk a different direction, then repath back to the first path and get stuck forever going back and forward over the same area. But I never see an error come up.

[Tony_Demetriou]

Sorry for the thread bump - I’m wondering if you’ve had any chance to look at this, or any suggestions of what I could try?

Thanks!

[aron_granberg]

Hi

I really don’t know what could be causing this. Are you using multiple grid graphs or anything like that?
Are you modifying the graph in some way using code?

Which version are you using? You could try upgrading, it’s possible something has been fixed.

[Tony_Demetriou]

Thanks - I’ve made some strange partial progress with this problem!

Knowing it’s something you haven’t seen before still helps narrow it down
It also helps to know that it’s probably caused by something I’m doing, so I might be able to strip things down until I find the cause.

I’m using a single grid graph, but I am changing that graph centre and updating it during runtime.
I have “Scan on Awake” in addition to code that updates the graph when new terrain finishes generating.

I’d prefer to use multiple grid graphs, because MapMagic 2 generates terrain in “squares”, but I couldn’t walk between graphs so I switched to one large graph.

GridGraph graph;
...
graph.center = pos;
graph.UpdateTransform();
var guo = new GraphUpdateObject(new Bounds(pos, Vector3.one*900f));
guo.updatePhysics = true;
path.UpdateGraphs(guo);

I’m also occasionally triggering:

AstarPath.active.Scan(graph);

And when moving around the map I call for updates with:

var guo = new GraphUpdateObject(_bounds);
guo.updatePhysics = false;
AstarPath.active.UpdateGraphs(guo);
AstarPath.active.FlushGraphUpdates();

(Graph has width of 50 nodes and node size of 6, so 300 width - the 900 size is from when I was using multiple graphs so I could have 3x3 terrain blocks navigable)

I’m currently using 4.2.15 - I can try the beta. I couldn’t get the package manager update to work, but I can manually try it.

[Tony_Demetriou]

Here’s the weird progress…

The example I used above is now generating the graph differently, and I’m not getting the errors anymore.

I’m not sure if the errors have been fixed altogether, or if they still exist and this particular spot no longer gives an easy way to recreate them.

I haven’t changed anything in my code or scene, except for trying to install A* beta from the scoped registry. It shows in my project settings/packaged manager under scoped registry, and the “importing a new scoped registry” message appeared, but then Unity crashed and when I restarted it everything seemed like before. The normal package manager window still shows 4.2.15 and I don’t see any new files in my project. The Pathfinder component About also says 4.2.15

So I assume I’m still using the older version, and have no idea what could possibly have changed.

It’s successfully pathfinding around the gaps when going uphill, and “jumps” over the gaps to come downhill - so there’s more paths down the mountain than there are paths up the mountain. That’s great!

It means I can get into this “red” node, as long as I approach from above. But strangely, it seems to also want to create this path for one of the units, which looks like an invalid path to me (He wants to walk into the red node, but can’t cross from his current node into the next one. So he just keeps switching between that and a similar invalid path, walking back and forward)

I’m not overly worried about those invalid paths, they seem to be relatively rare, and I can probably nudge units around when they get stuck. I wanted to mention it here in case it’s linked with the pathfinding mystery.

Cheers