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: 5704
Joined: Mon Apr 10, 2017 4:25 pm

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#16 Post by Oberlus »

I guess the cache would be good in a std::map using a std::tuple for the key.

Code: Select all

    // Declare a type for the key (very unsure about the '*', does the visibility map need also to be a pointer, or should the Conditions be passed by value or with &?)
    typedef std::tuple<int, Universe::EmpireObjectVisibilityMap, Conditions::Conditions*, Conditions::Conditions*> targettingInfo;
    // Probably I need to define a constructor for that tuple and overload operator<.

    // The cache for targets could be a map:
    std::map<targettingInfo, Condition::ObjectSet> targets_cache;
    // While bout-invariant stuff is not considered, clear the targets_cache on every bout

    // Instantiate targetting info from source, visibility and targetting conditions of species and weapons
    auto targetting_info(attacker, combat_state.combat_info.empire_object_visibility, species_targetting_condition, weapon.combat_targets);

    // Looking up the cache
    Condition::ObjectSet targets, rejected_targets;
    auto search = targets_cache.find(targetting_info);
    if (search != targets_cache.end())
        targets = targets_cache[targetting_info];
    else {    // Not found, so evaluate targets and cache them up
        AddAllObjectsSet(combat_state.combat_info.objects, targets);	// Adds to targets all objects in combat_info (i.e. planets, ships and fighters in the system)
        ScriptingContext context(attacker, combat_state.combat_info.empire_object_visibility);
        // apply species targeting condition and then weapon targeting condition
        species_targetting_condition->Eval(context, targets, rejected_targets, Condition::MATCHES);
        weapon.combat_targets->Eval(context, targets, rejected_targets, Condition::MATCHES);
        // Caching up the set of targets corresponding to a given key.
        targets_cache[targetting_info] = targets;
    }
    // Then the code for randomly selecting a target for the current weapon among the valid targets.
I don't know yet if std::tuple of non-standard types can handle comparisons with Condition::Condition*, etc. out of the box or I should overload operator< (probably), but the rest seems pretty straightforward.

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

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#17 Post by Geoff the Medio »

You definitiely do not want to use a visibility map by value as a key in a map. Every entry would then have a copy of the whole visibility map.

But I'm not really sure why you want to use a vis map as a key at all... it's a property of the combat state, and won't change during a combat round, so won't be of much use for indexing cache results, as every condition test during a combat round will have the same visibility map, and you seem to be planning to refresh the target sets each combat round anyway...

Pointers should be comparable with < which means they should be usable as a key in a map. But why you'd want to do this is unclear. You might as well store a tuple of part class and part name instead of part targetting condition, as each part will have a separate targetting condition object, which will have a different address from all the other, even if they are actually the same scripted condition. There is not really a useful way to sort conditions by value at present.

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

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#18 Post by Oberlus »

Geoff the Medio wrote: Thu Feb 20, 2020 6:27 am You definitiely do not want to use a visibility map by value as a key in a map. Every entry would then have a copy of the whole visibility map.

But I'm not really sure why you want to use a vis map as a key at all... it's a property of the combat state, and won't change during a combat round, so won't be of much use for indexing cache results, as every condition test during a combat round will have the same visibility map, and you seem to be planning to refresh the target sets each combat round anyway...
Roger. So I must use only empire id and the targetting conditions.
Geoff the Medio wrote: Thu Feb 20, 2020 6:27 amPointers should be comparable with < which means they should be usable as a key in a map. But why you'd want to do this is unclear. You might as well store a tuple of part class and part name instead of part targetting condition, as each part will have a separate targetting condition object, which will have a different address from all the other, even if they are actually the same scripted condition. There is not really a useful way to sort conditions by value at present.
The idea is to define some comparator of Condition::Condition*. I don't know yet how are Conditions implemented internally.

What's a struct MatchHelper? Can't find it anywhere.


Assuming conditions can be abstracted like these:

Condition A: IsVisible && (IsShip || IsPlanet) && !IsDestroyed && !(OwnerEmpireIs(X) || OwnerEmpireIs(Y))
Condition B: IsVisible && (IsShip || IsPlanet) && !IsDestroyed && !(OwnerEmpireIs(Y) || OwnerEmpireIs(Z))

Or maybe like this:

Condition A: AND( IsVisible, OR(IsShip, IsPlanet), NOT(IsDestroyed), NOT(OR(OwnerEmpireIs(X), OwnerEmpireIs(Y))))


