Weapon target check intervals

Jip

Every unit in the game has a weapon. All weapons combined take up a significant portion of the simulation budget. The time is not spent on creating the projectiles. It is spent on the scanning for targets and the filtering of targets for the weapon to fire at.

At the end of this topic you'll understand why this is so expensive, what we're changing about it and what that means for the behavior of every single unit in this game. The reason for these changes is simple: performance. Nobody wants to play in slow motion, even though people unconsciously appreciate the additional APM.

This topic is related to this pull request on Github:

https://github.com/FAForever/fa/pull/3857/files

Why it is expensive

Throughout this section I'll purposefully make simplifications. These are marked with an asterisk (a *). I will not describe why these are simplifications - it would make the topic too lengthy and it would take up too much of my time. The best you can have is the speculation of why things are a simplification of people taking the time to read and respond to this topic.

The introduction states that a weapon performs two actions to find targets*:

(1) Scan the surrounding of the weapon for any target
(2) Filter the targets for priority

For the programming enthusiastic among us we'll talk about complexity theory. Complexity theory describes how expensive an operation is based on the input*. For this example we will work with the following scenario:

A screenshot of fifteen purple Mantis and ten red Mantis

We denote n to be the number of weapons that we need to scan for. When a weapon scans for targets there are some trivial improvements that we can make:

(a) We can easily skip allied units*
(b) We can use an acceleration structure to easily skip units that are very unlikely to be a valid target

Using these two tricks we can scan for targets in a reasonable fashion: Using (a) we can skip checking for our own or allied units. And, using (b) we can (efficiently) skip checking entire collections of units that are far away. At some point we end up with a list of targets. We denote k as the number of targets found for a given weapon.

We're scanning for all weapons, and each weapon has a series of targets. Using the notation provided before it means we can assume to at most nk targets. In this example we have fifteen purple Mantis and ten red Mantis. Therefore we have at most 300 targets*: 150 from the perspective of the purple Mantis and 150 from the perspective of the red Mantis.

In this given situation one can argue that all weapons can point to roughly the same units. Therefore they share a common list of targets, and at this point all the targets are homogeneous. Using batching and other tricks you can get even more performance for this phase.

Once we have a list of targets for a weapon we need to prioritize those targets. An example of such a priority list is the following:

TargetPriorities = {
    'EXPERIMENTAL',
    'SNIPER',
    'ANTISHIELD',
    'MOBILE TECH3 ARTILLERY',
    'MOBILE TECH2 SILO',
    'STRUCTURE SHIELD',
    'STRUCTURE TECH3 DEFENSE DIRECTFIRE',
    '(STRUCTURE * TECH2 * DEFENSE - ANTIMISSILE)',
    'MOBILE TECH1 ARTILLERY',
    'MOBILE TECH3',
    'MOBILE TECH2',
    'MOBILE TECH1',
    'COMMAND',
    '(ALLUNITS - SPECIALLOWPRI)',
},

By all means this list is excessive. Yet, this is not a made up example as this is taken from the Cerberus turret.

A common query for computers is to determine whether one element in a list matches a given condition. In order to determine this a computer has to iterate the entire list*. Therefore, say our Mantis used the example target priorities it would need to iterate across the list at least twelve times: only then we find a unit that is applicable to the categories given: a tech 1 mobile unit named a Mantis. We denote l as the number of elements in the target priorities list. With it we can finalize our formula to compute the total number of computations with lkn.

Each weapon will have to determine whether there is a unit of a given priority in their range. Therefore all of the 300 targets need to be filtered. This is no homogenous operation - we can set the target priorities of each unit individually. Therefore there's no batching that we can apply. This is simply expensive, and it depends on the number of nearby targets.

By now you understand that this can be expensive. In this simple, yet common scenario we already have to scan for hundreds of targets. Let alone when we are dealing with entire armies colliding, or with entire clouds of ASF.

For your idea, using n for the number of units to check for, k for the average number of targets and l for the size of the target priority list we can end up with:

100 units with each 50 targets and 5 priorities: 100 x 50 x 5= 25.000 checks*
300 units with each 200 targets and 5 priorities: 300 x 200 x 5 = 300.000 checks*
400 units with each 400 targets and 5 priorities: 400 x 400 x 5 = 800.000 checks*

