Add a "maximum path query search length" property to NavigationAgent

[Griiimon]

Describe the project you are working on

Encountered this problem in 2 of my projects already.

Describe the problem or limitation you are having in your project

Given a large enough world (either 2D or 3D) a pathfinding search may take very long ( over a second ) which leads to huge frame drops.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

I would like to have an option to set a maximum search time for pathfinding queries. I guess, it's not pratical to use actual duration (msecs) but it could also be maximum path length or cost. If the pathfinder exceeds the limit of the parameter it would instantly return ( can't reach target ).

This should give the developer better control over performance.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

An additional field in the Inspector for navigation agents.

If this enhancement will not be used often, can it be worked around with a few lines of script?

I'm afraid not.

Is there a reason why this should be core and not an add-on in the asset library?

It needs to be core.

[Calinou]

cc @smix8

Shouldn't you try to perform more but shorter pathfinding operations instead of trying to find a very long path once?

[smix8]

Path query performance can be measured by using the NavigationServer2D.map_get_path() function directly.

The NavigationAgent has far different things going on each update that can eat a lot of performance so it is not good to use it to judge the actual pathfinding performance.

If a single path query using this server function directly should take over a second that is a big red warning telling that the navigation map polygon setup used in that project must be blown out of any reasonable proportion.

I think this is a case of XY and the source of the performance problems must be elsewhere and this is not a proper way to solve this. Needs more project / debug info to see what is the real performance problem.

[Griiimon]

Shouldn't you try to perform more but shorter pathfinding operations instead of trying to find a very long path once?

Of course you should, but you don't always know in advance if the path is going to be longer than expected. And keep in mind that it only takes one long path (in a large world) to trigger a inacceptable stutter.

Take this example: I have a tilemap with 100k tiles with walls that make a maze-like level. Now an AI Enemy hears the player fire a gun 10 tiles away. It tries to find a path to him but he's actually behind a wall and the shortest way would take him around half the map on a path that is thousands of tiles long.

Obviously, I can run pre-checks. For example a raycast to see if there's a direct line of sight or a small dynamic a-star/dijsktra field around the Enemy to see if he can get there with an acceptable number of steps and only then actually use the navigation agent.

Problem solved right? Not quite. What if there are other dynamic obstacles in the way, like small rigidbody crates for example that where pushed there by the player for protection. They won't show up in the pre-check because it is tile-based and the crates can be moved around freely. Furthermore I can't exclude the whole tile in the pre-check because the might just be enough room for the enemy to squeeze through. I hope I'm painting a clear picture.

Now the pre-check was successful, which leads to the navigation agent trying to find a presumably short path but obstacles are in the way and the path leads through the whole maze to come up behind the player. Stutter! Again, if you're creating a little game jam entry with a tile map that fits on your screen this isn't a problem at all. I'm talking about a very large level.

Solution: Have a parameter for the navigation agent to keep its pathfinding scope in check. Keep in mind I want to get rid of the frame drops. I don't care if there actually is 1000-tile long path but the navigation agent can't find it. It would be a trade-off, but one that I've control over.

Another example in my 3D open-world project: The player stands on a cliff right above the enemy. The enemy can see him but can't get there in a straight line. The shortest path leads a around the mountain, is a few kilometers long and passes through hundreds of trees on the way. Stutter!

Now a possible work-around here is to do LOD navigation maps, with a less detailed one that doesn't include trees for example. But still, it only takes one very long path the pre-check doesn't catch.

Another work-around I haven't tried yet is building a chunk system of navigation regions and only activate a small number of regions per pathfinding call positioned around the paths origin, thus limiting the maximum possible path length.

The whole discussion wouldn't even be happening if the pathfinding could be run on a different thread, though. Maybe @smix8 can shed some light here, but at least with navigation agents I'm pretty sure the pathfinding runs on (and potentially blocks) the main thread even if set_target_location() is called from a thread. Not sure what would happen if you used NavigationServer.map_get_path() directly.

I'm not saying the navigation module isn't great and more than sufficient for the vast majority of use cases, it just could use a little more flexibility for the very small minority that isn't content with just making small platformers and mobile games using godot. An option to limit the path search length, which is turned off by default, doesn't seem that absurd to me.