Reviewing attackers/targets processing in CombatSystem.cpp

Programmers discuss here anything related to FreeOrion programming. Primarily for the developers to discuss.

Moderator: Committer

Message
Author
User avatar
Oberlus
Cosmic Dragon
Posts: 5715
Joined: Mon Apr 10, 2017 4:25 pm

Reviewing attackers/targets processing in CombatSystem.cpp

#1 Post by Oberlus »

struct CombatInfo has a class ObjectMap objects than contains several std::map for each type of universe object (m_objects for all, m_resource_centers, m_pop_centers, m_ships, m_planets, etc.).
struct AutoresolveInfo contains a struct CombatInfo.

ShootAllWeapons() calls to AddAllObjectsSet(AutoresolveInfo& combat_state.combat_info.objects, Condition::ObjectSet& targets) to add all objects in combat_state.combat_info.m_objects to targets (these includes everything in the system, maybe even buildings, AFAIK).
Targets is later queried through weapon.combat_targets->Eval(context, targets, rejected_targets, Condition::MATCHES) to get only the valid targets for current weapon.
Finally, one random object in that subset is chosen as target.

Possible targets subsets:
- Ships.
- Planets.
- Fighters(/missiles).
- Ships & planets.
- Ships & fighters.
Maybe someday also Planets & Fighters and Ships&Planets&Fighters, but that doesn't make sense right now.