The growth looks like a quadratic one*. Anything that is quadratic is an issue when you're trying to do something real time. The only solution is to slow down the simulation - and oh boy it gets slow at times.

What we're changing

The scanning of targets has a series of parameters:

The frequency, or the TargetCheckInterval of a weapon
The flexibility, or the AlwaysRecheckTarget of a weapon
The complexity, or the TargetPriorities list of a weapon

By changing these values we can determine how much they influence the performance of the game. before we do that it is important to understand what they mean.

The parameter TargetCheckInterval determines how often a weapon scans its surroundings for targets. It determines how responsive a unit is in general. As an example, a mantis that scans for targets every 3 seconds may miss a scout that was on the edge of its attack radius.

The parameter AlwaysRecheckTarget determines whether a weapon continuously scans for a better target, even though it already has a target. This allows a unit to switch to another target that has a higher target priority. The priorities depend on the TargetPriorities list.

The parameter TargetPriorities determines what targets are preferred over others. The previous example was quite extensive. Another example is the target priorities list of an actual Mantis:

TargetPriorities = {
    'TECH1 MOBILE',
    'TECH2 MOBILE',
    'TECH3 MOBILE',
    '(STRUCTURE * DEFENSE - ANTIMISSILE)',
    '(ALLUNITS - SPECIALLOWPRI)',
},

You'd expect a weapon to have between four to six priorities to differentiate between.

We'll sanitize these values to find a clean balance between performance and playability. To summarize the changes:

(1) The average weapon will have a higher TargetCheckInterval that depends on the range of the weapon. The more range the weapon has, the higher the target check interval is.
(2) The average weapon will not recheck for targets once it has acquired a target, therefore AlwaysRecheckTarget is set to false. Indirect weapons such as artillery, stationary weapons such as point defense, weapons with an attack radius of 50 or higher and weapons of experimental units are allowed to recheck their targets as they may end up firing at a low-value unit purely because it was the first one in range.
(3) The TargetPriorities target priority list is simplified or extended until there are four to six elements left.

Fun fact, this is the target priority list of a Summit:

TargetPriorities = {
    'NAVAL MOBILE',
    '(ALLUNITS - SPECIALLOWPRI)',
},

But hey - ATP doesn't give you any advantage. Just your battleships being able to magically prioritize my battleships, while my summits attack your shards. No big deal - it is fair and square.

You can find the exact formula can be found in the pull request:

https://github.com/FAForever/fa/pull/3857/files

You can find the relevant changes in this paste bin file:

https://pastebin.com/64kKE75j

You can search for units on their unit id or on their English name.

What it means to the behavior of units

On average units either:

(1) no longer respond to change
(2) respond slower to change

As an example of (1), if a Mantis is firing at a brick and suddenly a Pillar is in its attack radius then it will not switch targets. An example of (2), for weapons that do respond to changes they end up being a few ticks slower with actually responding to the change because we check for targets less frequently.

Note that a weapon will scan for new targets when it 'loses' (destroys) its current target. Therefore, for the average battle, units will still rapidly scan for targets for the sake of finding a new target. This is particularly true for interceptors and superiority fighters as it takes only five to seven shots to destroy their counterpart.

In practice I've made sure that the changes are barely noticeable from a gameplay perspective.

What it means to performance

Initial tests with AI show that we can have up to 600 units with these changes at the same costs of 500 units without these changes. That is quite a significant change.

Dense fights are significantly faster performance wise. As an example, try and spawn 300 mantis next to 300 other mantis. The performance tanks to 150 ms / tick, where our budget is 100 ms / tick. With these changes it sits at roughly 20 ms / tick. That is quite a significant change.

Jip

I'll use this post to keep track of discussions.

To answer @BlackYps , the latest log of changes (before / after) can be found here:

https://pastebin.com/4i86J4qj

List of units that have SPECIALHIGHPRI and SPECIALLOWPRI as their categories:

https://pastebin.com/fZ7Mcrep

I'd also like to note that the discussion is not about whether we're going to do this. It is about how we're going to do this. We're going to have to think in solutions. The performance we'd leave on the table by not doing this is unacceptable.

Issues

