Optimize some parts of `NavMap::sync`
This is a few optimizations I've done while investigating navigation on a large procedural streaming terrain.
- Reduced the amount of
HashMaplookups - Use a "pair" structure for connections instead of heap-allocated
Vector<T>because they only ever have up to 2 elements - Pre-allocate instead of letting several reallocations occur in
push_backandHashMapre-hashs - Use squared distance instead of distance to avoid square root calls
Note: I saw that in Find the compatible near edges there is a double for loop, which seems to pretty much iterate every possible pair of free edges. This will iterate each pair twice, (A, B) and (B, A). Unless I'm missing something, the inner loop could use for (unsigned int j = i + 1; j < free_edges.size(); j++) { so each pair only has to be iterated once. But I haven't done that change because I'm not sure if the current loop is actually intented.
@Zylann PR https://github.com/godotengine/godot/pull/93005 has now been merged. Would you be available to rebase on top?
Thanks!