How can you get Navigation2D to recognize updates to the nav mesh?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Will Nations

A Q&A reproduction of the following Reddit post:

https://www.reddit.com/r/godot/comments/7k4qos/why_does_this_script_created_hole_in_the/

This script created hole is not detected by the navigation mesh! Help~

:bust_in_silhouette: Reply From: Will Nations

Speaker: /u/WordOfRabbit.

So here is how you get Navigation2D to recognize updates to the nav-mesh:

var navPolyInstance = $NavPolyInstance
navPolyInstance.enabled = false
navPolyInstance.enabled = true

I am not joking; I had figured out how to manually force Navigation2D to update, but I wanted to see how NavigationPolygonInstance does it behind-the-scenes, in-case I could glean some missed steps or possibly a more efficient method. It turns out it simply does the C++ equivalent of exactly what I was doing, but tied it to the tree_enter and tree_leave notifications, which means you can force it to perform the same update by disabling and then re-enabling it.

That said, I can see scenarios in which you don’t want to disable and then re-enable (possibly don’t want to mess with attached children), or you want to perform a lot of changes so you’d like to batch them and handle it yourself, so I’m still going to detail the manual process.

First things first, whether you have the engine handle it, or do it manually, you need to modify your nav-mesh properly.

# The NavigiationPolygonInstance used by my Navigation2D node.
var NavPolyInstance = $NavPolyInstance
# Polygon2D node that has the polygon data I want to cut out of the nav-mesh.
var Cutout = $DynamicCutoutPolygon

# [...]

func adjustPolygonPosition(inTransform, inPolygon):
    var outPolygon = PoolVector2Array()
    var finalTransform = NavPolyInstance.transform.inverse() * inTransform

    for vertex in inPolygon:
        outPolygon.append(finalTransform.xform(vertex))

    return outPolygon

func modifyNavPoly():
    NavPolyInstance.navpoly.add_outline(adjustPolygonPosition(Cutout.transform, Cutout.polygon))
    NavPolyInstance.navpoly.make_polygons_from_outlines()

Wherever your new polygon data comes from, be it Polygon2D node, or one of the various physics-body nodes, you need to properly transform it, or you won’t preserve its position or rotation when using it to modify the nav-mesh. You need to directly apply those transforms yourself to the vertices.

So what we’re doing in the above code, is first calculating a matrix by which we can transform our polygon vertices by. In this particular case, Cutout is a child of our Navigation2D node, but not NavPolyInstance. We need to take the transform of Cutout and multiply it by the inverse of the transform of NavPolyInstance.

When we transform our vertices by this new matrix, it will transform them to be in the same position as we see in the editor, but will apply the inverse of the transformation present on NavPolyInstance, so that any transform present on NavPolyInstance is in-effect negated away, so that the modification made to the nav-mesh, is exactly where our Cutout node appears in the editor.

Here is an example of the difference between applying the inverse-transformation of NavPolyInstance to the transform of Cutout, and just using the transform of Cutout directly, when NavPolyInstance has been transformed (in this case rotated), so it no longer has an identity matrix:

Inverse-Transformation Applied

Inverse-Transformation Not Applied

As you can see in the second-example, it behaves as if you applied the rotation to Cutout, even though Cutout isn’t a child of NavPolyInstance. This can be a desired behavior, but in-most circumstances, I would imagine you would want the behavior of the first example, where the cutout is placed exactly as you placed it.

One-last thing on this before we move on. If you have non-uniform scaling applied to your objects, you need to use the affine-inverse transformation. It’s a more expensive calculation however, so stick with the regular inverse unless you need to use the affine-inverse.

So now we get into actually updating Navigation2D to reflect the changes we’ve made to the nav-mesh. This actually isn’t very complicated, it just needs some explanation on exactly what’s happening.

onready var current_navpoly_id = 1

func rebuildNavPath():
    navpoly_remove(current_navpoly_id)

    # If you build from source, this method was changed the other day to "navpoly_add"
    current_navpoly_id = navpoly_create(NavPolyInstance.navpoly, NavPolyInstance.get_relative_transform_to_parent(get_parent()))

So it turns out that you can only modify navpoly data in Navigation2D using its id, but the class has no ability to retrieve a list of existing ids and isn’t documented on how they’re calculated. Adding nav-poly data returns an id you can keep track of, but you have no way of accessing the ids of nav-poly data added by a NavigationPolygonInstance. Looking through the C++ code for the class, it turns out that the id is simply an incrementing value. It starts at 0, and every time some navpoly data is added, it increments by 1. It doesn’t decrease when removing navpoly data. The tricky part is that every time a NavigationPolygonInstance is added or disabled then re-enabled, that id is incremented.

Cool, thanks

wombatTurkey | 2018-03-23 08:24

what about the case where the navigation polygon is within a tile map?
i´m doing a script where the map is randomly generate by script adding cells to the tilemap, and after it finishes i have to calculate some paths within it, so i need the navigation2d to be updated after the map is created.
For a while I used yield(get_tree(), "idle_frame") to skip a frame and let the update happens by default, but it is not really acceptable

Andrea | 2018-11-09 13:43