(1) Weapons have a lower reaction time, this is particularly noticeable with the delayed vision updates. As an example: a t1 scout can pass a t1 interceptor if they fly towards each other to some degree. The interceptor does not have the reaction time to take it down because there is a delay on the vision being updated and there's an (additional) delay on the weapon checking for targets (0.3 -> 0.7). This is not an issue when there is radar coverage.

(2) Some weapons have an extensive list of target priorities. It is not unusual to find more than ten different target priorities for a single weapon. These should be reduced to 4 - 8 elements each, depending on the expected instance count of a unit and its attack radius. As an example: an experimental can have 8 because you can count the number of active instances on one hand. A Mantis should have at most 4, as we can have hundreds of those walking around.

Solutions

(1) After a suggestion of BlackYps the approach to compute the target check interval has changed slightly. All interceptors happen to have the same target check interval as before.

(2) We could remove the SPECIALLOWPRI, SPECIALHIGHPRI and ALLUNITS categories from all weapon target priorities lists. These are either operation related, improperly used or out of place. As an example, take the target priorities of an Aeon T4 Rapid Fire Artillery:

TargetPriorities = {
    'EXPERIMENTAL MASSFABRICATION',
    '(EXPERIMENTAL * ARTILLERY - FACTORY)', -- don't include fatboy
    'TECH3 ANTIMISSILE',
    'NUKE STRUCTURE',
    'TECH3 STRUCTURE ARTILLERY',
    'TECH3 ENERGYPRODUCTION',
    'ORBITALSYSTEM',
    'EXPERIMENTAL MOBILE',
    'TECH3 STRUCTURE',
    'TECH3 MOBILE',
    'STRUCTURE',
    '(ALLUNITS - SPECIALLOWPRI)',
},

Even though storages are set to SPECIALLOWPRI, they are also a STRUCTURE and therefore they still have a higher priority than all the other units.

Impossibilities

(a) We can not change the logic that is used to determine viable targets. That is part of the engine. We can only change the parameters.

BlackYps

Did many (or all?) units constantly recheck targets before?

Sprouto

It is a valid option, but it's not super widespread - and it is a valid option in certain cases. Combined with the targeting interval - it can be a performance issue - especially if the priority list is long ( each and every category is checked every interval so it multiplies very quickly ).

Jip

@blackyps said in Weapon target check intervals:

Did many (or all?) units constantly recheck targets before?

I'd need to check, but I think the majority did yes.

maudlin27

