`GridMap`: Attempted to merge a navigation mesh triangle edge with another already-merged edge

[tavurth]

Godot version

4.0.rc3.official.7e79aead9

System information

Mac

Issue description

When using NavigationMesh and GridMap, an error is shown on each start:

ERROR: Attempted to merge a navigation mesh triangle edge with another already-merged edge. This happens when the current `cell_size` is different from the one used to generate the navigation mesh. This will cause navigation problems.

@tool
extends Node3D

func _ready():
    var map = ResourceLoader.load("level.tres").build()
    self.add_child(map)

    var child: GridMap = map.get_child(0)

    var lib: MeshLibrary = child.get_mesh_library()
    var items = lib.get_item_list()

    for id in items:
        print(lib.get_item_navigation_mesh_transform(id))

    var map_id: RID = child.get_navigation_map()

    print(child.get_cell_size())
    NavigationServer3D.map_force_update(map_id)
    NavigationServer3D.map_set_active(map_id, true)

    print(NavigationServer3D.map_is_active(map_id))
    print(NavigationServer3D.map_get_regions(map_id))

The above outputs:

[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
[X: (0.9, 0, 0), Y: (0, 1, 0), Z: (0, 0, 0.9), O: (0, 0.125, 0)]
(0.25, 0.25, 0.25)
true
[]
ERROR: Attempted to merge a navigation mesh triangle edge with another already-merged edge. This happens when the current `cell_size` is different from the one used to generate the navigation mesh. This will cause navigation problems.
   at: sync (modules/navigation/nav_map.cpp:692)

As can be seen above, the nav-meshes are not touching each other.

They are also unique, although I would prefer to use the same nav-mesh over and over.

Steps to reproduce

1. Download the project below
2. Run the project

Minimal reproduction project

test-navmesh.zip

[tavurth]

Possibly related:

https://github.com/godotengine/godot/issues/72188

[smix8]

That is not a valid navigation mesh in your screenshot. Same issue as in the linked issue.

A navigation mesh can not have a volume, it needs to have flat surfaces.

[tavurth]

@smix8 Hmm, how does the NavigationMesh.create_from_mesh work then?

[smix8]

As the documentation mentions the create_from_mesh() function copies over the vertices and indices from the mesh resource.

What it does not do is validate the mesh data for a navigation mesh or bake.

[tavurth]

I also added a hand-built grid-map with navigation meshes built in this way:

If that's not the correct way to do this, then it's very confusing 🤔

test-navmesh.zip

[Zireael07]

I'm with @tavurth here, this is confusing, I planned to use a navmesh for my city - which is proc-gen - once 4.1 rolls around.

At the very least, the docs NEED to mention the "no volume" limitation

[tavurth]

As the documentation mentions the create_from_mesh() function copies over the vertices and indices from the mesh resource.

Ok I'm still confused 🤔

So I should only be using the top surface of the mesh to build a navmesh?

[smix8]

@tavurth You can export your MeshLibrary with a setup like in the documentation that you can find here https://docs.godotengine.org/en/stable/tutorials/3d/using_gridmaps.html#navigationmeshes where you already baked the navmesh on the NavigationRegion3D.

You can also create a simple bake scene with just a NavigationRegion3D and a NavigationMesh with agent radius 0 and add the content of your GridMap cell below and bake the navmesh. Now save the navmesh to a file and add it to your GridMal MeshLibrary item.

Basically as the navmesh of your grid cells you only want to have the "ground" as a navmesh baked at zero agent radius else you will have seams due to the grid layout.

In general I would suggest to not use the cell baked navigation if you want agent radius cause the GridMap has the same issues as TileMap in that you can not shrink the navigation meshes on a tile / grid layout without causing seams. It is better to have a NavigationRegion3D as a parent that bakes a (secondary?) GridMap that has only those cells that should be used for navigation.

@Zireael07

At the very least, the docs NEED to mention the "no volume" limitation

A navmesh describes the traversable surface. This is already added in multiple places in the navigation documentation.

[tavurth]

You can also create a simple bake scene with just a NavigationRegion3D and a NavigationMesh with agent radius 0 and add the content of your GridMap cell below and bake the navmesh. Now save the navmesh to a file and add it to your GridMal MeshLibrary item.

Hmm I didn't understand this exactly, as a NavMesh does not exist as a Node but rather as a Resource.

I created a new plane instance and moved it to the top of my Mesh:

Then create the navigation mesh:

And move the NavigationRegion to be just below the main floor Mesh:

And export as a MeshLibrary:

Why are these purple triangles appearing? 🤔

Also the following code:

func _ready():
    for map_id in NavigationServer3D.get_maps():
        prints("MAP ID", map_id)
        print(NavigationServer3D.map_is_active(map_id))
        print(NavigationServer3D.map_get_regions(map_id))

Outputs nothing:

MAP ID RID(597000454144)
false
[]

test-navmesh.zip

[tavurth]

In general I would suggest to not use the cell baked navigation if you want agent radius cause the GridMap has the same issues as TileMap in that you can not shrink the navigation meshes on a tile / grid layout without causing seams. It is better to have a NavigationRegion3D as a parent that bakes a (secondary?) GridMap that has only those cells that should be used for navigation.

Ok so this is working at runtime now? Last time I checked it was broken from threading concerns.

If that does work, I guess I can add a GridMap below the NavigationRegion3D and bake at map export time.

[tavurth]

@smix8

https://docs.godotengine.org/en/4.0/tutorials/navigation/navigation_using_navigationmeshes.html#navmesh-for-3d-gridmaps

This is exactly what I'm doing at the moment 🤔

And yet this code from the docs generates a NavMesh with volume, since this is a 3D grid map 🤔

[smix8]

@tavurth

Please edit your last post when you want to add something while no one has responded.

• Add a NavigationRegion3D
• Add a NavigationMesh on the NavigationRegion3D
• Set the agent_radius to 0 on the NavigationMesh
• Add a MeshInstance3D with a Plane Mesh the size of your GridMap cell box and move the plane to the box ground level.
• Hit bake and use that NavigationMesh resource on your GridMap MeshLibrary item.

The NavigationServer syncs on the physics update. If you query the server get_maps() in a _ready() function you are querying an empty server without maps. Doc about NavigationServer synchronization

The code snippet for the procedual GridMap navigation was made for a GridMap using plane meshes, not box meshes or any other shaped mesh. This needs to be added to the explanation.

Why are these purple triangles appearing?

Those are the debug visuals for edge connections. If only single triangles show up it means the other half of the connection is missing due to broken edge merge. In that case the other half is on other sides of the box meshes.

Threaded navigation mesh baking is currently not possible in master or Godot 4 dev3 due to the recent SceneTree threading changes. The fix has not been merged yet https://github.com/godotengine/godot/pull/77412

[tavurth]

Please edit your last post when you want to add something while no one has responded.

Ok 👍

If you query the server get_maps() in a _ready() function you are querying an empty server without maps.

Aha that makes sense, changed to the following and it displays:

func _ready():
    await NavigationServer3D.map_changed

    for map_id in NavigationServer3D.get_maps():
        prints("MAP ID", map_id)
        print(NavigationServer3D.map_is_active(map_id))
        print(NavigationServer3D.map_get_regions(map_id))

[RID(618475290624), RID(639950127105), RID(648540061698), RID(657129996291)]

~- I'm still unsure what these pink triangles are, I didn't see them in any of the docs images, is that normal?~

Those are the debug visuals for edge connections. If only single triangles show up it means the other half of the connection is missing due to broken edge merge. In that case the other half is on other sides of the box meshes.

Aha I missed this edit. So the triangles are correct, there should be one on each side of the gridmap here as shown.

In general I would suggest to not use the cell baked navigation if you want agent radius cause the GridMap has the same issues as TileMap in that you can not shrink the navigation meshes on a tile / grid layout without causing seams. It is better to have a NavigationRegion3D as a parent that bakes a (secondary?) GridMap that has only those cells that should be used for navigation.

• I'm still unsure how to proceed with this suggested approach, perhaps you know of some relevant documentation?

I have compiled the sample here for others to use as a reference:

test-navmesh.zip

Suggestion

Perhaps NavigationMesh.create_from_mesh could automatically figure out the faces closest to the UP_VECTOR and use those for baking to avoid this volume issue?

[smix8]

I'm still unsure how to proceed with this suggested approach, perhaps you know of some relevant documentation?

Don't use navigation meshes inside the GridMap MeshLibrary. Instead, place a(nother?) GridMap below a NavigationRegion3D node with the single purpose of having all the cells that should have navigation mesh.

This GridMap should only have cells that should have navigation meshes as the NavigationRegion3D will parse them. You can control if visual meshes or collision shapes or both are parsed with the NavigationMesh geometry property that you added to the NavigationRegion3D. Prefer collision shapes as those are faster to parse and bake.

Bake a navigation mesh for the entire GridMap so the mesh can shrink to agent size without seams between your cells. This is both better for pathfinding quality and performance compared to having a single navigation mesh for every single GridMap cell.

Perhaps NavigationMesh.create_from_mesh could automatically figure out the faces closest to the UP_VECTOR and use those for baking to avoid this volume issue?

That is what the navigation mesh baking does. The process to make sense from a random mesh is not that simple as it may look.

This create_from_mesh() function is a legacy problem that should be deprecated which I made a pr for https://github.com/godotengine/godot/pull/77702. This function gives users the illusion that they do something correct by copying visual Mesh data directly to a NavigationMesh while this is 95% of the times wrong, and those 5% are mostly plane meshes. All the documentation script examples that use this function assume plane, or at least flat surface, meshes without mentioning it explicit but that is another issue.

The function is from a time where Godot had a very simplistic concept of what a valid navigation mesh could and should be, with no navigation mesh connections and no NavigationServer to worry about. The vast majority of visual meshes have inherently invalid data for navigation mesh use. It makes little sense to support such a data copy directly with a dropdown Editor option that most new users will stumble over.

For those that know how to create valid navigation mesh data in script the functions to add vertices and polygons to a NavigationMesh exist while everyone else should use the navigation mesh baking.

[tavurth]

@smix8 this writeup is super helpful, thank you 🙏

I will give the Navmesh baking a try tomorrow and try to compile our thoughts here to the documentation when I get a little time 👍

[tavurth]

@smix8 Ok I'm trying it now:

First I've tried like this:

When I bake the parent NavigationRegion3D and then delete the child NavigationRegion3D nodes there is no remaining mesh 🤔

Next I tried like this:

Then bake the parent and delete the MeshInstance3D nodes, ok nothing there...

Next I tried like this:

Ok, after baking and deletion the parent still has no NavigationMesh data.

Next I tried this:

After pressing "Bake navmesh" on the parent and deleting the children, no results.

Conclusion?

I've no idea how we're expected to bake a NavMesh as you mentioned many times previously.

Could you make a small tutorial, or perhaps some pointers?

[tavurth]

Aha I figured it out, earlier you mentioned "With agent radius 0"

Why is this the way to bake a NavMesh?

Can we document this, or perhaps better, can we just allow baking with a non-zero agent radius?

Update:

Aha I see, agent size was not working because the map was too small. This could be a helpful error message?

[smix8]

@tavurth The basic tutorial steps to make a navigation scene are in the 2D & 3D Navigation Overviews of the documentation. As those are the first pages of the navigation documentation it is assumed that people encounter them first. The 3D tutorial to bake and run a basic 3D navigation scene can be found here.

Why is this the way to bake a NavMesh?

Can we document this, or perhaps better, can we just allow baking with a non-zero agent radius?

The default agent_radius is the same as the default NavigationAgent radius, makes sense now?

You can already set the agent radius to zero but having a zero agent radius as the default in a more hidden property is not good usability cause outside of niche uses like preparing grid cells you basically always want an agent radius to avoid clipping.

The Nr.1 issue / complain of 2D users is agent clipping because 2D has no auto-margin for agent sizes. 3D users never voice similar issues thanks to the default agent size.

[tavurth]

The Nr.1 issue / complain of 2D users is agent clipping because 2D has no auto-margin for agent sizes. 3D users never voice similar issues thanks to the default agent size.

Yes it's something I even built a bespoke a star for before in godot 3.x. Glad to see were getting a few improvements.

So far it's fairly logical, but there are some small gotchas like nice to have some more error messages when I'm doing something stupid.

As those are the first pages of the navigation documentation it is assumed that people encounter them first. The 3D tutorial to bake and run a basic 3D navigation scene can be found here.

While this may be true godot docs don't seem to have a great SEO at the moment and none of my Google searches have landed on those tutorials.

I will take a look and see if I can find them.

I will also throw these Github issues into chatgpt soon and see if we can get a nice step by step for gridmap, using the images I posted above.

[smix8]

Closing the issue as the discussion has run stale for some time now and there is no bug and I think all points have been answered or can be found in the documentation by now. Also there were some improved error msg in the 4.1 release for this error. Feel free to comment if you think otherwise so we can reopen.