Would it be faster (or at least as fast) to query directly the m_ships when the valid targets are only ships, m_planets for planets, a merged map of m_ships and m_planets when corresponds, etc.?
And add a new container for fighters, either in CombatInfo or in AutoresolveInfo, to do the same with fighters (that currently are together with ships, but I'm unsure)?
____

Should this be a good idea, the processing of phases within a combat bout for different subsets of attackers performed in CombatRounds() (the caller of ShootAllWeapons() could use the same way.

Currently, CombatRounds() first processes planets in a for(const auto& planet : combat_info.objects.find<Planet>(shuffled_attackers)).
Is objects.find<Planet> directly querying m_planets? My C++ inexperience does not let me be sure on this by looking at ObjectMap.cpp/h, but it seems to me that it queries the whole set of objects to return only the ones corresponding to the vector of indices shuffled_attackers, and the non-planet objects are ignored within the for (because they get cast to null or something like that in find<Planet>.
Then CombatRounds() processes everything else (also planets, that are skipped) using a for (const auto& attacker : combat_info.objects.find(shuffled_attackers)), which returnins every object in combat info.
It could instead process everything but the missiles (if they get their own m_missiles).

Why is used shuffled_attackers? It is a random permutation of the indices of the objects involved in combat. It is used to select the attackers in a random order, but the order in which you process them (within each phase) does not make a difference because the target is selected randomly too and it does not matter who gets its target first because shooting is simultaneous at the end of the bout and being selected for shooting in a previoes step does not affect who will you pick as target. Could this intermediate step be removed?

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#2 Post by Geoff the Medio »

Oberlus wrote: Sun Feb 16, 2020 12:37 pmWould it be faster (or at least as fast) to query directly the m_ships when the valid targets are only ships, m_planets for planets, a merged map of m_ships and m_planets when corresponds, etc.?
AddAllObjectsSet could be reworked to use ObjectMap::all<T> to get just objects of a particular type, but I think the idea here is or should be to not constrain what targets are possible for a condition to select.
Is objects.find<Planet> directly querying m_planets?
find calls the corresponding object type templated Map function, which for Map<Planet> is ObjectMap::m_planets.
Why is used shuffled_attackers? It is a random permutation of the indices of the objects involved in combat. It is used to select the attackers in a random order, but the order in which you process them (within each phase) does not make a difference because the target is selected randomly too and it does not matter who gets its target first because shooting is simultaneous at the end of the bout and being selected for shooting in a previoes step does not affect who will you pick as target. Could this intermediate step be removed?
Possibly.

User avatar
Oberlus
Cosmic Dragon
Posts: 5715
Joined: Mon Apr 10, 2017 4:25 pm

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#3 Post by Oberlus »

Geoff the Medio wrote: Sun Feb 16, 2020 7:01 pm
Is objects.find<Planet> directly querying m_planets?
find calls the corresponding object type templated Map function, which for Map<Planet> is ObjectMap::m_planets.
Oh, that's better than I thought. So the for loop of the second phase (all but planets, that boils down to fighters and ships/monsters) could be divided into two for loops calling to combat_info.objects.find<Ship>(shuffled_attackers) and combat_info.objects.find<Fighter>(shuffled_attackers), not that it make any sense right now. Or a third for loop could be added for missiles (ignoring missiles in the second loop). I'll get time to play with this but not any time soon. Thank you for the answers.

User avatar
Oberlus
Cosmic Dragon
Posts: 5715
Joined: Mon Apr 10, 2017 4:25 pm

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#4 Post by Oberlus »

The available targets for each shoot is calculated every bout for every weapon.
You must calculate/update the available targets every bout, but not necessarily for every weapon: you can cache the available targets for a given weapon part (or set of weapon parts) on a given faction/empire and bout. All your PC_DIRECT_WEAPON parts are going to shoot to the same set of targets.
Calculating the available targets implies querying all combat objects for a given pair of species and weapon targetting conditions. When you have hundreds of ships on a single fleet with hundreds of direct weapons and/or hundreds of fighters/bombers/interceptors, this means you are repeating hundreds of times the same calculations over hundreds of universe objects.

So I am thinking of chaching up targets within ShootAllWeapons. Also, in CombatRound there is a TODO about caching the results of GetWeapons to avoid recalling them on every bout. That seems also a sound idea but with less impact on performance.

Do you think this is worth of attention?

I would have already tested with an actual implementation if there is a reasonable accelleration of combat resolution, but I'm still learning the necessary C++ in my free time, and I couldn't help it asking.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#5 Post by Geoff the Medio »

Oberlus wrote: Tue Feb 18, 2020 6:50 pmDo you think this is worth of attention?

I would have already tested with an actual implementation if there is a reasonable accelleration of combat resolution, but I'm still learning the necessary C++ in my free time, and I couldn't help it asking.
It would be worth attention if it interests you to rewrite the code to be "cleaner" or if combat resolution is currently slow enough to be noticeably extending turn processing times. In my experience, the biggest delay in turn processing is autosaves completing and AIs playing their turns, if the player has a very fast turn (ie. almost no orders). I haven't noticed combat specifically being a probem, but I probably don't test often with big combats.

User avatar
Oberlus
Cosmic Dragon
Posts: 5715
Joined: Mon Apr 10, 2017 4:25 pm

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#6 Post by Oberlus »

Geoff the Medio wrote: Tue Feb 18, 2020 7:17 pm It would be worth attention if it interests you to rewrite the code to be "cleaner"
That interests me (I've been struggling with the code already). I'll give it a try.
I haven't noticed combat specifically being a probem, but I probably don't test often with big combats.
In multiplayer servers with no AIs, combat and other universe management code is what takes more CPU time (obviously). Having a more efficient code could be relevant when resources are scarce.
My feeling from big battles (10k damage per fleet) on huge galaxies, single player, is that the extra time on battle processing (compared to absence of such battles) is noticeable. But I don't know how much of the total time corresponds to what would be saved with the suggested change. Anyway, it's an interesting exercise to learn C++.

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#7 Post by Ophiuchus »

Oberlus wrote: Tue Feb 18, 2020 6:50 pm The available targets for each shoot is calculated every bout for every weapon.
You must calculate/update the available targets every bout, but not necessarily for every weapon: you can cache the available targets for a given weapon part (or set of weapon parts) on a given faction/empire and bout.
The caching like you imagine should work well for the current content.
But you can already implement targeting conditions for such a caching would fail, e.g. targeting only ships with a certain amount of structure. If we do not allow for Value() in targeting, at least caching during a bout would work. And of course for conditions which do not have so complicated effects also higher-level caching works. I think actually the conditions support querying the complexity of a condition.
Also geoff added already support for species targeting conditions which would change the target sets - so caching would have to work differently there. Also the intended battle scanners should change targeting.

So in the general case you can not cache. But in many cases you can.
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.

Look, ma... four combat bouts!

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#8 Post by Geoff the Medio »

Conditions have functions that indicate if they are invariant to context objects like the source (ie. the attacker), which could be used to decide if the condition result can be cached. But most targetting conditions depend explicitly on the source object's owner empire...

User avatar
Oberlus
Cosmic Dragon
Posts: 5715
Joined: Mon Apr 10, 2017 4:25 pm

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#9 Post by Oberlus »

Ophiuchus wrote: Wed Feb 19, 2020 10:30 am The caching like you imagine should work well for the current content.
But you can already implement targeting conditions for such a caching would fail, e.g. targeting only ships with a certain amount of structure. If we do not allow for Value() in targeting, at least caching during a bout would work. And of course for conditions which do not have so complicated effects also higher-level caching works. I think actually the conditions support querying the complexity of a condition.
Also geoff added already support for species targeting conditions which would change the target sets - so caching would have to work differently there. Also the intended battle scanners should change targeting.

So in the general case you can not cache. But in many cases you can.
I'm not sure I follow you.

Code: Select all

                Condition::ObjectSet targets, rejected_targets;
                AddAllObjectsSet(combat_state.combat_info.objects, targets);	// Adds to targets all objects in combat_info (i.e. planets, ships and fighters in the system)

                // attacker is source object for condition evaluation. use combat-specific vis info.
                ScriptingContext context(attacker, combat_state.combat_info.empire_object_visibility);	// Evaluation with this context selects different targets depending on empire owner of Source

                // apply species targeting condition and then weapon targeting condition
                species_targetting_condition->Eval(context, targets, rejected_targets, Condition::MATCHES);	// Evaluation with this attacker species' targetting conditions selects different targets depending on species
                weapon.combat_targets->Eval(context, targets, rejected_targets, Condition::MATCHES);        // Evaluation with this weapon's targetting conditions selects different targets depending on the weapon
My intention is to cache "targets" for weapons of the same empire (I think that is the only info relevant here from ScriptingContext), same species_targetting_condition and same weapon targetting conditions. I don't know what would be the appropriate C++ container for that, it has to search for triplets of <int, Condition::Condition*, Condition::Condition*> or something like that.
BTW, is there a simple way to "merge" together two Condition::Condition?

This would mean no improvement in battles with few ships of diverse designs (and species). Such battles are infrequent and mostly early game.
But battles with many instances of the same ship design on each fleet... In recent multiplayer games I'm used to fleets of hundreds of ships with 3 or 4 ship designs (chaff, bomber carrier, cannon boat, interceptor carrier or flak boat). That would make for 4-5 instances of "targets" per each faction (allied empires). With species targetting condition in the mix that would grow (and the improvement reduce) but still be interesting.

Regarding weapon types, with KISS hard targetting we have:
- Direct-damage: planets and ships
- Interceptors and flak: fighters (class) only
- Bombers: ships only
- Fighters: ships and fighters (class)

We could have more and the system should still work as long as the targetting conditions are specified in FOCS and gets to the backend in weapon.combat_targets.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#10 Post by Geoff the Medio »

Oberlus wrote: Wed Feb 19, 2020 11:57 amBTW, is there a simple way to "merge" together two Condition::Condition?
Merge how? Combine them as C++ objects? Or logically combine their function in game?
My intention is to cache "targets" for weapons of the same empire (I think that is the only info relevant here from ScriptingContext), same species_targetting_condition and same weapon targetting conditions.
The point is that that is not enough info to sort conditions with for combat target results caching. Conditions can depend on arbitrary stuff, so two targetting conditions on the same or different ships with the same or different ship design with the same or different species could have the same or very different results. There are even some "random" conditions that can and do return different results every time they are evaluated so can never be cached. Whether a condition's result can be cached can be determined in some contexts from its invariance to source objects. But most targeting conditions are variant, or dependent on, the source object, so will always return false for source invariance and there is no SourceInvariantExceptIgnoreSourceOwnerDependence function.

User avatar
Oberlus
Cosmic Dragon
Posts: 5715
Joined: Mon Apr 10, 2017 4:25 pm

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#11 Post by Oberlus »

Geoff the Medio wrote: Wed Feb 19, 2020 1:04 pm
Oberlus wrote: Wed Feb 19, 2020 11:57 amBTW, is there a simple way to "merge" together two Condition::Condition?
Merge how? Combine them as C++ objects? Or logically combine their function in game?
Yes, C++ objects, something like:

Code: Select all

Condition::Condition* merge(Condition::Condition* a, Condition::Condition* b)
To have to search for one single Condition::Condition* in the cache.

My intention is to cache "targets" for weapons of the same empire (I think that is the only info relevant here from ScriptingContext), same species_targetting_condition and same weapon targetting conditions.
The point is that that is not enough info to sort conditions with for combat target results caching. Conditions can depend on arbitrary stuff, so two targetting conditions on the same or different ships with the same or different ship design with the same or different species could have the same or very different results.
If you mean that ScriptingContext context(attacker, combat_state.combat_info.empire_object_visibility) has more relevant info than just Empire id., then all that should be used as "key" along with the conditions.

If you mean something else, I don't understand.

Assume we use as key for the cache <the empire ID owner of context.source> (to not target allies), <context.empire_object_vis_map_override> (to not target undetected enemies), <species_targetting_condition> and <weapon.combat_targets>.
The other member variables of ScriptingContext (effect_target, condition_root_candidate, condition_local_candidate and current_value) can be ignored, right? In any case, here context is created with only source and empire_object_vis_map_override.
Different attackers (source) with the same empire owner and the same visibility map and the same species and the same weapon.combat_targets should be shooting at the same subset of targets. Or in other words:
If calling to

Code: Select all

species_targetting_condition->Eval(context, targets, rejected_targets, Condition::MATCHES);
weapon.combat_targets->Eval(context, targets, rejected_targets, Condition::MATCHES);
with different attackers that share identical empire owner, visibility, species and weapon is going to give different results depending on something else, either I don't understand this system or that something else should also be used in the key for the cache.

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#12 Post by Ophiuchus »

Oberlus wrote: Wed Feb 19, 2020 11:57 am
Ophiuchus wrote: Wed Feb 19, 2020 10:30 am So in the general case you can not cache. But in many cases you can.
I'm not sure I follow you.
If you have a completely valid

Code: Select all

combatTargets = LocalCandidate.Structure > 40
or a

Code: Select all

combatTargets = LocalCandidate.Structure < 40
the possible targets change every bout (because some might not have structure 40 anymore). (First example there will be less targets, second example there will be extra targets; also the combatTargets could use the Source instead of the candidate).
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.

Look, ma... four combat bouts!

User avatar
Oberlus
Cosmic Dragon
Posts: 5715
Joined: Mon Apr 10, 2017 4:25 pm

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#13 Post by Oberlus »

Ophiuchus wrote: Wed Feb 19, 2020 2:12 pmthe possible targets change every bout
Yes, I know. That's true also for simpler conditions (like "ships"), because targets die between bouts.
The cache is redone every bout.

Ophiuchus
Programmer
Posts: 3433
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#14 Post by Ophiuchus »

Geoff the Medio wrote: Wed Feb 19, 2020 11:40 am Conditions have functions that indicate if they are invariant to context objects like the source (ie. the attacker), which could be used to decide if the condition result can be cached. But most targetting conditions depend explicitly on the source object's owner empire...
I think geoff refers to the COMBAT_TARGETS_VISIBLE_ENEMY macro which uses VisibleToEmpire is basically used for all weapon systems.

Automatic analysis of conditions is possible but not realistic.

Maybe one could add functions to all conditions which indicate if the condition is bout-invariant. Most leaf conditions are invariant during combat, but VisibleToEmpire may change between bouts as a ship uncloaks.

Another thing one could do is do caching for well-known conditions (where you know you can cache). I would like to have something like named conditions in the future (so an ID one can refer to).

The use of VisibleToEmpire actually means if you do not add complexity to handle visibility on the side, caching targets for a whole combat does not work at all.
Oberlus wrote: Wed Feb 19, 2020 2:24 pm
Ophiuchus wrote: Wed Feb 19, 2020 2:12 pmthe possible targets change every bout
Yes, I know. That's true also for simpler conditions (like "ships"), because targets die between bouts.
The cache is redone every bout.
Well I would have CullTheDead simply remove the target from the cache if it is dead.
If you only target a cache for a bout I guess my suggestion is that we either disallow using Value() in combatTarget conditions or add the adding combatBoutInvariant function which basically is true for everything which does not use immediate values in the tree.
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.

Look, ma... four combat bouts!

User avatar
Oberlus
Cosmic Dragon
Posts: 5715
Joined: Mon Apr 10, 2017 4:25 pm

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#15 Post by Oberlus »

Ophiuchus wrote: Wed Feb 19, 2020 2:30 pmAutomatic analysis of conditions is possible but not realistic.
What do you mean? Obviously, you don't refer to evaluating them (calculating "targets" corresponding to those conditions).
I would have CullTheDead simply remove the target from the cache if it is dead.
If other conditions have changed during the bout (visibility, new fighters, LocalCandidate.Structure>X, present species, etc.) you will be forced to recalculate "targets" anyway, so I think we can leave CullTheDead simple, as it is now (it does not touch "targets").
If you only target a cache for a bout I guess my suggestion is that we either disallow using Value() in combatTarget conditions or add the adding combatBoutInvariant function which basically is true for everything which does not use immediate values in the tree.
In both cases (Value and combatBoutInvariant) you are talking about FOCS "parameters" for part definition and the such, right?
I know nothing about Value() (have not got to that yet). So I don't know why should it be disallowed, what effects that would have, or whether I agree with it.
Re. combatBoutInvariant, tracking what conditions won't change during a bout might be tricky, if it depends on the awareness of the modder when setting up the value of combatBoutInvariant in FOCS. Also, the gain might be small and not easy to implement, because it needs too layers of cahing (one per bout nested within one per combat):
Since some conditions will change, the final targets set must be recalculated even if some conditions where bout-invariant.
To capitalice on the boutInvariant evaluations, we could cache for the whole combat the targets for bout-invariant conditions (and cull dead targets from the set between bouts), before applying the bout-variable conditions, and apply the combat-variable conditions on each bout, and cache the resulting (final) targets set only for this bout.

Since there are only 3 bouts (2 for fighters) that can share the same set of bout-invariant (partial) targets, while there can be hundreds of weapons/fighters on a fleet that will share the same (final) targets on the same bout, I'll focus on the cache-per-bout-only approach, which I hope won't require dissallowing Value() in combatTargets nor the addition of combatBoutInvariant.

Post Reply