0002919: Army lose creature bonuses like Archangels morale +1 after stacks are joined

(0007504)
hkoehler (developer)
2018-03-17 06:29
edited on: 2018-03-17 08:00

* No bonus added in creatures/castle.json
* Some morale bonuses are handled here in CArmedInstance::updateMoraleBonusFromArmy(), but not Angel bonus by the looks of it
* Note to self: "get config" console command extracts the bonus from legacy data:
"const_raises_morale" : {
    "propagator" : "HERO",
    "type" : "MORALE",
    "val" : 1
}
* CBonusSystemNode::bonuses holds propagated bonuses
* When removing 1st of 2 angels, you get error "Bonus was duplicated (Angels +1) at Hero Caitlin", coming from
void CBonusSystemNode::unpropagateBonus(std::shared_ptr<Bonus> b)
{
    if(b->propagator->shouldBeAttached(this))
    {
        bonuses -= b;
        while(vstd::contains(bonuses, b))
        {
            logBonus->error("Bonus was duplicated (%s) at %s", b->Description(), nodeName());
            bonuses -= b;
        }
        logBonus->trace("#$# %s #is no longer propagated to# %s", b->Description(), nodeName());
    }

    FOREACH_RED_CHILD(child)
        child->unpropagateBonus(b);
}
* So looks like issue is basic propagation/unpropagation handling - each angel adds one bonus, unpropagate removes them both ...
* In this case it's actually the same pointer, stored twice
* In CBonusSystemNode::getAllBonuses, the call of eliminateDuplicates ensures that this duplicate bonus isn't counted twice.

(0007505)
AVS (administrator)
2018-03-17 08:21

Looks like a bug in propagation implementation.
1) bonus source is creature type
2) bonus is propagated from creature type to each (Angel) stack instance
3) from each stack instance bonus is propagated to the hero and duplicates

(0007506)
AVS (administrator)
2018-03-17 08:29

Possible quick fix could be adding vstd::contains(bonuses, b) check to CBonusSystemNode::propagateBonus

More clean fix:
rewrite propagateBonus by collecting set of all red children and then process them

(0007507)
hkoehler (developer)
2018-03-17 08:45
edited on: 2018-03-17 08:47

The issue isn't just that we have duplicate bonuses. Even if we eliminate those, unpropagate would still remove the bonus causing the bug. So either:

1) We keep duplicates (one per stack) and unpropagate only removes one copy. getAllBonuses eliminates the duplicates for calculation. Not very pretty and has overheads, but works?

2) We remove duplicates, and have special handling for stacks, unpropagating only when the last stack of a creature type is removed. Won't work if different stacks propagate different bonuses (is that a possiblity), and not pretty either.

3) When unpropagating, we tell parent to clear itself and re-gather propagated bonuses from its children (recursively). Clean, but possibly time-consuming.

I reckon 3) is the preferred method if it doesn't cause performance issues. Due to the tree-like nature of the propagation/inheritance graph it'll likely be more expensive than the current dynamic inheritance approach, but I suspect it'll still be ok.

(0007508)
hkoehler (developer)
2018-03-17 08:51

Actually for 3), we wouldn't need to clear everything - just to tell the parent to check whether it still receives the bonus from one of its children. That should solve the performance issue.

(0007509)
AVS (administrator)
2018-03-17 08:53

I suspect that "3" equal complete tree rebuild each time because propagation works up to the tree roots.

(0007510)
AVS (administrator)
2018-03-17 08:56
edited on: 2018-03-17 08:57

OTOH any bonus change invalidates all caches, so it should _not_ be much slower even if we reapply all propagation each time node is detached.

(0007511)
hkoehler (developer)
2018-03-17 08:58

Hmm - you are right, as to find out what the children propagate they need to ask their children etc. Will need to think on this.

(0007512)
AVS (administrator)
2018-03-17 09:19

We can go other way.
1) Propagated/inherited bonuses are transient (not serialized) so we could easily change how they are stored without worrying about compatibility.

2) For each propagated bonus store also pointer to (direct red parent) source node and save all duplicates too. (We have to eliminate duplicates during read operation anyway because of inheritance)

3) when node is detached pass `this` to red parent along with bonus pointer so we can remove bonus came form actually detached node.

(0007513)
hkoehler (developer)
2018-03-17 09:22

That sounds like option 1), just more complex. Maybe simply keeping duplicates and only removing one of them with each unpropagate isn't the worst design.

(0007514)
AVS (administrator)
2018-03-17 10:37

* Say we have same bonus with PLAYER propagator (angel +1 morale to all heroes of a player) and hero (with 2 stacks of angels) is detached from player node (f.e. it happens also on entering town)
* we have one Bonus object in creature node, player have 2 copies from this hero
* it will be one unpropagate operation for this bonus but we shoudl remove two copies (and there might me more from other heroes).

