NavigationAgent2D does not apply radius settings around NavigationPolygonInstance in 3.5 beta 4

[nathanielhudson]

Godot version

v3.5.beta4.official [b6968ab]

System information

Windows 10

Issue description

Hello. Apologies if I've misunderstood anything and/or have made a stupid mistake here.

I have a NavigationAgent2D on which I am setting a radius. However, that radius does not seem to be affecting the paths provided by $NavigationAgent.get_next_location() and $NavigationAgent.get_nav_path(). The returned paths are hugging tight to corners and walls, whereas I would expect them to be offset by the radius value.

Steps to reproduce

Download and run the reproduction project. Despite a radius being set in the navigationagent (as confirmed with a print output), it hugs right to corners as if radius was 0.

Minimal reproduction project

Learning 3.zip

[Calinou]

Related to #60354 and/or #57486 (possible duplicate)?

[nathanielhudson]

Maybe? #60354 seems to show a 3D navmesh correctly baking the safety radius, but then the NavigationAgent3D is traveling outside the navmesh for some reason. #57486 seems to show a NavigationAgent2D responding in apparently suboptimal ways to a NavigationObstacle2D - although it is correctly using the radius to avoid the NavigationObstacle2D.

This issue is a NavigationAgent2D not employing the radius when navigating around a NavigationPolygonInstance. I'm not using any NavigationObstacle2D.

