FOCS Condition implementation

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

Moderator: Committer

Post Reply
Message
Author
User avatar
adrian_broher
Programmer
Posts: 1156
Joined: Fri Mar 01, 2013 9:52 am
Location: Germany

FOCS Condition implementation

#1 Post by adrian_broher »

What is the point of the ObjectSets, that are passed arround during evaluation?

Why are there matches and non_matches?

Why was this design chosen over a predicate design (pass in the object under evaluation and return if the condition applies as boolean value)?
Resident code gremlin
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz

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

Re: FOCS Condition implementation

#2 Post by Ophiuchus »

Not the authorative answer: i guess performance

non_matches and matches allow for shortcutting of calculation.

You can handle multiple objects at once instead of handling each object separately.

Also because it is breadth first instead of depht first, putting the most significant condition first will reduce computation time.
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: FOCS Condition implementation

#3 Post by Geoff the Medio »

The main purpose of conditions is to filter a set of candidate objects, not to match single objects independently. Passing, working on, and returning sets of (potential) matches is thus more fitting for the purpose.

Matching sets rather than each object independently also allows optimizations. Many conditions have parameters or sub-conditions that control how they match candidates. In some cases, those parameters or subconditions can be evaluated once and applied for all candidate objects. If each candidate was matched independently, then the parameters or subconditions would have to be evaluated again for each candidate. For example, a condition might match objects if they have a stealth meter less the sum of all the population meters of planets owned by an empire. That sum doesn't need to be calculated separately for each candidate as long as it doesn't directly refer to the candidate object in its script.

Conditions often do use a predicate system: the Match functions. For many of the conditions, especially simpler ones like ObjectType (Planet, System, Ship, etc.), there are Match functions that are used by the default base-class condition Eval function as a predicate that is applied to candidate objects to filter them for transfer between the matches and non_matches sets. But for some cases, using a predicate doesn't make sense or would be inefficient, in which case the overridden Eval function might not use a Match function.

The reason for having both matches and non_matches set is for evaluation of conditions like And, Or, and Not when they are composed as subconditions to eachother. Not And [Ship Unowned] doesn't need to propagate the negation into the subcondition(s), since it remembers all of the candidates at each step. All candidates would be put into the matches set and checked if they are ships. Those that aren't would be moved to non_matches. Then all remaining matches would be checked if they are unowned. Those that aren't would also be moved into non_matches. Then the matches and non_matches sets would be swapped due to the negation. For the Or condition, it puts candidates in matches, then filters matches with the first subcondition, whereas all additional subcondition are used to filter non_matches to see if they should be moved into matches. Anything already in matches after the first filter doesn't need to be tested again with any other subconditions.

User avatar
adrian_broher
Programmer
Posts: 1156
Joined: Fri Mar 01, 2013 9:52 am
Location: Germany

Re: FOCS Condition implementation

#4 Post by adrian_broher »

Matching sets rather than each object independently also allows optimizations. Many conditions have parameters or sub-conditions that control how they match candidates. In some cases, those parameters or subconditions can be evaluated once and applied for all candidate objects. If each candidate was matched independently, then the parameters or subconditions would have to be evaluated again for each candidate. For example, a condition might match objects if they have a stealth meter less the sum of all the population meters of planets owned by an empire. That sum doesn't need to be calculated separately for each candidate as long as it doesn't directly refer to the candidate object in its script.
So that's the reason for the clunkyness. However why shouldn't subconditions not store their evaluation result, if the do not depend on the candidate? That's the whole point of the invariances parameters, right? Adding a value cache to the condition and an epoche for identifying the validity for the cached value would achieve the same.
Resident code gremlin
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz

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

Re: FOCS Condition implementation

#5 Post by Geoff the Medio »

Conditions could be made to cache their results, but currently, in some cases, the code that evaluates a condition caches the results. The extra context the calling code has makes deciding when to do this easier, I think. As noted, within a containing condition, effect, or valueref, invariance tests are used to decide whether to evaluate once or per-candidate. Also, Universe::GetEffectsAndTargets stores a cache of condition results during its evaluation, keyed by source object.

If you are proposing a more-persistent cache, that would be difficult to keep current, I think. Determining when a cached condition result would become invalid would be complicated for arbitrary conditions, if there is to be any level of specificity beyond any time the gamestate changes.

User avatar
adrian_broher
Programmer
Posts: 1156
Joined: Fri Mar 01, 2013 9:52 am
Location: Germany

Re: FOCS Condition implementation

#6 Post by adrian_broher »

> If you are proposing a more-persistent cache
I'm currently still trying to grasp the setup so I propose nothing yet.

The problem is that I see the current implementation it makes my toe nails curls, nothing more, nothing less.
Resident code gremlin
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz

Post Reply