(0007515)
hkoehler (developer)
2018-03-17 12:12

If I understand the propagation mechanism correctly, the core of unpropagation when removing a hero from player happens here:

void CBonusSystemNode::removedRedDescendant(CBonusSystemNode *descendant)
{
    for(auto b : exportedBonuses)
        if(b->propagator)
            descendant->unpropagateBonus(b);

    FOREACH_RED_PARENT(parent)
        parent->removedRedDescendant(descendant);
}

Here the player notifies its red parents (in particular the two stacks of angels) to remove themselves from the player, each of which passes this command on towards the creature type. That's two calls of unpropagateBonus, each of which will remove one instance of the bonus from player. No?

Basically the unpropagation paths should be the same as for propagation ...

(0007516)
AVS (administrator)
2018-03-17 12:56

You`re right, it should work

(0007517)
SXX (administrator)
2018-03-17 14:19

BTW while we on it, might be we'll make it possible to have duplicate bonuses from duplicate sources?

E.g in H3 you might have two duplicate artifacts that give you resources on single hero and both of them will work, but in VCMI only one will. Might be we should make it possible to optionally make such bonuses additive?

Not very important problem, but should make our bonus system even more flexible.

(0007518)
AVS (administrator)
2018-03-17 14:28

SXX, bonus duplicates produced by inheritance too (by design). To correctly process multiple copies of same bonus we need to rewrite inheritance algorithm (aka Black Tree).

(0007519)
hkoehler (developer)
2018-03-17 19:30
edited on: 2018-03-17 20:14

I think all we'd need to do to the inheritance algorithm is to not explicitly eliminate duplicates. Then when summing up bonuses vals we can choose to either eliminate duplicates there or not, based on some new bonus parameter.

This approach may also help with the related issue of angel + archangel morale bonus stacking (0001266, 0002517) when it shouldn't:
* New bonus parameter stacking_group
* When set to special value STACKING_ALWAYS duplicates are kept, and stack with other bonuses with STACKING_ALWAYS
* When set to other value, duplicates are eliminated and it doesn't stack with other vals of same stacking_group (only max counts).
* When stacking_group is not specified (when parsing json), assign special value STACKING_OTHER, which will cause it to stack with everything except duplicates.

That way we could give angels and archangels the same stacking_id, and an artifact where we want duplicates to stack just gets set to STACKING_ALWAYS.
And current default behaviour is unchanged.

And I guess a good policy for assigning stacking groups to creatures is to just use the creature id of the base creature:

"angel" : {
    ...
    "const_raises_morale" : {
        "propagator" : "HERO",
        "type" : "MORALE",
        "val" : 1,
        "stacking" : "creature.angel"
    },
    ...
},
"archAngel" : {
    ...
    "const_raises_morale" : {
        "propagator" : "HERO",
        "type" : "MORALE",
        "val" : 1,
        "stacking" : "creature.angel"
    },
    ...
}

"endlessSackOfGold" : {
    ...
    {
        "subtype" : "resource.gold",
        "type" : "GENERATE_RESOURCE",
        "val" : 1000,
        "valueType" : "BASE_NUMBER",
        "stacking" : "STACKING_ALWAYS"
    }
    ...
}

(0007520)
Warmonger (administrator)
2018-03-17 21:05

Looks like the last option is what the bonus systems needs, anyway. So it's not a "fix", rather finally proper implementation.

(0007551)
SXX (administrator)
2018-03-27 07:57

Fixed:
https://github.com/vcmi/vcmi/pull/433 [^]

Issue History
Date Modified	Username	Field	Change
2018-03-17 05:13	SXX	New Issue
2018-03-17 05:13	SXX	Description Updated	View Revisions
2018-03-17 05:42	hkoehler	Assigned To	=> hkoehler
2018-03-17 05:42	hkoehler	Status	new => assigned
2018-03-17 06:29	hkoehler	Note Added: 0007504
2018-03-17 06:38	hkoehler	Note Edited: 0007504	View Revisions
2018-03-17 07:34	hkoehler	Note Edited: 0007504	View Revisions
2018-03-17 07:44	hkoehler	Note Edited: 0007504	View Revisions
2018-03-17 07:44	hkoehler	Note Edited: 0007504	View Revisions
2018-03-17 07:46	hkoehler	Note Edited: 0007504	View Revisions
2018-03-17 07:48	hkoehler	Note Edited: 0007504	View Revisions
2018-03-17 08:00	hkoehler	Note Edited: 0007504	View Revisions
2018-03-17 08:06	hkoehler	Relationship added	related to 0002517
2018-03-17 08:19	hkoehler	Relationship added	related to 0001266
2018-03-17 08:21	AVS	Note Added: 0007505
2018-03-17 08:29	AVS	Note Added: 0007506
2018-03-17 08:45	hkoehler	Note Added: 0007507
2018-03-17 08:47	hkoehler	Note Edited: 0007507	View Revisions
2018-03-17 08:51	hkoehler	Note Added: 0007508
2018-03-17 08:53	AVS	Note Added: 0007509
2018-03-17 08:56	AVS	Note Added: 0007510
2018-03-17 08:57	AVS	Note Edited: 0007510	View Revisions
2018-03-17 08:58	hkoehler	Note Added: 0007511
2018-03-17 09:19	AVS	Note Added: 0007512
2018-03-17 09:22	hkoehler	Note Added: 0007513
2018-03-17 10:37	AVS	Note Added: 0007514
2018-03-17 12:12	hkoehler	Note Added: 0007515
2018-03-17 12:56	AVS	Note Added: 0007516
2018-03-17 14:19	SXX	Note Added: 0007517
2018-03-17 14:28	AVS	Note Added: 0007518
2018-03-17 19:30	hkoehler	Note Added: 0007519
2018-03-17 19:33	hkoehler	Note Edited: 0007519	View Revisions
2018-03-17 19:34	hkoehler	Note Edited: 0007519	View Revisions
2018-03-17 19:53	hkoehler	Note Edited: 0007519	View Revisions
2018-03-17 20:14	hkoehler	Note Edited: 0007519	View Revisions
2018-03-17 21:05	Warmonger	Note Added: 0007520
2018-03-19 07:20	hkoehler	Relationship added	related to 0001555
2018-03-27 07:57	SXX	Note Added: 0007551
2018-03-27 07:57	SXX	Status	assigned => resolved
2018-03-27 07:57	SXX	Fixed in Version	=> 1.next
2018-03-27 07:57	SXX	Resolution	open => fixed

Notes
(0007504) hkoehler (developer) 2018-03-17 06:29 edited on: 2018-03-17 08:00	* No bonus added in creatures/castle.json * Some morale bonuses are handled here in CArmedInstance::updateMoraleBonusFromArmy(), but not Angel bonus by the looks of it * Note to self: "get config" console command extracts the bonus from legacy data: "const_raises_morale" : { "propagator" : "HERO", "type" : "MORALE", "val" : 1 } * CBonusSystemNode::bonuses holds propagated bonuses * When removing 1st of 2 angels, you get error "Bonus was duplicated (Angels +1) at Hero Caitlin", coming from void CBonusSystemNode::unpropagateBonus(std::shared_ptr<Bonus> b) { if(b->propagator->shouldBeAttached(this)) { bonuses -= b; while(vstd::contains(bonuses, b)) { logBonus->error("Bonus was duplicated (%s) at %s", b->Description(), nodeName()); bonuses -= b; } logBonus->trace("#$# %s #is no longer propagated to# %s", b->Description(), nodeName()); } FOREACH_RED_CHILD(child) child->unpropagateBonus(b); } * So looks like issue is basic propagation/unpropagation handling - each angel adds one bonus, unpropagate removes them both ... * In this case it's actually the same pointer, stored twice * In CBonusSystemNode::getAllBonuses, the call of eliminateDuplicates ensures that this duplicate bonus isn't counted twice.

(0007505) AVS (administrator) 2018-03-17 08:21	Looks like a bug in propagation implementation. 1) bonus source is creature type 2) bonus is propagated from creature type to each (Angel) stack instance 3) from each stack instance bonus is propagated to the hero and duplicates

(0007506) AVS (administrator) 2018-03-17 08:29	Possible quick fix could be adding vstd::contains(bonuses, b) check to CBonusSystemNode::propagateBonus More clean fix: rewrite propagateBonus by collecting set of all red children and then process them

(0007507) hkoehler (developer) 2018-03-17 08:45 edited on: 2018-03-17 08:47	The issue isn't just that we have duplicate bonuses. Even if we eliminate those, unpropagate would still remove the bonus causing the bug. So either: 1) We keep duplicates (one per stack) and unpropagate only removes one copy. getAllBonuses eliminates the duplicates for calculation. Not very pretty and has overheads, but works? 2) We remove duplicates, and have special handling for stacks, unpropagating only when the last stack of a creature type is removed. Won't work if different stacks propagate different bonuses (is that a possiblity), and not pretty either. 3) When unpropagating, we tell parent to clear itself and re-gather propagated bonuses from its children (recursively). Clean, but possibly time-consuming. I reckon 3) is the preferred method if it doesn't cause performance issues. Due to the tree-like nature of the propagation/inheritance graph it'll likely be more expensive than the current dynamic inheritance approach, but I suspect it'll still be ok.

(0007508) hkoehler (developer) 2018-03-17 08:51	Actually for 3), we wouldn't need to clear everything - just to tell the parent to check whether it still receives the bonus from one of its children. That should solve the performance issue.

(0007509) AVS (administrator) 2018-03-17 08:53	I suspect that "3" equal complete tree rebuild each time because propagation works up to the tree roots.

(0007510) AVS (administrator) 2018-03-17 08:56 edited on: 2018-03-17 08:57	OTOH any bonus change invalidates all caches, so it should _not_ be much slower even if we reapply all propagation each time node is detached.

(0007511) hkoehler (developer) 2018-03-17 08:58	Hmm - you are right, as to find out what the children propagate they need to ask their children etc. Will need to think on this.

(0007512) AVS (administrator) 2018-03-17 09:19	We can go other way. 1) Propagated/inherited bonuses are transient (not serialized) so we could easily change how they are stored without worrying about compatibility. 2) For each propagated bonus store also pointer to (direct red parent) source node and save all duplicates too. (We have to eliminate duplicates during read operation anyway because of inheritance) 3) when node is detached pass `this` to red parent along with bonus pointer so we can remove bonus came form actually detached node.

(0007513) hkoehler (developer) 2018-03-17 09:22	That sounds like option 1), just more complex. Maybe simply keeping duplicates and only removing one of them with each unpropagate isn't the worst design.

(0007514) AVS (administrator) 2018-03-17 10:37	* Say we have same bonus with PLAYER propagator (angel +1 morale to all heroes of a player) and hero (with 2 stacks of angels) is detached from player node (f.e. it happens also on entering town) * we have one Bonus object in creature node, player have 2 copies from this hero * it will be one unpropagate operation for this bonus but we shoudl remove two copies (and there might me more from other heroes).

(0007515) hkoehler (developer) 2018-03-17 12:12	If I understand the propagation mechanism correctly, the core of unpropagation when removing a hero from player happens here: void CBonusSystemNode::removedRedDescendant(CBonusSystemNode *descendant) { for(auto b : exportedBonuses) if(b->propagator) descendant->unpropagateBonus(b); FOREACH_RED_PARENT(parent) parent->removedRedDescendant(descendant); } Here the player notifies its red parents (in particular the two stacks of angels) to remove themselves from the player, each of which passes this command on towards the creature type. That's two calls of unpropagateBonus, each of which will remove one instance of the bonus from player. No? Basically the unpropagation paths should be the same as for propagation ...

(0007516) AVS (administrator) 2018-03-17 12:56	You`re right, it should work

