godot icon indicating copy to clipboard operation
godot copied to clipboard

Optimize some parts of `NavMap::sync`

Open Zylann opened this issue 1 year ago • 1 comments

This is a few optimizations I've done while investigating navigation on a large procedural streaming terrain.

  • Reduced the amount of HashMap lookups
  • 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_back and HashMap re-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 avatar Apr 03 '24 18:04 Zylann

@Zylann PR https://github.com/godotengine/godot/pull/93005 has now been merged. Would you be available to rebase on top?

smix8 avatar Oct 18 '24 19:10 smix8

Thanks!

Repiteo avatar Nov 05 '24 03:11 Repiteo