Computation Rewriting Part 2: Calculations

[brather1ng]

The second part of the computation rewriting (see #463) is the core calculation part.

This should do pretty much what you'd expect: put parsed stats in and get the calculated stats out.

The goal here would again be to separate the mechanics from the calculation logic as much as possible. That means, there are mostly two parts to this:

• (PR: Calculation Rewriting Part 2.1: Core Data Structure #509) The calculation data structure. Some kind of graph structure built using parsed stats where you can select nodes you want to receive value updates about (the nodes representing the stats that are shown in the UI).

• (PR: Calculation Rewriting Part 2.2: Mechanics and Builder Implementation #512) The mechanics. The builder interfaces from parsing need a non-stub implementation that will define the interaction between calculation and parsing as they (or something built from them) will be passed into the calculation data structure.
  There are also the given stats and effect stats already defined together with the parsing data that are not yet used. They will need to be passed to and used by the calculation data structure in some parsed form.

  For the main mechanics, e.g. how DPS is calculated, my idea was to define them as data similar to the given stats. E.g. add a new entry to the given stats that says something to the effect of "Value of the DPS stat = value of the damage per hit stat * value of the attacks per second stat". Defining these as data leads to a calculation data structure that doesn't need to know anything about mechanics and what it actually calculates.

• (PR: Calculation Rewriting Part 2.3: Skill and Item parsing #515) There needs to be a way to turn items and skills into modifiers

• (PR: Calculation Rewriting Part 2.4: Basic UI #517) For the computation rewriting to become usable while it is work in progress, some minor UI integration should also be done in this part. I'm thinking about a simple separate component that just shows the values of a few stats here (e.g. as a new tab next to skill tree and equipment). The larger work for that will probably be using the user's actual tree and equipment and showing the calculation conditions that need to be user specified.

I'll start with the calculation data structure. That is the most interesting part from an algorithmic point of view, so I'll post my ideas for it here. But it shouldn't be developed completely in isolation, so it will also require a bit of work on the mechanics and integration parts (not UI integration, probably some extension to the console program from parsing).

[MLanghof]

Some kind of graph structure built using parsed stats where you can select nodes you want to receive value updates about (the nodes representing the stats that are shown in the UI).

More specifically, a directed acyclic graph.

• For constructing it, the skill/item/passive mechanic interactions determine how and which nodes are created/connected. You mentioned the possibility of keeping the mechanics "specifications" in a data-driven format, but I agree that it's probably a lot of additional effort for little gain (on top of the feel/fear that the occasional unique mechanic will require special code regardless). I'd be curious to hear your ideas on this, particularly the "node" structure, which needs to be both general enough to accommodate all the possible operations, but simple enough to still be reasonably maintainable. I'll try and sketch out what I can come up with in the next few days.

• The calculation seems intuitive once the graph is built, but there are quite some subtleties to take into account. Rounding is one of them. As discussed in Discord, it might also be a good idea to "compile" the calculations for use in the GA - whether that is in the form of a symbolic math library that can reduce formulas, an actual compiler to do constant folding and optimized bytecode generation for us or anything like that. Since the intermediate values should still be accessible (see PoB "Calcs" tab), we will need different "calculation method" options and thus have to interface the calculation graph somewhere. Whether that is an entire "calculation engine" interface (this seems too high level, the implementations would likely duplicate a lot of logic), on the node level or somewhere else is still to be decided.

• On a related note, we need to figure out whether we want to track "dirty" nodes (i.e. those that need to be updated after some basic stat changes) and whether that's worth the effort over just updating everything. For normal skill tree use it's likely insignificant (especially seeing as we need updates on all intermediate values anyway if people look at them), for the GA there's hopefully a better variant (see above), but for such a thing as node powers (assuming we want to include a feature like that) it may be useful. Or maybe the GA version works there too, but:

• Changing the skill tree may potentially influence the calculation graph structure, which is detrimental in regards to the previous two points. The questions here would be:

  • Are there any skill nodes that do this (depends on the way nodes work)?
  • Are they all keystones or otherwise identifiable so that they can be treated specially (or omitted)?

  Limiting repeated calculations to a "fixed" calculation graph seems reasonable at this point (despite "find the best possible build ever" seeming like an exciting objective for the GA), but it'd better not lead to arbitrary-seeming user experience.

• An alternative approach would be to extract a subgraph for each purpose. In this sense, all possible graphs could be seen as subgraphs of a "global" one that includes all possible effects and calculations (which would need to be built only once). I don't see strong benefits for this "extract subgraphs from the global one" approach though. The ability to extract a subgraph of all nodes influencing a given set of nodes will be good to have in general regardless for the preceding points, but that shouldn't be a problem either way.

some minor UI integration should also be done in this part

I'm actually quite concerned about the UI topic. Instead of going into detail here, I have created a separate issue: #502

[brather1ng]

More specifically, a directed acyclic graph.

While I also see a directed acyclic graph as the end goal, a forest (one tree for every stat you want to look at) could be a good idea for a first solution. It should be much simpler (no need to think about where nodes can be merged/reused) but slower because it'd be a lot bigger from all the duplications. This may or may not be something that can gradually be transformed into the DAG end goal by removing duplication and merging trees. I haven't spent much time thinking about the data structure yet, but I wanted to mention this possibility.

For constructing it, the skill/item/passive mechanic interactions determine how and which nodes are created/connected. You mentioned the possibility of keeping the mechanics "specifications" in a data-driven format in , [...]

Where to draw the line between mechanics being part of the data and being part of the calculation logic is probably something that should be figured out for each mechanic on its own. There are a lot of things that can easily be represented as data (e.g. the str/dex/int conversions to other stats are already part of the given data) and others that don't really make sense there (e.g. the calculation logic should handle the different forms -- base, increased, more, overrides -- itself).

I'd be curious to hear your ideas on this, particularly the "node" structure, which needs to be both general enough to accommodate all the possible operations, but simple enough that it's still reasonably maintainable.

I don't really have any ideas on that yet. Except that the stat (with conditions), form and value distinction made by parsing probably also makes a lot of sense as the key structuring points for calculation graph nodes. Also, it probably make sense to keep each added modifier as a separate node, at least if they are not exactly the same and come from exactly the same source (see all the different conditions).

The calculation seems intuitive once the graph is built, but there are quite some subtleties to take into account. [... and the two points below]

Not much I can add to that atm. It probably would be a good solution not to solve everything with the same data structure but build at least three (slightly to a lot) different structures:

• One for the main calculations that is only rarely updated (on actually skilling nodes) and allows detailed breakdowns and all that. It might even be reasonable to entirely rebuild this one with every tree/gear change (though that shouldn't be the goal).

• One for the "preview" calculations (hovering nodes, something like "show node power", previewing gear/gem changes). This does not need to be broken down but needs to support relatively fast updates.

• One for the GA. How much this differs from the one above depends on how much compiling/optimization can be done after building it and how those skill tree nodes you mentioned that influence the graph structure are handled.

  I don't think there are many (or even not any) of those nodes that are not keystones or ascendancy nodes, so we should only need to look at them once when building the initial structure (if we keep the requirement to mark all keystones the GA should include and expand that rule to discard all special mods that are not explicitly marked). Otherwise compiling the structure to a mathematical expression would probably not be possible.

  Are there any skill nodes that do this (depends on the way nodes work)?

  With how I imagined the data structure, they definitely exist. E.g. Iron Reflexes that adds connections from evasion related nodes to armour related nodes.

[brather1ng]

Really simple example of how I imagined the data structure:

Things obviously get a lot more complex once you take conditions and conversions into account.

Basic idea of an algorithm for adding mods into the data structure:

1. Build the subtree for the added mod (the naive implementation would require reiterating through all previously added mods)
2. Traverse the existing data structure and copy the new subtree everywhere it is required. A directed acyclic graph version would not copy the subtree but add edges to it, which is a much better solution.

The naive implementation would also throw away subtrees that were not added anywhere. Preventing that should avoid reiterating all mods in the first step: if the mod links to values of other nodes, those other nodes should still be stored and would not need to be recreated.

I see the "Total" nodes as the key points for speeding up the traversal. If references to these are stored somewhere and they contain enough additional information to decide whether they (or their subtree) are affected by mods, traversal could mostly be reduced to looking at these nodes (except for mods that actually affect them).

[MLanghof]

That seems like a good start (and obviously matches your mod "syntax" very well). Some thoughts:

• Are there any "baseline" stats that aren't covered between the tree and the items? I suppose we can add anything we want to the tree, so I guess not (at least I can't come up with anything. Well, Pantheon I guess?). Do you think your stat syntax is expressive enough that we'll be able to express the entire calculation graph as the product of this long list of stats? Hm I guess that's a dumb question because we can add anything to the syntax. Still, how would some conditions (say, "enemy is chilled" or "your crit chance is lucky") enter? Presumably also stats?

• It appears there are two types of nodes here: Those that correspond directly to a stat from the input list (e.g. "5% increased life"), and those generated as consequence of others (e.g. "total life" or "increased life"). In my understanding, a stat making any mention of "life" would create a (or seek out the) "total life" node, the "increased" part then creating or finding the "increased life" node and finally adding itself as a child. But I guess that doesn't work for something like "10% increased fire damage" because there's not necessarily any one "total fire damage" it pertains to. A hypothetical "10% increased fire damage with main hand" would then also have to check that condition on every "total fire damage" node it finds. Propagating these conditions down subtrees seems pretty difficult (I guess that's your "enough additional information"). Maybe we can look at a dual wield dps calculation to learn more.

Still wrapping my head around it, I probably deleted most of what I wrote while making this comment.

(PS: What did you create those trees in?)

[brather1ng]

Are there any "baseline" stats that aren't covered between the tree and the items? I suppose we can add anything we want to the tree, so I guess not (at least I can't come up with anything. Well, Pantheon I guess?).

I'm not sure I understand you correctly. If you are talking about the stats that don't depend on the tree/items/anything variable, there's already the concept of "given" stats in the parsing data. While there's no Pantheon in the program at the moment, that would be another of the variable things.

Do you think your stat syntax is expressive enough that we'll be able to express the entire calculation graph as the product of this long list of stats? Hm I guess that's a dumb question because we can add anything to the syntax.

For most things, if they are not supported, they can be added to the builder interfaces. This comes down to the topic of representing mechanics as data or logic again. There will be some things that don't make much sense as modifiers/stats, these would need to be supported by the data structure itself. Another example for that are conversions/gains ("x% of Foo converted to Bar", "gain x% of Foo as extra Bar"). They are not just "take the value of Foo, multiply it by x/100 and add the result as base to Bar", e.g. increases only apply once.

Still, how would some conditions (say, "enemy is chilled" or "your crit chance is lucky") enter? Presumably also stats?

I'm not entirely sure yet how to handle conditions.

For your examples, "enemy is chilled" is a global condition that has the same evaluation for the entire structure. For those my idea was that each node has access to an object it can query these global conditions from. It would probably make sense to represent both evaluation cases in the data structure at once so it doesn't need to be rebuilt when conditions change. Some/most of these global conditions need to be user-specified.

"Your crit chance is lucky" would probably be implemented as a stat that modifies how effective crit chance is calculated (if we add an effective crit chance stat similar to Path of Building's).

However there are also modifier parts currently parsed as conditions that are not globally true/false. E.g. "... with main hand", "minions have ...", "... from equipped shield". These would need to be handled differently in the structure on a case-by-case basis.

But I guess that doesn't work for something like "10% increased fire damage" because there's not necessarily any one "total fire damage" it pertains to.

If we only calculate one set main skill, which I think is a very useful simplification to make, there would only be a constant number of "total fire damage" nodes: one if the damage is not hand-specific (spells), or one for main-hand and one for off-hand if the damage is hand-specific. And maybe three for each of those depending on how min/max/average damage is handled. Other nodes linking to fire damage would need to specify which one of these they want (main-hand and off-hand would probably be calculated independently, so most nodes linking to fire damage are either main-hand or off-hand themselves, same for min/max).

A hypothetical "10% increased fire damage with main hand" would then also have to check that condition on every "total fire damage" node it finds. Propagating these conditions down subtrees seems pretty difficult (I guess that's your "enough additional information").

For "10% increased fire damage with main hand" it could easily be decided which "total fire damage" node it affects: it does affect the main-hand one (both "fire damage" and "with main hand" match that node) and it doesn't affect the off-hand one ("with main hand" doesn't match).

Maybe we can look at a dual wield dps calculation to learn more.

I'll do one now.

(PS: What did you create those trees in?)

http://www.umlet.com/
It's an UML tool, but I find it pretty useful for quickly creating any kinds of graphs. Simple drag & drop plus text-editor without any dialogs.

[brather1ng]

Partial tree for dual wield DPS calculation:

I don't have any more time to expand this today. If there are any further questions I can answer by adding more to the tree, I can do that tomorrow.

[brather1ng]

I spent some time figuring out what a subgraph for a stat needs to look like independent of the mods added to it. The graph below is this subgraph with all inherent nodes explicitly added, otherwise it is similar to the graphs I posted before. It's also no longer a tree.

I also went through the builders and wrote down some notes for the mechanics I found that can't be data-driven and would need to be supported by the graph itself. These are not represented in the graph as that would make it a lot less readable.

If you don't see any issues or possible improvements here, I think it is now enough specification to actually start implementing the calculation structure. I can also wait with pushing anything if you want more time to think about this and sketch out your own ideas, @MLanghof .

There's still a lot missing, especially regarding conditions, but I feel like I need to start diving into it to solve those things as they come up.

[MLanghof]

Don't let me hold you up, you seem to have a very clear picture already, it's not like I have a better idea lying around right now.

I'm still slightly skeptical about the conversion/gain part, because the set of applicable modifiers is potentially different for every path through the "gain/convert x ->y" graph (at least in my understanding), meaning you need a separate base and uncapped subtotal node for each such path.

For example, if you convert 50% of cold to fire, 50% of lightning to fire, 50% of phys to cold and 50% of phys to lightning (and have base damage for each of those), there are five fire base values (two from phys, one from cold, one from lighting and one from fire itself), each with a unique set of applicable increases etc. - I don't see that fitting into your scheme at the moment. But maybe there's an easy solution (I don't see "make sure each mod is only applied once" being able to resolve that without intricate inter-node logic).

[brather1ng]

Yeah, what I wrote in the graph was without thinking about conversion/gain chains.

With chains, there will be repetition in the subgraphs of stats. From a design perspective, it has a somewhat easy solution. Whether that's easy to implement is another question.

For your example:

"Make sure each mod is only applied once" is relevant for the Increase (and More) nodes. They may link to the same mod for different damage types but shouldn't apply them multiple times.

[MLanghof]

So shouldn't the graph maybe be built in multiple passes then? First all nodes that depend on other nodes, then all the static ones? I guess it wouldn't solve all issues but it's probably more efficient to do it this way rather than search through all increases again after you add the fifth fire base value.

[brather1ng]

I don't think that is possible when the graph is built incrementally with each skill tree/gear change. But it wouldn't have to search through all increases again. My idea (not shown in the graph from my previous comment) is to store the modifier nodes for each stat and form somewhere and have other nodes like those Increase nodes link to that collection and only indirectly to the actual modifier nodes. So e.g. "Increase Fire, Light" would link to the increase collections of Fire damage and Lightning damage.

But when the entire graph is rebuild (e.g. on startup. changing builds or whenever else it might be necessary), it sounds like a good idea to order the modifiers in a way that makes the initial building process more efficient. Maybe the object responsible for constructing/changing the graph should always takes a collection of modifiers as parameter so it can order them (which would also be applicable to the incremental changes because a lot of tree nodes have multiple modifiers, but I don't see much speedup potential there).

[brather1ng]

The core graph structure is now done (ignoring everything "special" that has to be built in, e.g. conversion paths, see the list at the end).

The idea behind the subgraph for a stat is basically the same as my "core building block" diagram. There will be one such subgraph for each instance of an IStat interface (to be precise, IStat implementations override equality to define whether two IStat instances represent the same stat subgraph).

Edges of the graph are represented by events: When the value calculation of a node uses the value of another node, it subscribes to the ValueChanged event of that node. When modifiers are added into the graph, the respective modifier collection raises an event. Nodes subscribed to other nodes that raise events will themselves raise an event, the event propagates through the graph. This propagation itself does not recalculate any values. Instead, clients of the graph can retrieve nodes relevant to them and subscribe to them themselves. In a batch update, each node only raises the event at most once (before its value is calculated again) and clients will only receive events at the end of the batch update (after all modifiers were added). Values of nodes are cached but will always be calculated lazily.

There are two types of nodes:

• "Value" nodes: These can retrieve the values of other nodes for calculating their own value. Values of nodes are retrieved by IStat instance and the NodeType of the node in the stat's subgraph.

  These nodes are created by wrapping an IValue instance: IValue contains one method that returns a value based on an object passed to it. That object can be used to retrieve values of other nodes. The actual node calls the method on IValue and subscribes to all other nodes whose values where retrieved.

  This type of node is used both for nodes of modifiers and for the stat subgraph nodes that do not belong to the other type.

• "Aggregating" nodes: They link to a modifier node collection and calculate their value by aggregating the values of the nodes in that collection. Each Form has its own modifier node collection and aggregating node for each stat subgraph.

Adding modifiers can be done simply by retrieving the stat subgraphs for the modifier's IStats (or creating them), creating a node based on the modifier's IValue, and adding the node to the modifier node collection of each stat subgraph matching the modifier's Form.

That is all graph construction that needs to be done when adding modifiers. The subgraph's nodes will only be created when they are necessary, i.e. when their value is requested from another node's value calculation.

This model can handle most of what is required. E.g. conditions can either determine the stat of a modifier (e.g. for main hand/off hand) or be part of the value calculation (set the value to 0/null if the condition is not met). However, there a few things still left to implement for what I'd consider the first part of this issue:

• The two types of nodes probably need to be merged into just value nodes, i.e. allow value nodes to retrieve the collection of values from a modifier node collection.
• A general concept of "paths" is required. E.g. for modifier source conditions and conversion/gain mods.
  • To allow breakdowns by item slot, paths could be created by default for each modifier source as part of construction. Modifier source conditions would then simply change the source of the modifier.
  • IStat instances need to be able to create paths, e.g. for conversions.
• A general concept of "behaviors" is required for stats that change the values of stat subgraph nodes directly.
  • These are defined in IStat instances and modify the input/output values of stat subgraph nodes (by adding nodes in between).
  • Examples:
    • The "Effectiveness of Added Damage" stat applies its value as a multiplier to all damage BaseAdd nodes.
    • Stats may have different rounding behaviors. That could be implemented by modifying (i.e. rounding) outputs.
• External stats/conditions that need to be entered by users need to be registered somewhere.
  • Default values for these could be implemented as behaviors that modify the stat's Base node.
  • These also need to specify their data type.

[brather1ng]

Calculation as a whole works now and can be used through PoESkillTree.Computation.Console (in the calculation-mechanics branch). It still needs to support more mods and have a real skill data model to actually be useful, after which I'd consider task 2 of this issue done.

I'm hoping to get that and a very simple UI integration (task 3 of this issue) done before the next league starts. Would be nice to release the calculation rewriting in an alpha version with the next league.

Short example usage of PoESkillTree.Computation.Console (the "add" parts substitute the missing skill model and build connection):

> add given
> listen skill hit dps
Started listening to Character.DPS.Hit (current value: 0)
> add 90 level
Stats: Character.Level
  Form: BaseAdd
  Value: 90
  Source: Global
> add 0 hit damage source
Stats: Character.SkillHitDamageSource
  Form: BaseAdd
  Value: 0
  Source: Global
Stat changed: Character.DPS.Hit
  Current value:
> add 1 uses main hand
Stats: Character.SkillUses.MainHand
  Form: BaseAdd
  Value: 1
  Source: Global
Stat changed: Character.DPS.Hit
  Current value:
> add 1 uses off hand
Stats: Character.SkillUses.OffHand
  Form: BaseAdd
  Value: 1
  Source: Global
Stat changed: Character.DPS.Hit
  Current value:
> +1 to attack speed
Stats: Character.CastSpeed.Attack.MainHand.Skill
  Form: BaseAdd
  Value: 1
  Source: Global
Stats: Character.CastSpeed.Attack.OffHand.Skill
  Form: BaseAdd
  Value: 1
  Source: Global
Stat changed: Character.DPS.Hit
  Current value:
> adds 4 to 6 physical damage
Stats: Character.Physical.Damage.Attack.MainHand.Skill
  Form: BaseAdd
  Value: Value(min: 4, max: 6)
  Source: Global
Stats: Character.Physical.Damage.Attack.OffHand.Skill
  Form: BaseAdd
  Value: Value(min: 4, max: 6)
  Source: Global
Stats: Character.Physical.Damage.Spell.Skill
  Form: BaseAdd
  Value: Value(min: 4, max: 6)
  Source: Global
Stats: Character.Physical.Damage.Secondary.Skill
  Form: BaseAdd
  Value: Value(min: 4, max: 6)
  Source: Global
Stat changed: Character.DPS.Hit
  Current value: 1.79135885996388
> 100% increased attack speed
Stats: Character.CastSpeed.Attack.MainHand.Skill
  Form: Increase
  Value: 100
  Source: Global
Stats: Character.CastSpeed.Attack.OffHand.Skill
  Form: Increase
  Value: 100
  Source: Global
Stat changed: Character.DPS.Hit
  Current value: 3.58271771992775
> query chance to hit
Stat: Character.ChanceToHit.Attack.MainHand.Skill
  Current value: 35.8271771992775
Stat: Character.ChanceToHit.Attack.OffHand.Skill
  Current value: 35.8271771992775