NavigationServer3D::sync can still be further optimized

[0x0ACB]

Tested versions

4.x

System information

Godot 4

Issue description

I do not agree with #100497 closing #96483. The underlying issue is still the same.

This approach doesn’t resolve the root issue; it simply masks it. For example, with a single moving platform, NavigationServer3D::sync rebuilds the entire map every frame rather than just the affected parts. This is highly inefficient and needs to be addressed. Same for navigation links. Changing them will cause the whole map to be updated instead of just disconnecting the link and reconnecting it to the new position.

I have started on optimizing the navigation module but I currently do not have the time to get it into a PR sate so here are a couple ideas that will greatly speed up NavigationServer3D::sync:

1. add separate lists for internal and external connections to Polygon. This allows you to:
   • compute internal connections once in NavRegion::update_polygons and store the unconnected edges. Then only connect unconnected edges between regions in NavigationServer3D::sync. [O(n²) -> O(k²) with k << n in practice]
   • only disconnect the connections between a region and all other regions instead of clearing all connections when removing a NavRegion [O(n²) -> O(k)]
   • only build connections between the new region and all other regions when adding a NavRegion [O(n²) -> O(~k)]
2. only actually update that one link when updating a NavLink and not the whole map [O(n²) -> O(~1)]
3. create some kind of broad-phase for NavRegions to further reduce the amount of edges that need to be checked. A simple AABB tree should be enough. This could be further extended to also build a broad-phase for the polygons inside the region. Moving regions could be marked and excluded from the broad-phase to make it a bit simpler.
4. Since the navmesh is an indexed mesh there is no need to do any kind of distance check to connect internal edges. Two edges form a connection if they use the same indices. This will also eliminate a bug where sometimes with very thin polygons the wrong edges are connected.

For 1. there is also the option to store the external connections directly in the NavRegion this would have the added benefit of generating an implicit hierarchical graph which could be used to speed up path queries at the cost of precision on very large maps. The internal connections could also be computed ahead of time when building the navmesh. Recast already gives you the information it is currently just discarded. This would however require a breaking change to the navmesh structure.

Steps to reproduce

Minimal reproduction project (MRP)

[akien-mga]

Hello. Could you amend the start of your issue so it doesn't needlessly come off abrasive and vindictive?

You may have a point that the sync algorithm can be further optimized, but phrasing it like you do initially is unconstructive and simply disheartening for contributors.

[0x0ACB]

Not sure which part of that comes across as vindictive or abrasive to be honest. That was not my intent. Also the PR that was used to close the Issue clearly states that it does not actually optimize anything so I was quite surprised it was used to close the issue.

[MJacred]

@0x0ACB

Not sure which part of that comes across as vindictive or abrasive to be honest

• while memes have their place in e.g. social media because of their expressiveness in an over-the-top way, they usually have no constructive nature. This meme is about venting frustration, and therefore misplaced in this context
• […] Not just parts of it. The whole map. That that is not efficient should be obvious[…] is a repetition of will rebuild the **whole** map every single frame and does not really contribute to your explanation. The text before (with "whole" already formatted in bold) already clearly explains the situation. In combination with "obvious" the text flow takes on a jeering/shaming character.

[0x0ACB]

while memes have their place in e.g. social media because of their expressiveness in an over-the-top way, they usually have no constructive nature. This meme is about venting frustration, and therefore misplaced in this context

The meme was a reference to this part in the PR:

[…] Not just parts of it. The whole map. That that is not efficient should be obvious[…] is a repetition of will rebuild the **whole** map every single frame and does not really contribute to your explanation. The text before (with "whole" already formatted in bold) already clearly explains the situation. In combination with "obvious" the text flow takes on a jeering/shaming character.

I don't see that as needless, it emphasizes the underlying issue and if rebuilding the whole map every time is not obviously inefficient I don't know what is. I had ChatGPT reformulate it non the less.

[smix8]

Na it is ok. I even appreciated the meme. Everyone can chill.

We have older issues open for the same thing like #68642 and we have proposals like godotengine/godot-proposals#5635 for the actual implementation details all tracking more or less the same stuff. Those are also linked in the navigation tracker #73566.

I think with those links it should be clearer why that issue was closed. I would appreciate if you could add your implementation details and suggestions to that proposal that would be a good place for this so contributors can find those info when they might start working on that stuff.

The reason why I linked that PR to close the issues is because it solved the immediate problem while what is left was either a duplicate already coved by other issues and proposals or too generic and open ended in the "make things faster" ballpark which I agree but that is not what issues are kept for. So even if the PR would have not closed the issue directly it would have been closed on the next clean up wave as an issue duplicate or consolidated because a proposal tracked the problem or feature already.