Navigation on a procedurally generated TileMap with obstacles

[schemar]

Godot Version

4.2

Question

Maybe my whole approach to island generation is wrong to begin with. In that case, please let me know

What I do:

1. I procedurally generate an island with a TileMap. At the moment, there are only two kinds of tiles: land and sea.
2. I procedurally generate trees on the island. Trees are not part of the TileMap. They are scenes which I add to the TileMap (island) scene.

Where I struggle:
I want to use path finding on the island. As far as I understand, I could use the TileMap‘s navigation feature. However, that’s not aware of the trees.

What are my options to make this work? I considered creating my own navigation mesh that fits the island and leaves out the trees, but my feeling is that this is rather complex and I wouldn’t even know where to get started with that.

Is it even „correct“ that the trees aren’t part of the TileMap?

Thanks for your help

[smix8]

I wouldn’t use the Tilemap build-in navigation as it is flawed on so many levels.

Instead use a NavigationRegion2D and bake your TileMap navigation data to a optimized navigation mesh. You can use the TileMap only as data by disabling the build-in navigation of the TileMapLayer and the navigation mesh baking will read all your TileMap cells with navigation polygons or collision polygons from the first TileMapLayer and bake a navigation mesh from them.

[schemar]

Thank you, I will keep that in mind. Step one is for me to get navigation working, then I’ll figure out the fixes/optimizations. Or is that a waste of time and I should do the baking right away?

[smix8]

Depends on what kind of setup your project runs.

If you want movement that is not restricted to the center points of your TileMap cells, e.g. like an old-school grid game, you basically can not use the TileMap build-in navigation. The TileMap build-in navigation creates navigation meshes that will get all your agents stuck on every single corner with physics collision. The TileMap can not create or place navigation meshes with a correct offset for an agent radius due to its cell layout. To bake navigation meshes that have offset for agent radius you need to use a NavigationRegion or the NavigationServer bake functions.

You can not stack or overlap navigation meshes. If you use the TileMapLayer system with cells that have navigation / collision polygons it might be a waste of time. As far as 2D navmesh baking is concerned pretend that the TileMap has only a single TileMapLayer, because only the first TileMapLayers gets baked. If you use a Navigation Region2D dont forget to disable the build-in TileMap navigation on the TileMapLayer or the two navmeshes will conflict.

[schemar]

Thank you for taking the time to respond. I will use baked navigation meshes which can include the obstacles. It seems that’s the best lowish-effort solution.

Thank you for your insight!

[schemar]

Thanks again, @smix8! It works!

I have a (“procedurally”) baked NavigationPolygon from my TileMap and the obstacles that are its children. All based on their physics layers.

I still get the issue that characters may get stuck at corners, but I’m confident I will find a way to make it “good enough”

Not sure if it helps anyone, but this is my GDScript:

    # Bake navigation region from physics layer of TileMap and children:
    var nav_region: NavigationRegion2D = $NavigationRegion2D
    # Go by group name and children, as going by ROOT node somehow doesn't work.
    # Make sure the TileMap is in the group for navigation that is set on the `NavigationPolygon`.
    nav_region.navigation_polygon.source_geometry_mode = (
        NavigationPolygon.SOURCE_GEOMETRY_GROUPS_WITH_CHILDREN
    )
    nav_region.navigation_polygon.clear()
    nav_region.navigation_polygon.add_outline(
        PackedVector2Array(
            [
                Vector2(0, 0),
                Vector2(map_size.x * 32, 0),
                Vector2(map_size * 32),
                Vector2(0, map_size.y * 32)
            ]
        )
    )
    nav_region.bake_navigation_polygon()

[smix8]

You need to change the agent_radius property of the NavigationPolygon to a size that fits your agent. If this radius is to small, the default is 10 pixel, there is not enough margin and the collision shape of your agent will get stuck on physics collision. See Using navigation meshes — Godot Engine (latest) documentation in English that has an image that shows the problem at the beginning. A navigation mesh describes a surface that an agent can stand on safely with its center compared to physics shapes that describe outer collision bounds, so without margin agents will always get stuck when navmesh and physics shape align with each other.

[schemar]

Thanks, I will do that.

I think that also means that I want to do my characters quite a bit smaller than the size of a tile in the tilemap. The game is 2D top-down and I want them to be able to go relatively close to the edges. Right now I’m thinking 32x32 pixels tiles and only 16x16 pixels characters, but I’ll experiment.

In any case, thank you so much for your support.