And assuming also that:
  • you can iterate over the condition elements, considering also parenthesis, operators and whatnot, such as "IsVisible", "&&", "(", etc.,
  • the elements can be treated as strings with a consistent operator <,
  • and the elements are "ordered" in some way so that any two pairs of conditions (like "IsVisible" and IsDestroyed) are going to appear always in the same order when at the same level within a commutative operator (*).
We could do something like

Code: Select all

Operator Condition A < Condition B
    if(A.size() < B.size)    // size: number of elements
        return true;
    else if(A.size() == B.size) {
        for( i = 0; i<A.size(); i++) {
            if (A[i] < B[i])    // A[i] is a string; what is considered greater than what is not relevant as long as it is done consistently 
                return true
            else if (A[i] > B[i])
                return false
        }
    }
    return false

* So that AND(Visible,Destroyed) will always appear as that and never as AND(Destroyed,Visible), because both conditions are equivalent but their elements are in a different order, and so a string-based comparition would wrongly return they are different.

Are conditions internally ordered or can they be forced to be?

Or better, where can I see the guts of those conditions?

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

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#19 Post by Ophiuchus »

Oberlus wrote: Wed Feb 19, 2020 3:42 pm
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 meant logically deducing if a condition tree is invariant/which keys you would need to use for caching (external deducing as contrasted to internal composition based like the *invariant functions). Would be done once in the game.
Oberlus wrote: Wed Feb 19, 2020 3:42 pm
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?
No I am talking about ValueRefs in conditions. If you use Value or Value(..) you get the immediate value as opposed to the current value. The current value is the value before effects are applied. The immediate value can change during effect evaluation. So Value(Target.Structure) in combat would change during a bout if the target is hit and you could implement e.g. (semi-)perfect targeting with it, preventing shot overkill.

Also allowing/disallowing immediate values are important for the combat system - if you allow for immediate values, the order of shooting suddenly matters. Currently the system is based on randomized shooters. So if you start sorting shots/having a non-random order, the combat system changes.

The *Invariant functions are part of the conditions, they have nothing to do with actual targets, they do not need a cache. E.g. an AND condition would be combatBoutInvariant when all its subconditions are combatBoutInvariant. And i think only conditions which return the immediate value are not combatBoutInvariant. If you want to cache you would simply call combatBoutInvariant on the condition and if it returns true it is OK to cache.

Actually this kind of bout invariance does not buy much.
Probably better add a cacheKeys function to the conditions returning properties which one would need to cache such a condition. E.g. for Visibility: Source.Detection, Target.Stealth, for species dependent: Source.Species, for comparing a target structure valref: Target.Structure

Or simply give conditions IDs and handle the few well known common conditions.
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: 13586
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#20 Post by Geoff the Medio »

Oberlus wrote: Thu Feb 20, 2020 10:06 amSo I must use only empire id and the targetting conditions.
Not really, as using conditions doesn't make much sense, and it would probably make more sense to index by things like part type and class...
Geoff the Medio wrote: Thu Feb 20, 2020 6:27 amYou might as well store a tuple of part class and part name instead of part targetting condition, as each part will have a separate targetting condition object, which will have a different address from all the other, even if they are actually the same scripted condition.
The idea is to define some comparator of Condition::Condition*.
When creating a map, you can specify a custom sort operator, which can compare two pointer types by dereferencing them and comparing the pointed-to values. But doing this usefully for a base-class pointer will require either having a bunch of casts or double-dispatch on the pointed-to types, or a way to get a sortable single representation of the pointed-to object that doesn't require knowing its type.
I don't know yet how are Conditions implemented internally.
Condition itself has no relevant internal state; it's just a abstract / virtual base class that is derived from by all the actual condition classes. This is a complication for you, as you don't have a bunch of Condition objects, but rather a bunch of pointers to objects of class derived from Condition, which all difficult to simply compare is any meaningful way...
What's a struct MatchHelper? Can't find it anywhere.
See: https://github.com/freeorion/freeorion/ ... s.cpp#L243
iterate over the condition elements, considering also parenthesis, operators and whatnot, such as "IsVisible", "&&", "(", etc.,
Not sure what a "condition element" is.
elements can be treated as strings with a consistent operator <
[...]

Code: Select all

