Merging navmeshes

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Анархид
:warning: Old Version Published before Godot 3 was released.

I want to construct a GridMap maze and have player-controlled entities pathfind through the maze.

It is obviously impractical to construct a navmesh for the whole maze each time, especially as each tile’s pathability is known during construction of the tile. So i want to have individual, tile-based navmeshes for each tile to somehow merge into one super-duper navmesh for the whole GridMap.

I have found a reddit post by reduz that says navmeshes merge automatically, but the conditions of merger are unclear. I was also unable to acquire the answer via RTFS (at least thus far) and asking in chat, however a video showing overlapping navmeshes suggests that the merging requires something more than mere clipping.

So: how do i achieve my goal of having an automatically merged gridmap-level navigation constructed from individual tile navmeshes? What are conditions of merging? Does geometry have to clip, or do bordering navmesh edges have to match perfectly? Are there any existing tools/methods/tricks to guarantee such edge matching easily, if edge equality is required?

:bust_in_silhouette: Reply From: batmanasb

I think the 2D version of your question might have been answered here: https://forum.godotengine.org/1790/how-to-implement-pathfinding-with-a-tilemap, but I’m not sure how well this process can be converted to 3D… sorry.

I think the way merging works is when several NavigationPolygonInstances clip, but only if they are all children of the same Navigation2D node. Also, you can attach NavigationPolygonInstances to a Tileset’s tiles, and use snapping to help align them perfectly.

The clipping doesn’t seem to work for 3d, but thanks to comparison with 2d, i think i have managed to isolate both problems that prevent my goal from working…

Анархид | 2016-03-21 18:19

:bust_in_silhouette: Reply From: Анархид

With some experimentation, i was able to determine that in Godot 2.0.1:

  1. Gridmap tiles as loaded from the MeshLibrary can only have a mesh and a collision shape. It is not possible to add secondary meshes or navigation meshes as children of the MeshLib tile. I have tested this by adding a TestCube to one of my tiles, reexporting the scene as a meshlib, reloading the gridmap theme, and instantiating the tile. Scaling and other subscene niceties are also, apparently, unsupported.

Edit: some future version of Godot with this PR merged is hopefully going to support gridmap navmeshes. Or, if you require this functionality right now, you can custom-build an engine with this patch.

  1. Navmesh merging works only on exact edge coordinate matches. Both vertices of both edges which will be joined have to have precisely matching coordinates.

Here is a screenshot that shows both of these effects in action:
Navmeshes merging and unnavigatable gridmap

I guess i’ll just have to use scene instancing directly, at least for now.