godotengine / godotengine/godot
NavigationAgent3D finishes prematurely on dense NavigationMeshes when target_desired_distance < path_desired_distance
- Dominant language
- C++
- Stars
- 117k
- Forks
- 26.8k
- PR merge metrics
- PR metrics pending
Description
### Tested versions
- Reproducible on v4.4.1.stable.official [49a5bc7b6]
### System information
Godot v4.4.1.stable - macOS Sonoma (14.7.6) - Multi-window, 2 monitors - Metal (Forward+) - integrated Apple M3 Max (Apple9) - Apple M3 Max (16 threads)
### Issue description
When using a NavigationAgent3D to navigate a relatively dense NavigationMesh, with `NavigationAgent3D.target_desired_distance` significantly lower than `NavigationAgent3D.path_desired_distance`, the NavigationAgent3D can prematurely finish navigating far outside of the `target_desired_distance`.
The issue is in `NavigationAgent3D::_is_within_waypoint_distance()`, it only compares the waypoint against `path_desired_distance`, even when evaluating for the last waypoint.
https://github.com/godotengine/godot/blob/9b22b41531c82132732fda0f9818c5709c2587bc/scene/3d/navigation/navigation_agent_3d.cpp#L915-L919
The following change handles the case, and results in the navigation finishing significantly closer to the final waypoint.
```diff
@@ -854,7 +854,8 @@ void NavigationAgent3D::_move_to_next_waypoint() {
bool NavigationAgent3D::_is_within_waypoint_distance(const Vector3 &p_origin) const {
const Vector &navigation_path = navigation_result->get_path();
Vector3 waypoint = navigation_path[navigation_path_index] - Vector3(0, path_height_offset, 0);
- return p_origin.distance_to(waypoint) < path_desired_distance;
+ return p_origin.distance_to(waypoint) <
+ (_is_last_waypoint() ? target_desired_distance : path_desired_distance);
}
bool NavigationAgent3D::_is_within_target_distance(const Vector3 &p_origin) const {
```
### Steps to reproduce
See the MRP, but you use a dense navmesh, then using an agent with a low target_desired_distance (I'm using 0.15 in the MRP), attempt to navigate to a point that ends near multiple sections in the navmesh.
If you're using the MRP, just click the button. You'll see we stop well outside the `target_desired_distance`
EDIT: Improved sceenshots with player capsule position in first comment below. I forgot to include the capsule position in the label in the MRP.
With the patch above, applied to 4.4.1, we stop much closer:
### Minimal reproduction project (MRP)
[navigation-agent-finishes-early-issue.zip](https://github.com/user-attachments/files/21049700/navigation-agent-finishes-early-issue.zip)
Contributor guide
Research direction
Start in scene/3d/navigation/navigation_agent_3d.cpp, especially NavigationAgent3D::_is_within_waypoint_distance() and its handling of the last waypoint. Reproduce the behavior with the linked minimal reproduction project using a dense NavigationMesh and a low target_desired_distance. Done means navigation does not finish outside target_desired_distance when it reaches the final waypoint.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- game-dev
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 55/100