godotengine / godotengine/godot

NavigationAgent3D finishes prematurely on dense NavigationMeshes when target_desired_distance < path_desired_distance

Open
#108,261 5 comments 0 reactions 0 assignees View on GitHub
documentation topic:3d topic:navigation
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.

Image

With the patch above, applied to 4.4.1, we stop much closer:

Image

### 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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.