Just to check re the point about never rechecking for targets if one has already been found, does that mean if I fly an air scout over a bunch of T1 MAA, followed by bombers, the T1 MAA will all target the air scout (it's the only unit they see), and if they fail to kill it (often the air scout travels too fast, unless its cybran MAA or is going almost directly at the MAA) theyll keep trying to target it while the bombers are free to cause carnage as long as the air scout stays within range of the MAA?
Similarly a land scout could be used to distract Aeon T2 PD (although it'd require more micro) allowing a guncom to close in without taking damage if the opponent isn't paying attention?

Jip

All ground to air units (and structures) are allowed to retarget, exactly because of that reason. See the paste bin dumb .

As an example:

Processing: ueb2204 (<LOC ueb2204_name>Air Cleaner)
 - Weapon label: Fragmentation Flak
 - - WeaponCheckinterval (prev): 0.30000001192093
 - - WeaponCheckinterval (post): 0.5625
 - - AlwaysRecheckTarget (post): true
 - - TrackingRadius (post): 1.1499999761581

thecore

"100 units with each 50 targets and 5 priorities: 100 x 50 x 5= 25.000 checks*"
I wonder if targets can be sorted by distance from each unit and also targets separated into priority groups.
So instead of each unit checking all near by targets, they just check the nearest enemy unit per group.
arrayPriorityGroupEXPERIMENTAL[0]
arrayPriorityGroupSNIPER[0]
etc

So if you had 100 units, checking 5 groups each having 50 units in them then you only need to check the nearest unit per group and then decide which one has priority.

In the example the unit would target the nearest unit ranked by Priority. So if there was a unit with q higher Priority it would target that unit instead.

Not sure if this would be a improvement or not as sorting can be quite taxing on performance.

Jip

I'm afraid that all of this is part of the engine. And we can not rewrite the logic.

Ctrl-K

@thecore not the best idea sorting according distance: nearest unit stays behind and you have to turn weapon to it.

MazorNoob

Will setting target priority affect AlwaysRecheckTarget? If I'm sending a few tanks to kill engies and an enemy tank gets into range first I'd rather they switched to an engie when possible. Same issue with e.g. killing power in a raid, switching immediately vs. in 10 seconds after killing some tanks makes a difference.

ZooDoo4U

I'm wondering what changes have been made since vanilla SupCom? I've played a long time, never saw where enemy units would get in range and not fire at them. Remember seeing a couple people asking about this scenario "Anyone see enemy units move in range but never fire..."? I'm starting to notice more and more in most every game. Not only this seems the game in general keeps getting more and more laggy with each successive patch.

Also no way to make the checks key or hash lookups rather than an n*m list match?

thecore

@bluescreenof4z0t maybe check nearest unit within line of sight first before checking any distance.

Jip

Remember seeing a couple people asking about this scenario "Anyone see enemy units move in range but never fire..."?

That is this scenario:

https://forum.faforever.com/topic/3805/cybran-t2pd-having-problems-targeting-and-not-firing-at-targets-in-range

We're fixing that too, as structures will no longer have a scanning radius (for targets) that is larger than their own range.

Not only this seems the game in general keeps getting more and more laggy with each successive patch.

This is the case for single player games. It is fixed with:

https://github.com/FAForever/fa/pull/3837

It is available on FAF Develop. I can highly recommend you to give it a try, especially if you play alone. The benchmarks show a 30% to 40% performance increase when you play alone on FAF Develop .

I'm wondering what changes have been made since vanilla SupCom?

A lot - in particular with the complicated target priorities. This can cause the issue that you describe where a unit 'waits' for a more valuable target to get into firing range.

arma473

@jip said in Weapon target check intervals:

structures will no longer have a scanning radius (for targets) that is larger than their own range

This allows turrets with no target to turn towards an incoming target? That's not a bad thing.

Jip

@arma473 said in Weapon target check intervals:

@jip said in Weapon target check intervals:

structures will no longer have a scanning radius (for targets) that is larger than their own range

This allows turrets with no target to turn towards an incoming target? That's not a bad thing.

It is when we have overly complicated target priorities. Take this forum thread and my answer in the second post:

https://forum.faforever.com/topic/3805/cybran-t2pd-having-problems-targeting-and-not-firing-at-targets-in-range

Brutus5000

I'm not really into the details, but checking the same thing over and over again seems a bit weird, when there are good data structure such as a priority queue.

Assuming the engine gives us access to events (a) a target entered turret range (b) a target left turret range (c) a target is no longer accessible (destroyed/submerge/lifted off).
For a) Determine the targets priority and add it to the priority queue.
For b) Delete it from the priority queue
For c) Delete it from the priority queue
For d) A user changes the priority: recalculate priority queue (but with same targets)

For determining the current target: Take the first item from the priority queue.

No need to iterate over all targets in range every recheck interval.

Jip

The targets are computed in the engine. We only have the parameters and the output that we can work with in Lua. Anything else requires assembly patches.

KaletheQuick

Would it be possible to enforce some limit on target priorities? Like t1 can have 2 priorities, then some "ALLUNITS" catchall, t2 4, t3 6, exp 8? And enforce it so ATP mods don't interfere?

Or would batching or target sharing be possible? Like one unit of a type can just 'give' its target to a nearby unit of the same type? Or I guess a unit searching for a target asks nearby allies of the same type for their target, checks if it's in range/valid, and then if not proceeds with a whole target check?

Jip

Would it be possible to enforce some limit on target priorities? Like t1 can have 2 priorities, then some "ALLUNITS" catchall, t2 4, t3 6, exp 8? And enforce it so ATP mods don't interfere?

That is what I'd like to have - yes. Perhaps not that extreme, anywhere between 4 to 6 is fine. But 10+ is a bit much. The balance team isn't quite in favor yet.

Or would batching or target sharing be possible? Like one unit of a type can just 'give' its target to a nearby unit of the same type? Or I guess a unit searching for a target asks nearby allies of the same type for their target, checks if it's in range/valid, and then if not proceeds with a whole target check?

I'm afraid that finding nearby units is a similar query to finding nearby targets .