Nav mesh - re-implement the quad tree compression methods

[Garanas]

Description

The compression is a key component of the navigational mesh. It significantly reduces the amount of memory and computations during run-time. The initial implementation works, but performance-wise it can be improved. We're talking about the Compress method of the CompressedLabelTree class. At the moment of writing, you can find it on line 281:

• https://github.com/FAForever/fa/blob/deploy/fafdevelop/lua/sim/NavGenerator.lua#L353

The issue of the initial implementation is that it works top-down instead of bottom-up. This causes a lot of data to be re-read. This is best explained with a drawing:

Say we have a 4x4 square. The bottom right corner is invalid, marked as red. The rest of the square is valid, marked as blue. The current implementation reads the entire square, only to find out that the last read is invalid. The entries that are read are marked as yellow. The algorithm splits the area in four equal squares, and then starts reading each square separately again. The entries that are read for each square are marked as yellow.

On a map we're not talking about 4x4 squares, but about 32x32, 64x64, 128x128 or even 256x256 squares. That means we can potentially do a lot of re-reading when a square is not entirely valid.

Course of action

Re-implement the compress method using a bottoms-up approach. This is a recursive implementation:

• (1) We first compute all children, up to the base case: the compression threshold. These represent the initial leafs.
• (2) We check each child to determine if they have the same label. If they all have a label assigned and they are all the same (either -1 for invalid, or 0 for valid) then we cull the children and assign that label to the current node. That node then becomes a new leaf.

With this approach we guarantee that we only read each cell of the square once. We do introduce some additional class instantiations that we then potentially immediately trash - in the future we'll be looking at pooling those to prevent thrashing the garbage collector too much.

The description is a bit rough - if you have questions, you can ask so in the comments.

Test plan

The output should be exactly the same, but the generator should be faster. The changes should be limited to the Compress function of the CompressedLabelTree class.

Note that the pooling is not part of this issue, it will be a separate issue and needs to be solved using a separate pull request.

Learning goals

Learn to work with algorithms and data structures.

[Zjonn]

Hey @Garanas, I will take care of this issue, you can assign it to me

[Garanas]

@Zjonn do you still have the intention to pick this up?

[Zjonn]

@Garanas yes, I just need to have some free time and desire. In order to create a deadline for myself, I will try to deliver some preliminary tests this week

[Zjonn]

@Garanas where can I find the lua version that supports preallocation syntax (local instance = {&1 &0}), it looks like faf 'lua-lang' doesn't support it?

[Garanas]

There is no Lua syntax that supports it, it is something the people at GPG introduced. You can try removing it temporarily