Add method to Snap point to Navigation Mesh

[mrjustaguy]

Describe the project you are working on

Stealth Game, Wandering system

Describe the problem or limitation you are having in your project

If i tell a NavigationAgent to go to a Random 3d Point, the navigation will occasionally break because the agent cannot reach the Point, but thinks it can (is target reachable returns true, but can't get to the point unless the target desired distance is set to be much higher)

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

Snapping points to the Mesh would ensure that a given point is indeed theoretically reachable (so if the mesh is properly baked for the agent's movement capabilities), and it could also be used to improve navigation in general if you're able to assume that all the points are indeed on the navigation mesh and not above/below it, which could potentially also simplify navigation a little.

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

add function Snap_target_to_Navigation_Mesh (or something along those lines) This function would take the 3d vector of the target, and find the closest triangle it can snap to the surface of, from the Navigation Mesh.

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

Implementing Snapping manually, though not just a few lines of code, and this is general Navigation system UX improvement.

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

Navigation is Core.

[smix8]

assume that all the points are indeed on the navigation mesh and not above/below it

The navigation path positions are already limited to the navigation mesh surface.

The final position of the agent and last position in the navigation path array are also the closest reachable positions to the target position on navigation mesh.

[JBingrun]

I'm currently trying to achieve a snapping effect using GDScript, but after some experimentation, I've realized that map_get_closest_point doesn't necessarily provide the vertical intersection point. Instead, it gives a nearby point. To address this, I've been comparing the horizontal positions of the original object and the point obtained from map_get_closest_point.

https://github.com/godotengine/godot-proposals/assets/6387498/b2875c8b-e47e-424f-872d-ce08f46180c2

[mrjustaguy]

assume that all the points are indeed on the navigation mesh and not above/below it

The navigation path positions are already limited to the navigation mesh surface.

The final position of the agent and last position in the navigation path array are also the closest reachable positions to the target position on navigation mesh.

This is sadly, false. asking navigation_agent.target_position returns y values above and below the flat navmesh by quite a margin, and not snapped to the navmesh, which results in the agents getting stuck because they get to the point on the nav mesh, but the target distance is still too great to consider it a reached target, but the Agent thinks it can reach it...

This is why Low target distances result in agents getting stuck, it's because the points aren't actually all ON the nav mesh as they aren't properly snapped to it.

Both the end destinations should be snapped to the nav mesh, and the agent's coordinates should be snapped to the navmesh, which eliminates the need for target desired distance as a solution to prevent agents from getting stuck as it can be significantly reduced.

[smix8]

I've realized that map_get_closest_point doesn't necessarily provide the vertical intersection point. Instead, it gives a nearby point.

It compares the distance to the closest point on the faces of the navigation mesh polygons. All closest point functions in Godot also work with a small epsilon due to expected float errors. The same epsilon that e.g. is_equal_approx() uses by default.

This is sadly, false. asking navigation_agent.target_position returns y values above and below the flat navmesh

I see. That is expected as NavigationAgent.target_position returns whatever arbitrary position the user has set. That property is a path query parameter, not a part of the actual navigation path. As a user set query parameter it is not intended to receive any updates outside of user input. It also is required by internal logic that tracks this position with that property e.g. for repaths when pushed to far away from the current path segement or to query a new path to the original user intended target_position should the navigation map change.

In the actual navigation path the first, last and all positions between are on navigation mesh surface. If you need "my target_position snapped to navigation mesh" the NavigationAgent has the function get_final_position(). That function will return the closest position to the target_position on the reachable navigation mesh polygon faces. That will also be the last navigation path position so the other option is to check the last index of the current navigation path array.

[jkulawik]

I think I'm having the same issue. If I set a target that's at a certain height range, I can't predict if the target is actually reachable.

Example: navigation target is the purple box, and target_desired_distance = 1.0. White box is the final path position (get_final_position()), which is being reached within the specified pathing precision (path_desired_distance = 0.7 and is_navigation_finished() returns true).

The navigation agent gets softlocked because it considers the target as reachable (distance from final position is 0.9) but in reality it is not, because the distance from the agent (1.2) is bigger than target_desired_distance.

Things I tried that are unviable:

• Setting target_desired_distance to something higher - not very viable because it can affect other mechanics (in my game it's melee attack range)
• I've tried toying with path_height_offset, but it would only break navigation further
• Decreasing path_desired_distance - does not work because navigation breaks before achieving sufficient precision

I've tried around a dozen workarounds, and the only one that's not disastrous is to detect this softlock by checking when is_target_reached() returns false but is_navigation_finished() returns true. Then you can treat the target as reached or handle the softlock in some other way.

In my opinion, snapping a point to the navmesh is the only good solution, as it leaves the users the freedom to use it when it's necessary and leave it out when it's not. It shouldn't be too hard to implement, since it is something that is already done by the navigation server for the waypoints.

[jkulawik]

I gave the "get_closest_point" method a test. It's honestly not too bad for basic cases. And much more elegant than dealing with the softlock

[tudor07]

This feature would be great. Right now I am using the TileMap to implement something like this myself but it's very cumbersome.