(Not saying they're not related under the hood, just wanted to document what I perceived the differences between the issues to be)

[Scony]

@Calinou I think the milestone for this one should be 3.5.

Regarding the issue itself, it's unrelated to 3D.

The issue here is due to the fundamental problem of 2D navigation in Godot which is: there is no baking stage.

In 3D for example, we have to bake navigation mesh before we can use it. One of the parameters we provide to the baking stage is agent_radius which actually should be called max_agent_radius. It tells the navmesh calculator what is the largest possible agent radius which can be used in the context of this particular navmesh. The navmesh calculator uses it to shrink the navmesh in a way that the largest agent will fit into the original geometry. So e.g. if we have a 10x10 plane and max_agent_radius=2 the resulting navmesh will be shrunk by 2 units in every direction, so it will be 6x6 so that every agent with R<=2 can safely walk 10x10 plane by moving its center within that 6x6 area.

In 2D navigation we have no baking stage and thus the user must take care of polygons himself. This is fine if one is creating navigation polygons from code, but the problem strikes if one uses a tilemap. In that case, one would have to introduce extra tiles with navigation margins which is so cumbersome that I consider it virtually impossible.

The only way to overcome this problem would be IMO to introduce a new option to the NavigationAgent2D so that it uses non-optimized paths for movement. In the case of tilemap the paths would go through tile centers like this (red line):

@nathanielhudson would such an option be satisfactory to you?

[Calinou]

I think the milestone for this one should be 3.5.

This sounds like a difficult problem to tackle for 3.5, so I'd prefer keeping the milestone to 3.x to not disappoint people in case this needs to be pushed back.

[Scony]

I think the milestone for this one should be 3.5.

This sounds like a difficult problem to tackle for 3.5, so I'd prefer keeping the milestone to 3.x to not disappoint people in case this needs to be pushed back.

ok, sounds reasonable

[nathanielhudson]

@Scony - Tile centers would be good for my use case, but it might be a problem for others - tile centers assumes that the tiles are approximately the same size as the agents - If I had small tiles and big agents, it may not work.

I feel that ideally we'd have either the navmesh or agent be smart enough to take the agent's radius into account. Spitballing here... it would be neat if the navmesh or agent could internally cache a modified version of the navmesh geometry contracted by the agents' sizes. For example, my 10px agent goes to make a path and creates a new version of the navmesh geometry offset_polygon-ed by 10px. If that agent asks for another path the cached geometry could be re-used. If a 20px agent asked for a path, a new version with a 20px offset would be created and cached. Don't know if that's too much complexity or would have weird performance implications though.

[Scony]

I feel that ideally we'd have either the navmesh or agent be smart enough to take the agent's radius into account. Spitballing here... it would be neat if the navmesh or agent could internally cache a modified version of the navmesh geometry contracted by the agents' sizes. For example, my 10px agent goes to make a path and creates a new version of the navmesh geometry offset_polygon-ed by 10px. If that agent asks for another path the cached geometry could be re-used. If a 20px agent asked for a path, a new version with a 20px offset would be created and cached. Don't know if that's too much complexity or would have weird performance implications though.

IMO that's only doable with baking stage implemented.

[nathanielhudson]

Fair. At risk of asking a dumb question, is there a reason why 2D has no bake?

[Scony]

Fair. At risk of asking a dumb question, is there a reason why 2D has no bake?

It was never implemented. Till 3.5 Godot navigation system was very straightforward.

[smix8]

@nathanielhudson
Until 2D gets an official baking implementation you can still bake your agent radius if you are feeling fancy as the 2D Navigation uses the 3D Navigation behind the scene in Godot 3.5 and 4.0 and your 2D navmesh is just a flat 3D navmesh.

E.g. get the NavigationMesh from your 2D NavigationPolygon resource. Convert the navmesh back to a "real" mesh for a meshinstance node that is a child of a NavigationMeshinstance / NavigationRegion3D and bake your agent. Then upload this navmesh to the NavigationServer3D with the map RID of your World2D / Navigation2D and the region RID of your NavigationPolygonInstance / NavigationRegion2D.

[viksl]

@smix8
Is there a way to use this workaround with a tilemap too, please?

[golddotasksquestions]

This is very disappointing. I have been avoiding the current Godot3 Navigation2D exactly because entities get stuck on corners and was hoping the new navigation solution in Godot 3.5 and Godot4 to solve this long standing issue. It's great we now have it built-into 3D navigation, but the vast majority of Godot users are still using Godot for 2D as recent poll shows.

[smix8]

The navigationmesh for both 2D and 3D edges are where the center of the actor can move. Users cannot place a collision wall at the actors center and expect things to work in both 2D and 3D.

EDIT
@viksl
No, the TileMap and TileMapEditor are both navigation abominations that create a single navregion for each tile and do not give access to all the create navregions on the NavigationServer. You are better off adjusting your Tile navigationpolygon by hand if you use TileSets.

[AlejandroMonteseirin]

I have the same problem in Godot 3.5.
Tile map navigation have problems because characters get stuck in corners or try to pass in 3px routes when they have a size of 100px. Also, navigationAgent avoidance radius only works with obstacles, not with the tilemap navigation.

My workaround was reducing the collision polygon of the walls. However, that create a lot of issues and create a strange feeling because the characters move too near to walls (especially in corners).

It will be nice if we can configure a radius for the navigation agent. Any other solution?

[smix8]

@AlejandroMonteseirin
The only solution is to fix your navpolygon by adding enough margin for whatever actor size should use the navigationmesh for pathfinding. The navigationmesh describes the safe-zone for the actors center position and is the baked result with all the information about collision / scene layout / actor size and not the other way around.

[timothyqiu]

As a workaround, you can set the navigatable area to be half the size of the tile (tile size minus double the character's radius to be precise):

Then set "Edge Connection Margin" to half the tile size (double the character's radius). It can be set in the project settings dialog at navigation/2d/default_edge_connection_margin, and also available on the Navigation node.

[stats]

That is a nice workaround. If you have all entities of the same size it may work great.

If you have entities of different sizes you may still have some issues. IMO NavigationAgent2D will still need to have a radius setting so that different sized agents can use the same navmesh.

[ka0s420]

Unfortunately that work around doesn't work for my situation, as the walls in my map are much thinner than the total tile size, so if i make a margin big enough to connect the little island navmesh pieces like you have in the gif above, then the agents can form paths through the walls. I'm also quite nonplussed at how you're able to get such uniform perfect navmeshes on ur tiles, I couldn't find a grid feature when trying to make mine. there is a snap feature, but no grid:

Also, yeah I have enemies of different sizes anyway

[smix8]

Working on 2D NavigationMesh Baking, progress see video below.

[smix8]

Added parser to bake a NavigationRegion2D NavigationPolygon from TileMap / TileSet

Works the same as NavigationRegion3D works with GridMap.

[hornetDC]

@smix8 any updates on this?

[smix8]

@hornetDC
Will be part of pr #70724 if you want to track it. It is not part of the pr yet as I did not have time to push the update from my local working branch yet.

[smks]

Hey! Just checking this will be in Godot version 3.*? I really would like to have this feature 🙏 (worries me that most commercial games would be using v3 at present and it isn't feasible to use Godot 4... yet).

[smix8]

@smks Godot 4.1+ only.

[Vivalzar]

1. This issue is marked as closed. Why? Is there new APIs? Because it seems it is still present in Godot 4.2.

2. And so, I tried to implement the workaround given here by @smix8. I used the example from the 2D Navigation Overview. I can't seem to make it work. The radius stays at 0. What am I missing?

Here is the code I'm using:

extends CharacterBody2D

var movement_speed: float = 20.0
var movement_target_position: Vector2 = Vector2(350.0, 190.0)

@onready var navigation_agent: NavigationAgent2D = $NavigationAgent2D
@onready var navigation_region: NavigationRegion2D = $"../NavigationRegion2D"

func _ready():
	# These values need to be adjusted for the actor's speed
	# and the navigation layout.
	navigation_agent.path_desired_distance = 4.0
	navigation_agent.target_desired_distance = 4.0

	# Make sure to not await during _ready.
	call_deferred("actor_setup")

func actor_setup():
	### MY ADDITION BELOW
	var navigation_map: RID = NavigationServer3D.map_create()
	var navigation_mesh: NavigationMesh = navigation_region.navigation_polygon.get_navigation_mesh()
	navigation_mesh.agent_radius = 10.0
	NavigationMeshGenerator.bake(navigation_mesh, self)
	NavigationServer3D.region_set_navigation_mesh(navigation_region.get_region_rid(), navigation_mesh)
	NavigationServer3D.region_set_map(navigation_region.get_region_rid(), navigation_map)
	NavigationServer3D.map_set_cell_size(navigation_map, 1.0)
	NavigationServer3D.map_force_update(navigation_map)
	navigation_agent.set_navigation_map(navigation_map)
	### MY ADDITION ABOVE

	# Wait for the first physics frame so the NavigationServer can sync.
	await get_tree().physics_frame

	# Now that the navigation map is no longer empty, set the movement target.
	set_movement_target(movement_target_position)

func set_movement_target(movement_target: Vector2):
	navigation_agent.target_position = movement_target

func _physics_process(_delta):
	if navigation_agent.is_navigation_finished():
		return

	var current_agent_position: Vector2 = global_position
	var next_path_position: Vector2 = navigation_agent.get_next_path_position()

	var new_velocity: Vector2 = next_path_position - current_agent_position
	new_velocity = new_velocity.normalized()
	new_velocity = new_velocity * movement_speed

	velocity = new_velocity
	move_and_slide()

[Vivalzar]

I could make it work eventually. Here is the solution I used:

func actor_setup():
	### MY ADDITION BELOW
	var radius: float = -10.0
	var tab: Array[PackedVector2Array]
	var polygon = NavigationPolygon.new()
	var outline = navigation_region.navigation_polygon.get_outline(0)
	tab = Geometry2D.offset_polygon(outline, radius)
	polygon.add_outline(tab[0])
	polygon.make_polygons_from_outlines()
	navigation_region.navigation_polygon = polygon
	### MY ADDITION ABOVE

	# Wait for the first physics frame so the NavigationServer can sync.
	await get_tree().physics_frame

	# Now that the navigation map is no longer empty, set the movement target.
	set_movement_target(movement_target_position)