Add 2D navigation mesh simplifcation to 4.0 TileMap

[Black-Virtue]

Describe the project you are working on

Experimenting with the TileMap and Navigation features
Planning to use them in procedural map generation (not necessarily randomised)

Describe the problem or limitation you are having in your project

When pathing across a TileMap defined NavigationMap the pathing picks paths that only cross between adjacent or diagonal tiles
This leads to inefficient paths and effectively reduces pathing to simple 8-directional, rather than 360 degree movement, as tile size trends towards 1px

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Access to a TileMap's NavigationMesh and built in "simplify navigation mesh" function would solve this issue even at it's most primitive, and provide other useful functionality.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

It is currently hypothetically possible to iterate over each tile in a TileMap (or navigation Mesh): look for adjacent navigation polygons, check they share vertices and manually merge them to slowly form a new NavigationMesh.
This is both quite cumbersome and would become painfully slow in GDscript with larger TileMaps

Having at least full tiles flag themselves to be merged into adjacent meshes would be very useful.
If TileMap received "set_tiles_rect" and/or "set_tiles_fill" this could be further simplified by creating the NavigationPolygon using just the edge tiles.

If this enhancement will not be used often, can it be worked around with a few lines of script?

Not to my knowledge.
Even in the case of a smaller function in terms of lines of code it would be iterating over thousands of nodes in a cumbersome way to handle in GDscript without special cases.

A general "simplify mesh" function could see a lot more general use.

Is there a reason why this should be core and not an add-on in the asset library?

This would make TileMap a far more powerful tool to handle graphics, static body physics physics, and navigation.
Having TileMap handle these features without needing custom code would open up the features for simpler use by artists and designers without experience in and/or are intimidated by coding.

[Black-Virtue]

navigation.zip
Sample project with two scenes showing TileMap's navigation defaulting to 8directional movement on the grid as tile size shrinks.
(click to select pathing destination)

[Black-Virtue]

I have a basic optimiser working, though it assumes each tile is either fully navigable or non-navigable, only works for square grids, and will suffer when presented with Navigable areas that have lots of non-horizontal/vertical edges for now.
https://github.com/Black-Virtue/Godot4-Navigation-with-TileMaps

Most of the code is in TileMapHelper.gd for those wanting to use it. It comes in at ~200 lines, which is a bit much to just post here.

[LoonyMoth]

Would merging a Tilemap's NavigationPolygons into chunks of arbitrary size help with this? This is something I've been trying and failing to achieve manually with the Geometry2D functions for similar purposes.
In addition, loading in new tiles for procedural generation seems to become very expensive in physics processing time, in a linear fashion, with each new tile added.

One strategy I've been trying is to generate one starting positive 'hull' polygon which covers the entire chunk.
I then walk through the Tilemap, tile by tile, and then collect negative 'hole' polygons which would be non-navigable obstacles.
These are then clipped out of the main hull to sort of minimize geometry in the region.

However, I'm having trouble getting it to work right, especially with complex shapes or multiple recursive hulls/holes. Merging multiple polygons together in one function might be helpful for this (see #913)

Does anyone have any other ideas or suggestions as to how to simplify or streamline navigation using Tilemaps?

[smix8]

Navigation baking for 2D including TileMaps is planned to be part of pr 70724. It will properly arrive with Godot 4.1 and add the same navigation baking functionality for 2D that 3D has rightnow.

This means TileMap navigation baking will work the same as for 3D GridMap rightnow. You keep the option to use the TileMap internal tile baked navigation or you can disable it and use a NavigationRegion2D node that parses the TileMap data and bakes an optimized NavigationPolygon for the entire TileMap, same as NavigationRegion3D and GridMap do rightnow.

For the TileMap internal tile baked navigation could merge them by TileMapQuadrant, that is the only middle unit that TileMap has that could make sense. Though it wouldn't improve the pathfinding path quality a lot if used with a small TileMapQuadrant size (default 16) and small cells.