Rework how formations are computed

[Garanas]

While looking at how selections work I stumbled upon formations. It was an intriguing find, not only do we have full control over the behavior of formations but the existing implementation sets the garbage collector on fire.

When are formations applied

The first interesting find is that formations are computed often. So often in fact that I would consider it a hot spot. It triggers when:

• (1) A player issues an order that may involve movement. These orders apply the attack or growth formations depending on the preference of the user
• (2) A unit that is on guard and another unit leaves or joins the guard order
• (3) The formation orders via script issue a formation

Another interesting find is that the formation are computed twice. It is computed once in UI and then another time in the simulation. It is computed in the UI to generate a preview. It is computed in the sim to apply the formation in the simulation.

And last but not least, an interesting combination is the Cybran build drone with (2). Build drones issue guard commands separately and therefore each time a Cybran engineer starts/stops assisting a construction the guard formation needs to be recomputed. These drones entirely ignore the guard formation but the guard formation is recomputed in the simulation.

The costs of computing a formation

In the existing implementation there are two relevant costs:

• (1) For attack and growth formations there's a flat cost of about 5kb of memory allocation regardless of the size of the selection.
• (2) For attack and growth formations the computations to create the formation are complicated and computationally expensive.
• (3) Formations scale over the size of the selection. This makes sense for the output (as you need to map every unit to an offset) but it does not make sense for the intermediate computations. The computations rely on the footprint and the categories of a unit. Those are the same for all units of the same type.

Because formations are computed twice the costs are doubled - it is computed in the UI (for the player on the local machine) and in the simulation (for every order that involves some movement from all players and/or script).

more to come

[lL1l1]

I noticed that when units in formation are given a formation facing in the opposite direction, one unit from the front tries to go to a position near the new front, when it should be going to a position in the near back. Is this possible to fix here?

https://github.com/FAForever/fa/assets/82986251/cbaa247b-33d1-4bdb-a4e2-7ffb73c19e03

Seems like since the front row has more units than the back, it has to grab 1 unit from the back to place in the front row, but it places that unit right in the middle of the front row instead of the closest position in the front row.

[Garanas]

That's engine behavior I'm afraid. All we can tell the engine is what category a given position should have, not what specific unit should end up there.

For my idea, how do you enable that path finding preview?

[lL1l1]

how do you enable that path finding preview?

Console commands dbg NavWaypoints, dbg NavSteering, and dbg NavPath or, since dbg autocompletes, just dbg navw dbg navs dbg navp.

[Garanas]

[Garanas]

Now we need to take into account the footprint somehow 😃 !

[Garanas]

Some initial data on the performance. For roughly 800 units (600 direct fire, 80 anti air, 50 scouts, 80 artillery):

• New growth formation: roughly 1.0 - 1.5 milliseconds
• Old attack formation: roughly 7.0 - 8.0 milliseconds

Note that a the simulation has a budget 100 milliseconds before the simulation slows down. And the UI has a budget of 16 milliseconds before your frame rate dips below 60fps!

[Garanas]

Interesting enough, in this game of 52 minutes:

• https://replay.faforever.com/21942580

You can observe the following formation counts:

• GuardFormation: +/- 11.000 which is +/- 211 a minute
• AttackFormation: +/- 2.800 which is +/- 53 a minute
• GrowthFormation: +/- 700 which is +/- 13 a minute

The guard formation explodes because of the Cybran build drones ( @zhanghm18 ). It's called so often that it triggers almost four times per second 😃

And for this 38 minutes of replay:

• https://replay.faforever.com/21924449

• GuardFormation: +/- 6000 which is +/- 157 a minute

• AttackFormation: +/- 7300 which is +/- 189 a minute (!!)

• GrowthFormation: +/- 300 which is +/- 8 a minute

[Garanas]

[Garanas]

[Garanas]

With features such as https://forum.faforever.com/topic/7351/ctrl-ui-mod this becomes even more relevant 😃

[Garanas]

There's an interesting engine bug with the Guard formation: usually they map fine when the unit (that is being guarded) is on the move but when the unit rotates across some threshold then suddenly all units are mapped completely differently, causing a lot of path finding pain:

https://github.com/FAForever/fa/assets/15778155/300a0317-fa2e-4294-8e49-9b8b275bc8e6

At first I thought it was related to the spiral pattern that I want to introduce:

https://github.com/FAForever/fa/assets/15778155/1e825212-116a-4125-af70-fa12f58e714c

But it occurs, regardless of the pattern.

[Garanas]

First working examples of sub-formations:

https://github.com/FAForever/fa/assets/15778155/fe654bc5-86e5-4fbf-94d6-f33735b447ee

https://github.com/FAForever/fa/assets/15778155/9e3ce00a-0f99-4249-9c7a-68e6fd6a8d9d