Occasional error when using bake_navigation_polygon()

Godot Version

4.2

Question

I have a tilemap of various environmental objects such as trees and rocks. I’ve set it up so it randomly spawns a bunch of them. through the tilemap I’ve set the collisions.

Each ‘day’ a new set of objects is spawned and the navigation data is rebaked via bake_navigation_polygon(). This works about 75% of the time but occasionally it throws this error and no navigation data is baked:

E 0:00:19:0699   generator_bake_from_source_geometry_data: NavigationPolygon Convex partition failed. Unable to create a valid NavigationMesh from defined polygon outline paths.
  <C++ Source>   modules/navigation/nav_mesh_generator_2d.cpp:819 @ generator_bake_from_source_geometry_data()

The C++ source its referencing is as follows:

	if (tpart.ConvexPartition_HM(&tppl_in_polygon, &tppl_out_polygon) == 0) { //failed!
		ERR_PRINT("NavigationPolygon Convex partition failed. Unable to create a valid NavigationMesh from defined polygon outline paths.");
		p_navigation_mesh->set_vertices(Vector<Vector2>());
		p_navigation_mesh->clear_polygons();
		return;
	}

Does anyone have any insight on why this is happening and how to fix it? It’s unusual that it works most of the time. I feel like it has to be related to how the objects may have randomly been spawned that day but thats just my hunch. Any insight is appreciated.

Thanks

The 2D navmesh baking is done with polygon outline paths. Outline paths need to be converted to actual navmesh polygons. If outlines overlap or intersect the conversion does not work and this and similar errors are the result.

That said not all overlaps or intersections are equal. The navmesh baking first merges all the traversable outlines together, then merges all the obstruction outlines together, then intersects the two for the final result.

Because of the merge steps this means you can partly overlap outlines of the same type but you can not nest them fully inside each other. E.g. have a staticbody2d inside another staticbody2d has a high change of flipping the outline, turning surface into a hole or vice versa breaking the conversion to polygons.

Thanks for your help, I seen you were helping with similar issues years ago and appreciate you taking the time to write that out.

If I’m understanding correctly this is likely happening because when the environment is randomly generated, some of their colliders are intersecting in a way which causes the error.

If that is correct, I’m thinking the only way to really fix it is to add some logic to ensure that they do not spawn so close to each other, do you think that’s the best fix or is there something else worth trying?

Spawning not too close is one way but you need to make sure that your randomly generated shapes do not nest inside each other if they have more complex shapes.

I’m assuming its not taking the entire sprite into account, its just the collider, all of which are simple rectangles or pentagons.

I liked the density I had before but I think I might have to spread them out more to let the navigation bake do its thing.

If there is anything else I can do to keep the density I’m all ears but for now I think you answered my question, thank you again.

A Sprite2D is just a texture and is ignored as it has no parsable shape (and parsing pixels would create shapes that are useless due to being overdetailed).

MeshInstance2D, MultiMeshInstance2D, Polygon2D, StaticBody2D and TileMap are the node types that are parsed by the 2D navmesh baking.

I mean you can have density where your shapes partly overlap, you just can not stack them completely on top of each other or inside each other. E.g. have a small tree entirely inside a large tree due to the uncontrolled random placement. Depending on your used shapes you would need to Rect/AABB check and see that this is not the case.

I appreciate the further clarification, with your further clarification it hit me it likely wasn’t the random environment objects itself causing the problem, there was already some objects I was also baking pre-baked and the random generation did not take those into account so its very likely they just spawned right on top of one.

Regardless I now understand what I have to take into account, thank you very much again!