(0007517) SXX (administrator) 2018-03-17 14:19	BTW while we on it, might be we'll make it possible to have duplicate bonuses from duplicate sources? E.g in H3 you might have two duplicate artifacts that give you resources on single hero and both of them will work, but in VCMI only one will. Might be we should make it possible to optionally make such bonuses additive? Not very important problem, but should make our bonus system even more flexible.

(0007518) AVS (administrator) 2018-03-17 14:28	SXX, bonus duplicates produced by inheritance too (by design). To correctly process multiple copies of same bonus we need to rewrite inheritance algorithm (aka Black Tree).

(0007519) hkoehler (developer) 2018-03-17 19:30 edited on: 2018-03-17 20:14	I think all we'd need to do to the inheritance algorithm is to not explicitly eliminate duplicates. Then when summing up bonuses vals we can choose to either eliminate duplicates there or not, based on some new bonus parameter. This approach may also help with the related issue of angel + archangel morale bonus stacking (0001266, 0002517) when it shouldn't: * New bonus parameter stacking_group * When set to special value STACKING_ALWAYS duplicates are kept, and stack with other bonuses with STACKING_ALWAYS * When set to other value, duplicates are eliminated and it doesn't stack with other vals of same stacking_group (only max counts). * When stacking_group is not specified (when parsing json), assign special value STACKING_OTHER, which will cause it to stack with everything except duplicates. That way we could give angels and archangels the same stacking_id, and an artifact where we want duplicates to stack just gets set to STACKING_ALWAYS. And current default behaviour is unchanged. And I guess a good policy for assigning stacking groups to creatures is to just use the creature id of the base creature: "angel" : { ... "const_raises_morale" : { "propagator" : "HERO", "type" : "MORALE", "val" : 1, "stacking" : "creature.angel" }, ... }, "archAngel" : { ... "const_raises_morale" : { "propagator" : "HERO", "type" : "MORALE", "val" : 1, "stacking" : "creature.angel" }, ... } "endlessSackOfGold" : { ... { "subtype" : "resource.gold", "type" : "GENERATE_RESOURCE", "val" : 1000, "valueType" : "BASE_NUMBER", "stacking" : "STACKING_ALWAYS" } ... }

(0007520) Warmonger (administrator) 2018-03-17 21:05	Looks like the last option is what the bonus systems needs, anyway. So it's not a "fix", rather finally proper implementation.

(0007551) SXX (administrator) 2018-03-27 07:57	Fixed: https://github.com/vcmi/vcmi/pull/433 [^]