if (A[i] < B[i])    // A[i] is a string; what is considered greater than what is not relevant as long as it is done consistently
Ordering two arbitrary conditions is probably more complicated than you're thinking, mainly because there is not just one Condition class, but a variety of derived classes that can have varying numbers and types of member variables, from none for simpler conditions like "All" or "Source", to multiple sub-conditions and contained ValueRefs, which themselves could have further sub-conditions or ValueRefs. Conditions generally have serialize (convert to string in a reversible way) functions, but I'd be hestitant to plan to use those for sorting, though it might work in practice.
AND(Visible,Destroyed) will always appear as that and never as AND(Destroyed,Visible)
That is not supported by serialize functions.
Are conditions internally ordered or can they be forced to be?
Assuming you mean are the sub-conditions of And and Or conditions ordered somehow, they are ordered as they are defined in scripts, and this shouldn't be changed, as in some cases the meaning is not the same if they are reordered, and often the efficiency of evaluation will be different if they are reordered.
Or better, where can I see the guts of those conditions?
https://github.com/freeorion/freeorion/ ... nditions.h and https://github.com/freeorion/freeorion/ ... itions.cpp

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

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#21 Post by Oberlus »

Geoff the Medio wrote: Fri Feb 21, 2020 10:07 amusing conditions doesn't make much sense, and it would probably make more sense to index by things like part type and class...
I'm convinced of this now.Thank you for the guiding.
Geoff the Medio wrote: Fri Feb 21, 2020 10:07 amNot sure what a "condition element" is.
Not relevant now, but I mean each atomic part of a written representation of the condition (not a logical representation), the same way I could represent numbers with strings and use those strings to map them (alphabetical order), as long as +3, 3 and 3.0 are converted to the same string before indexing.

Interesting enough, when searching for MatchHelper using the github.com interface, I do not get results for Conditions.h or Conditions.cpp, only Condition.h.

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

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#22 Post by Oberlus »

Ophiuchus wrote: Thu Feb 20, 2020 11:41 amAlso allowing/disallowing immediate values are important for the combat system - if you allow for immediate values, the order of shooting suddenly matters. Currently the system is based on randomized shooters. So if you start sorting shots/having a non-random order, the combat system changes.
I'm thinking of the following to remove all influence of ordering on the combat (i.e. fully simultaneous):

On each bout:

For loop over attackers, evaluating targetting conditions (or looking them up in the cache if implemented), picking up targets and storing them.
For loop over attackers again, calling to the functions that deal actual damage.

Weapons like missiles (i.e. that depend on the most recent value of their own structure to deal or not damage) that were targetted during this bout could refrain form dealing damage without the need for a whole bout flying.
Weapons with targetting conditions that depend on the structure of the targets would also have no dependency on the order of attackers.

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

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#23 Post by Geoff the Medio »

Oberlus wrote: Fri Feb 21, 2020 10:38 amOn each bout:

For loop over attackers, evaluating targetting conditions (or looking them up in the cache if implemented), picking up targets and storing them.
For loop over attackers again, calling to the functions that deal actual damage.
Should be fine...

If you want to caching to be general, though, you'd have to check for invariance to whatever you use to index the cache. Almost all targetting conditions aren't source-invariance, and indexing for each source would make the cache useless. So you might need to add a SourceInvariantOtherThanOwner property to conditions. That would be the same a SourceInvariant, except it wouldn't count references to Source.Owner as breaking the invariance. If that was implemented, you could index the cache by a tuple of <owner, part type, part class, species>, which would be actually potentially useful, since all ships with the same design owned by the same owner with the same species and whose targetting conditions don't otherwise depend on properties of the attacker would be able to share the cached results.

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

Re: Reviewing attackers/targets processing in CombatSystem.cpp

#24 Post by Oberlus »

Geoff the Medio wrote: Fri Feb 21, 2020 2:11 pm you could index the cache by a tuple of <owner, part type, part class>
I'm thinking on creating a GG_ENUM for WeaponTargetingClass and indexing by that and empire owner.
Different tuples part_type_name,part_class can have de same targetting conditions, e.g. death ray and plasma, or interceptor and flak.
A function GetWeaponTargettingClass(part_type_name,part_class) would return the right one.

Edit:

Problem with this is it makes backend rigid, would not accept user modding: if I add a new weapon or change the targetting rules of an existing one in FOCS...
So discarded.

Post Reply