Perfect navigation on the navigationmesh

[snipercup]

Currently, each chunk in the world is using it's own navigationmap, region and navigationmesh. To perfect it, we should change it so that there is one map, and each chunk has it's own region and navigation mesh. This will improve navigation, because at the moment, mobs cannot navigate beyond one chunk. It's not a huge problem, but we can still perfect it.

I created this issue to share my notes and insights so we may review this issue at a later moment.

Without the merged navigationmaps, the navigation meshes look like this:

With this proposed implementation, the navigationmeshes have perfect edges, causing them to be merged by the navigationmap.

I created this branch with my implementation as described above, but there's no guarantee the branch will exist in the future: https://github.com/snipercup/CataX/tree/navigationmesh

Although the implementation works, it causes the game to stutter. This is because now, the navigationmesh spans across chunks and is a lot bigger because of it. This increases the bake time and leads to low framerates. The frame time spiked at 180ms in the city. Without this implementation we get at most 30 frametime.

In my imlementation, this is the setup_navigation function:

# Setup the navigation for this chunk. It gets a new map and a new region
# You can fiddle with the numbers to improve agent navigation
func setup_navigation():
	# Use the default navigation map instead of creating a new one
	var navigation_map_id = get_world_3d().get_navigation_map()

	# The navigation region of this chunk is associated with its own navigation map
	# The cell size should be the same as the navigation_mesh.cell_size
	NavigationServer3D.map_set_cell_size(navigation_map_id, 0.1)
	
	# Adjust the navigation mesh settings as before
	navigation_mesh.cell_size = 0.1
	navigation_mesh.agent_height = 0.5
	# Changing the agent_radius will also make the navigation mesh grow or shrink.
	navigation_mesh.agent_radius = 0.2
	navigation_mesh.agent_max_slope = 46
	navigation_mesh.border_size = 1

	var chunk_overlap: float = 2
	# Define the AABB and offset
	var aabb_size = Vector3(
		LEVEL_WIDTH + chunk_overlap,
		MAX_LEVELS * 2,
		LEVEL_HEIGHT + chunk_overlap
	)
	var bounding_box_offset = Vector3(
		(chunk_overlap / 2) * -1,
		0,
		(chunk_overlap / 2) * -1
	)
	var aabbpos: Vector3 = Vector3(0,-12,0)

	# Set the baking AABB using mypos as the position
	navigation_mesh.set_filter_baking_aabb(AABB(aabbpos, aabb_size))
	navigation_mesh.set_filter_baking_aabb_offset(bounding_box_offset)

	# Create a new navigation region for this chunk
	navigation_region = NavigationRegion3D.new()
	add_child(navigation_region)
	# Set the default navigation map to the navigation region
	navigation_region.set_navigation_map(navigation_map_id)

This is the relevant part of the add_mesh_to_navigation_data function:

func add_mesh_to_navigation_data(blockposition: Vector3, blockrotation: int, blockshape: String):
	var block_global_position: Vector3 = blockposition# + mypos
	var blockrange: float = 0.5
	var extend: float = 1.0 # Amount to extend for edge blocks
	
	# Check if there's a block directly above the current block
	var above_key = str(blockposition.x) + "," + str(block_global_position.y + 1) + "," + str(blockposition.z)
	if block_positions.has(above_key):
		# There's a block directly above, so we don't add a face for the current block's top
		return
	
	# Determine if the block is at the edge of the chunk
	var is_edge_x = blockposition.x == 0 || blockposition.x == LEVEL_WIDTH - 1
	var is_edge_z = blockposition.z == 0 || blockposition.z == LEVEL_HEIGHT - 1

	# Adjust vertices for edge blocks
	var adjustment_x
	var adjustment_z
	if is_edge_x:
		adjustment_x = extend
	else:
		adjustment_x = 0
	if is_edge_z:
		adjustment_z = extend
	else:
		adjustment_z = 0

	if blockshape == "cube":
		# Top face of a block, the block size is 1x1x1 for simplicity.
		var top_face_vertices = PackedVector3Array([
			# First triangle
			Vector3(-blockrange - adjustment_x, 0.5, -blockrange - adjustment_z), # Top-left
			Vector3(blockrange + adjustment_x, 0.5, -blockrange - adjustment_z), # Top-right
			Vector3(blockrange + adjustment_x, 0.5, blockrange + adjustment_z), # Bottom-right
			# Second triangle
			Vector3(-blockrange - adjustment_x, 0.5, -blockrange - adjustment_z), # Top-left (repeated for the second triangle)
			Vector3(blockrange + adjustment_x, 0.5, blockrange + adjustment_z), # Bottom-right (repeated for the second triangle)
			Vector3(-blockrange - adjustment_x, 0.5, blockrange + adjustment_z)  # Bottom-left
		])
		# Add the top face as two triangles.
		mutex.lock()
		source_geometry_data.add_faces(top_face_vertices, Transform3D(Basis(), block_global_position))
		mutex.unlock()

I started this attempt because of this comment in our code:

# See also (Godot 4.3) https://docs.godotengine.org/en/latest/tutorials/navigation/navigation_using_navigationmeshes.html#baking-navigation-mesh-chunks-for-large-worlds
# We can try to align the edges for more seamless navigation
#If you know your final chunk size and the border size increase the bake bound by 2*border_size
#in general the border size should be large enough to have all the important source geometry from the neighbours included. If not enough geometry from the neighbour chunks is included or the border size is too small edges might end up not aligned again when baked. 
#a reasonable starting size is 10-15% of a chunk size as the border size but that all depends on how large your chunks are or how complex the geometry.

This is indeed how I implemented it. Specifically, the edges of the navigationmap of the chunk are extended beyond the chunk, then everything outside the chunk is discarded because of the AABB bounding box and offset. This is the way Godot suggest creating perfect edges. To move forward with this implementation, we will probably need to exclusively use the NavigationServer3D so everything is offloaded to the threads. This will be a complicated task, but I think we can do it. However, it does not guarantee that the framerate will be good afterwards.

Important: If we only use the NavigationServer3D, we cannot see the navigationmesh in debug mode anymore. As a workaround we'd need an implementation that allows us to use either nodes or the NavigationServer3D api and then export the game using the Navigationserver3D api since that one will have the most performance.

[snipercup]

Maybe we can pull it off in the next Godot update? This says that we can soon use collisionshapes for navigationmesh baking and navigationmap synchronization will happen outside the main thread so the impact will be a lot smaller: https://godotengine.org/article/dev-snapshot-godot-4-4-beta-1/

[snipercup]

We can try it pretty soon, when we upgrade to 4.4: godotengine/godot#100497