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
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:
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
TargetCheckIntervalof a weapon - The flexibility, or the
AlwaysRecheckTargetof a weapon - The complexity, or the
TargetPrioritieslist 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
TargetCheckIntervalthat 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
AlwaysRecheckTargetis 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
TargetPrioritiestarget 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:
You can find the relevant changes in this paste bin file:
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.