2DNavigation pathing around obstacles with safe_velocity creates inconsistent and poor/broken movement w/ wide turns

[JoshuaWeissTBS]

Godot version

4.0 Alpha1

System information

Windows 10, 3070ti, i5-11600k, 32gb ram, 165hz monitor

Issue description

Navigation pathing around a static body results in wide turns instead of taking shortest path, and with certain arrangements of static bodies, the object will take a long time to move or fail to path around at all.

The velocity of the object is grabbed from the navigationAgent2d velocity_computed (safe_velocity) signal.

Examples of wide turn:

https://user-images.githubusercontent.com/44821795/153578540-5d724745-17dd-4ac2-825c-7b7b39b7458c.mp4

https://user-images.githubusercontent.com/44821795/153579081-b37ee862-77a8-463e-a89d-47bc7bbfc26c.mp4

Example of slow pathing (also finishes in the wrong spot):

https://user-images.githubusercontent.com/44821795/153579758-457f0fba-6f85-4f53-9b04-98029ebbae44.mp4

Steps to reproduce

Create a scene like this:

Set the character 2d's velocity to the safe_velocity returned from the velocity_computed signal from navigationAgent2D

const VELOCITY = 100000.0

func _ready():
    $NavigationAgent2D.set_target_location(get_node("../Waypoint").get_global_transform().origin)
    $NavigationAgent2D.set_radius(10)
    print($NavigationAgent2D.get_nav_path())
    $"Line2D".points = $NavigationAgent2D.get_nav_path()

func _physics_process(delta):
#   $NavigationAgent2D.set_target_location(get_node("../Waypoint").get_global_transform().origin)
    # Query the `NavigationAgent` to know the next free to reach location.
    var target = $NavigationAgent2D.get_next_location()
    var pos = get_global_transform().origin
    print($NavigationAgent2D.get_nav_path())
    $"Line2D".points = $NavigationAgent2D.get_nav_path()
    var vel = (target - pos).normalized() * VELOCITY
    $NavigationAgent2D.set_velocity(vel)

func _on_navigation_agent_2d_velocity_computed(safe_velocity):
    motion_velocity = safe_velocity
    move_and_slide()

Move the static body and their collisions around to view the interactions with the characterbody and its navigation.

Minimal reproduction project

PaperStrategy_Godot4.0.zip

[JoshuaWeissTBS]

Feel free to reply if you want more info or to inform me that im doing it wrong

[Scony]

Well, the NavigationObstacle2D node has the shape of a circle. Its radius is being estimated by default by finding the smallest circle that encloses a given shape. In your case, the radius of such a circle is very large and thus agent's movement looks weird. However, if you run your videos again and imagine such a big circle, you'll notice that actually, the agent behaves as expected - it walks in a circular path just to avoid the obstacle.

To me, the whole idea of estimating radius makes very little sense while it misleads everyone who tries to use the NavigationObstacle2D (including myself in the past). I've been discussing this matter with @AndreaCatania and as a result, I've implemented a manual radius setting for obstacles. IMO it should be enabled by default. At the same time the NavigationObstacle2D should probably be documented better.

[JoshuaWeissTBS]

@Scony That makes sense, however a manual radius setting for obstacles that are any shape but a circle still run into the same issues. Is there a way currently implemented to have a navigationAgent2D take the shortest path? Is the safe_velocity supposed be just for moving targets? To me it would make sense that the navigationObstacle2D uses it's parents collision shape rather than a circle.

[Scony]

@JoshuaWeissTBS the whole problem is that all agents (NavigationAgent2D, NavigationObstacle2D, NavigationAgent, NavigationObstacle) are forced to be circular due to RVO2 library we use for collision avoidance. In other words - agents must have some radius and only that radius matters from a collision avoidance perspective. Thus any collision shape must be converted to a circle at the end of the day.

So to sum up - for any collision shape but a circle, people will be running into confusion as usually, the auto-calculated radius will be too large (as in your case).

[AndreaCatania]

I been thinking at this issue in the past, and I thought that a solution could be an algorithm that decompose the shape into few spheres / circles. In this way, we still use the really fast circular shape, but better describing the obstacle shape.

[Scony]

@AndreaCatania it would still be very dependent on the time horizon - with its value being small and with large, complex obstacle approximated by lots of circles the agent would likely stuck.

The only way which would probably make sense in case of complex obstacles would be to introduce static obstacles (obstacles which don't move at all) which are baked into navmesh.

[AndreaCatania]

Hmm, yee, it's not a proper solution. However, static obstacles are already supported, and RVO should be used for moving things like characters, etc.. From the video it seems like the feature is miss used, since the platform should not be a dynamic obstacle but rather a static one.

I think the really issue here understand what's the confusion source and fix it 🤔

[AndreaCatania]

We may add a Warning on the Obstacle node: When it's add under a Static Body it's automatically disabled and a warning appears saying that it's not needed to add Obstacle on a static body, since the navigation mesh takes care to generate it.

[Hecksa]

I've been running into similar issues trying out the new navigation stuff myself, so for what it's worth you can add my name to the list of people who didn't initially understand that obstacle nodes 1) had to be circular and 2) were only necessary on dynamic obstacles, so I'd definitely have benefitted from the warning mentioned by @AndreaCatania .

However, I'm also confused by the assertions that the navigation mesh considers static bodies. When I use the example project linked above by @JoshuaWeissTBS and remove the NavigationObstacle nodes attached to the StaticBody walls, the agent just paths straight into the wall.

So, whatever the confusion is, I'm suffering from it too. Is there some step we're missing? In the original blog post for the navigation overhaul, there was a step to bake a navmesh, which...I'd expect to see for 2D as well, but I can't find an option for it?

[Liamen94]

In alpha7 I got a similar issue with the navigation region setted up in a navigation layer on a tilemap, the agent doesn't even try to avoid any collision.

https://user-images.githubusercontent.com/41145848/167669750-0256e6c7-c467-4827-a22f-cbdc438bd218.mp4

In the video i made it change direction with a timer when stuck, but you can see it is not trying to avoid collision. The barrel is an instaced scene, while other collisions are defined in the tilemap

[smix8]

For those 2D users that are still confused / missing the "baking" step from the tutorial. Baking is currently only for 3D. In 2D use a NavigationPolygon resource and draw you navigation polygon with the polygon drawtool that you get when you select the NavigationRegion2D (4.0) / NavigationPolygonInstance (3.5). If you do procedual stuff to create a correct and working navmesh in 2D use the "make_polygons_from_outlines()" function of the NavigationPolygon resource in the end.