CBonusSystemNode.cpp 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644
  1. /*
  2. * CBonusSystemNode.cpp, part of VCMI engine
  3. *
  4. * Authors: listed in file AUTHORS in main folder
  5. *
  6. * License: GNU General Public License v2.0 or later
  7. * Full text of license available in license.txt file, in main folder
  8. *
  9. */
  10. #include "StdInc.h"
  11. #include "CBonusSystemNode.h"
  12. #include "Limiters.h"
  13. #include "Updaters.h"
  14. #include "Propagators.h"
  15. VCMI_LIB_NAMESPACE_BEGIN
  16. constexpr bool cachingEnabled = true;
  17. static std::atomic<int32_t> globalCounter = 1;
  18. std::shared_ptr<Bonus> CBonusSystemNode::getLocalBonus(const CSelector & selector)
  19. {
  20. auto ret = bonuses.getFirst(selector);
  21. if(ret)
  22. return ret;
  23. return nullptr;
  24. }
  25. std::shared_ptr<const Bonus> CBonusSystemNode::getFirstBonus(const CSelector & selector) const
  26. {
  27. auto ret = bonuses.getFirst(selector);
  28. if(ret)
  29. return ret;
  30. TCNodes lparents;
  31. getParents(lparents);
  32. for(const CBonusSystemNode *pname : lparents)
  33. {
  34. ret = pname->getFirstBonus(selector);
  35. if (ret)
  36. return ret;
  37. }
  38. return nullptr;
  39. }
  40. void CBonusSystemNode::getParents(TCNodes & out) const /*retrieves list of parent nodes (nodes to inherit bonuses from) */
  41. {
  42. for(const auto * elem : parentsToInherit)
  43. out.insert(elem);
  44. }
  45. void CBonusSystemNode::getAllParents(TCNodes & out) const //retrieves list of parent nodes (nodes to inherit bonuses from)
  46. {
  47. for(auto * parent : parentsToInherit)
  48. {
  49. // Diamond found! One of the parents of the targeted node can be discovered in two ways.
  50. // For example, a hero has been attached to both the player node and the global node (to which the player node is also attached).
  51. // This is illegal and can be a source of duplicate bonuses.
  52. assert(out.count(parent) == 0);
  53. out.insert(parent);
  54. parent->getAllParents(out);
  55. }
  56. }
  57. void CBonusSystemNode::getAllBonusesRec(BonusList &out) const
  58. {
  59. BonusList beforeUpdate;
  60. for(const auto * parent : parentsToInherit)
  61. parent->getAllBonusesRec(beforeUpdate);
  62. bonuses.getAllBonuses(beforeUpdate);
  63. for(const auto & b : beforeUpdate)
  64. {
  65. auto updated = b->updater ? getUpdatedBonus(b, b->updater) : b;
  66. out.push_back(updated);
  67. }
  68. }
  69. TConstBonusListPtr CBonusSystemNode::getAllBonuses(const CSelector &selector, const std::string &cachingStr) const
  70. {
  71. if (cachingEnabled)
  72. {
  73. // If a bonus system request comes with a caching string then look up in the map if there are any
  74. // pre-calculated bonus results. Limiters can't be cached so they have to be calculated.
  75. if (cachedLast == nodeChanged && !cachingStr.empty())
  76. {
  77. RequestsMap::const_accessor accessor;
  78. //Cached list contains bonuses for our query with applied limiters
  79. if (cachedRequests.find(accessor, cachingStr) && accessor->second.first == cachedLast)
  80. return accessor->second.second;
  81. }
  82. //We still don't have the bonuses (didn't returned them from cache)
  83. //Perform bonus selection
  84. auto ret = std::make_shared<BonusList>();
  85. if (cachedLast == nodeChanged)
  86. {
  87. // Cached bonuses are up-to-date - use shared/read access and compute results
  88. std::shared_lock lock(sync);
  89. cachedBonuses.getBonuses(*ret, selector);
  90. }
  91. else
  92. {
  93. // If the bonus system tree changes(state of a single node or the relations to each other) then
  94. // cache all bonus objects. Selector objects doesn't matter.
  95. std::lock_guard lock(sync);
  96. if (cachedLast == nodeChanged)
  97. {
  98. // While our thread was waiting, another one have updated bonus tree. Use cached bonuses.
  99. cachedBonuses.getBonuses(*ret, selector);
  100. }
  101. else
  102. {
  103. // Cached bonuses may be outdated - regenerate them
  104. BonusList allBonuses;
  105. cachedBonuses.clear();
  106. getAllBonusesRec(allBonuses);
  107. limitBonuses(allBonuses, cachedBonuses);
  108. cachedBonuses.stackBonuses();
  109. cachedLast = nodeChanged;
  110. cachedBonuses.getBonuses(*ret, selector);
  111. }
  112. }
  113. // Save the results in the cache
  114. if (!cachingStr.empty())
  115. {
  116. RequestsMap::accessor accessor;
  117. if (cachedRequests.find(accessor, cachingStr))
  118. {
  119. accessor->second.second = ret;
  120. accessor->second.first = cachedLast;
  121. }
  122. else
  123. cachedRequests.emplace(cachingStr, std::pair<int32_t, TBonusListPtr>{ cachedLast, ret });
  124. }
  125. return ret;
  126. }
  127. else
  128. {
  129. return getAllBonusesWithoutCaching(selector);
  130. }
  131. }
  132. TConstBonusListPtr CBonusSystemNode::getAllBonusesWithoutCaching(const CSelector &selector) const
  133. {
  134. auto ret = std::make_shared<BonusList>();
  135. // Get bonus results without caching enabled.
  136. BonusList beforeLimiting;
  137. BonusList afterLimiting;
  138. getAllBonusesRec(beforeLimiting);
  139. limitBonuses(beforeLimiting, afterLimiting);
  140. afterLimiting.getBonuses(*ret, selector);
  141. ret->stackBonuses();
  142. return ret;
  143. }
  144. std::shared_ptr<Bonus> CBonusSystemNode::getUpdatedBonus(const std::shared_ptr<Bonus> & b, const TUpdaterPtr & updater) const
  145. {
  146. assert(updater);
  147. return updater->createUpdatedBonus(b, * this);
  148. }
  149. CBonusSystemNode::CBonusSystemNode(BonusNodeType NodeType, bool isHypotetic):
  150. nodeType(NodeType),
  151. cachedLast(0),
  152. nodeChanged(0),
  153. isHypotheticNode(isHypotetic)
  154. {
  155. }
  156. CBonusSystemNode::CBonusSystemNode(BonusNodeType NodeType):
  157. CBonusSystemNode(NodeType, false)
  158. {}
  159. CBonusSystemNode::~CBonusSystemNode()
  160. {
  161. detachFromAll();
  162. if(!children.empty())
  163. {
  164. while(!children.empty())
  165. children.front()->detachFrom(*this);
  166. }
  167. }
  168. void CBonusSystemNode::attachTo(CBonusSystemNode & parent)
  169. {
  170. assert(!vstd::contains(parentsToPropagate, &parent));
  171. parentsToPropagate.push_back(&parent);
  172. attachToSource(parent);
  173. if(!isHypothetic())
  174. {
  175. if(!parent.actsAsBonusSourceOnly())
  176. newRedDescendant(parent);
  177. assert(!vstd::contains(parent.children, this));
  178. parent.children.push_back(this);
  179. }
  180. parent.nodeHasChanged();
  181. }
  182. void CBonusSystemNode::attachToSource(const CBonusSystemNode & parent)
  183. {
  184. assert(!vstd::contains(parentsToInherit, &parent));
  185. parentsToInherit.push_back(&parent);
  186. if(!isHypothetic())
  187. {
  188. if(parent.actsAsBonusSourceOnly())
  189. parent.newRedDescendant(*this);
  190. }
  191. nodeHasChanged();
  192. }
  193. void CBonusSystemNode::detachFrom(CBonusSystemNode & parent)
  194. {
  195. assert(vstd::contains(parentsToPropagate, &parent));
  196. if(!isHypothetic())
  197. {
  198. if(!parent.actsAsBonusSourceOnly())
  199. removedRedDescendant(parent);
  200. }
  201. detachFromSource(parent);
  202. if (vstd::contains(parentsToPropagate, &parent))
  203. {
  204. parentsToPropagate -= &parent;
  205. }
  206. else
  207. {
  208. logBonus->error("Error on Detach. Node %s (nodeType=%d) has not parent %s (nodeType=%d)",
  209. nodeShortInfo(), static_cast<int>(nodeType), parent.nodeShortInfo(), static_cast<int>(parent.nodeType));
  210. }
  211. if(!isHypothetic())
  212. {
  213. if(vstd::contains(parent.children, this))
  214. parent.children -= this;
  215. else
  216. {
  217. logBonus->error("Error on Detach. Node %s (nodeType=%d) is not a child of %s (nodeType=%d)",
  218. nodeShortInfo(), static_cast<int>(nodeType), parent.nodeShortInfo(), static_cast<int>(parent.nodeType));
  219. }
  220. }
  221. parent.nodeHasChanged();
  222. }
  223. void CBonusSystemNode::detachFromSource(const CBonusSystemNode & parent)
  224. {
  225. assert(vstd::contains(parentsToInherit, &parent));
  226. if(!isHypothetic())
  227. {
  228. if(parent.actsAsBonusSourceOnly())
  229. parent.removedRedDescendant(*this);
  230. }
  231. if (vstd::contains(parentsToInherit, &parent))
  232. {
  233. parentsToInherit -= &parent;
  234. }
  235. else
  236. {
  237. logBonus->error("Error on Detach. Node %s (nodeType=%d) has not parent %s (nodeType=%d)",
  238. nodeShortInfo(), static_cast<int>(nodeType), parent.nodeShortInfo(), static_cast<int>(parent.nodeType));
  239. }
  240. nodeHasChanged();
  241. }
  242. void CBonusSystemNode::removeBonusesRecursive(const CSelector & s)
  243. {
  244. removeBonuses(s);
  245. for(CBonusSystemNode * child : children)
  246. child->removeBonusesRecursive(s);
  247. }
  248. void CBonusSystemNode::reduceBonusDurations(const CSelector &s)
  249. {
  250. BonusList bl;
  251. exportedBonuses.getBonuses(bl, s);
  252. for(const auto & b : bl)
  253. {
  254. b->turnsRemain--;
  255. if(b->turnsRemain <= 0)
  256. removeBonus(b);
  257. }
  258. for(CBonusSystemNode *child : children)
  259. child->reduceBonusDurations(s);
  260. }
  261. void CBonusSystemNode::addNewBonus(const std::shared_ptr<Bonus>& b)
  262. {
  263. //turnsRemain shouldn't be zero for following durations
  264. if(Bonus::NTurns(b.get()) || Bonus::NDays(b.get()) || Bonus::OneWeek(b.get()))
  265. {
  266. assert(b->turnsRemain);
  267. }
  268. assert(!vstd::contains(exportedBonuses, b));
  269. exportedBonuses.push_back(b);
  270. exportBonus(b);
  271. }
  272. void CBonusSystemNode::accumulateBonus(const std::shared_ptr<Bonus>& b)
  273. {
  274. auto bonus = exportedBonuses.getFirst(Selector::typeSubtypeValueType(b->type, b->subtype, b->valType)); //only local bonuses are interesting
  275. if(bonus)
  276. bonus->val += b->val;
  277. else
  278. addNewBonus(std::make_shared<Bonus>(*b)); //duplicate needed, original may get destroyed
  279. }
  280. void CBonusSystemNode::removeBonus(const std::shared_ptr<Bonus>& b)
  281. {
  282. exportedBonuses -= b;
  283. if(b->propagator)
  284. {
  285. unpropagateBonus(b);
  286. }
  287. else
  288. {
  289. bonuses -= b;
  290. nodeHasChanged();
  291. }
  292. }
  293. void CBonusSystemNode::removeBonuses(const CSelector & selector)
  294. {
  295. BonusList toRemove;
  296. exportedBonuses.getBonuses(toRemove, selector);
  297. for(const auto & bonus : toRemove)
  298. removeBonus(bonus);
  299. }
  300. bool CBonusSystemNode::actsAsBonusSourceOnly() const
  301. {
  302. switch(nodeType)
  303. {
  304. case BonusNodeType::CREATURE:
  305. case BonusNodeType::ARTIFACT:
  306. case BonusNodeType::ARTIFACT_INSTANCE:
  307. case BonusNodeType::BOAT:
  308. return true;
  309. default:
  310. return false;
  311. }
  312. }
  313. void CBonusSystemNode::propagateBonus(const std::shared_ptr<Bonus> & b, const CBonusSystemNode & source)
  314. {
  315. if(b->propagator->shouldBeAttached(this))
  316. {
  317. auto propagated = b->propagationUpdater
  318. ? source.getUpdatedBonus(b, b->propagationUpdater)
  319. : b;
  320. bonuses.push_back(propagated);
  321. logBonus->trace("#$# %s #propagated to# %s", propagated->Description(nullptr), nodeName());
  322. invalidateChildrenNodes(globalCounter);
  323. }
  324. TNodes lchildren;
  325. getRedChildren(lchildren);
  326. for(CBonusSystemNode *pname : lchildren)
  327. pname->propagateBonus(b, source);
  328. }
  329. void CBonusSystemNode::unpropagateBonus(const std::shared_ptr<Bonus> & b)
  330. {
  331. if(b->propagator->shouldBeAttached(this))
  332. {
  333. if (bonuses -= b)
  334. logBonus->trace("#$# %s #is no longer propagated to# %s", b->Description(nullptr), nodeName());
  335. else
  336. logBonus->warn("Attempt to remove #$# %s, which is not propagated to %s", b->Description(nullptr), nodeName());
  337. bonuses.remove_if([b](const auto & bonus)
  338. {
  339. if (bonus->propagationUpdater && bonus->propagationUpdater == b->propagationUpdater)
  340. {
  341. return true;
  342. }
  343. return false;
  344. });
  345. invalidateChildrenNodes(globalCounter);
  346. }
  347. TNodes lchildren;
  348. getRedChildren(lchildren);
  349. for(CBonusSystemNode *pname : lchildren)
  350. pname->unpropagateBonus(b);
  351. }
  352. void CBonusSystemNode::detachFromAll()
  353. {
  354. while(!parentsToPropagate.empty())
  355. detachFrom(*parentsToPropagate.front());
  356. while(!parentsToInherit.empty())
  357. detachFromSource(*parentsToInherit.front());
  358. }
  359. bool CBonusSystemNode::isIndependentNode() const
  360. {
  361. return parentsToInherit.empty() && parentsToPropagate.empty() && children.empty();
  362. }
  363. std::string CBonusSystemNode::nodeName() const
  364. {
  365. return std::string("Bonus system node of type ") + typeid(*this).name();
  366. }
  367. std::string CBonusSystemNode::nodeShortInfo() const
  368. {
  369. std::ostringstream str;
  370. str << "'" << typeid(* this).name() << "'";
  371. return str.str();
  372. }
  373. void CBonusSystemNode::getRedParents(TCNodes & out) const
  374. {
  375. TCNodes lparents;
  376. getParents(lparents);
  377. for(const CBonusSystemNode *pname : lparents)
  378. {
  379. if(pname->actsAsBonusSourceOnly())
  380. {
  381. out.insert(pname);
  382. }
  383. }
  384. if(!actsAsBonusSourceOnly())
  385. {
  386. for(const CBonusSystemNode *child : children)
  387. {
  388. out.insert(child);
  389. }
  390. }
  391. }
  392. void CBonusSystemNode::getRedChildren(TNodes &out)
  393. {
  394. for(CBonusSystemNode *pname : parentsToPropagate)
  395. {
  396. if(!pname->actsAsBonusSourceOnly())
  397. {
  398. out.insert(pname);
  399. }
  400. }
  401. if(actsAsBonusSourceOnly())
  402. {
  403. for(CBonusSystemNode *child : children)
  404. {
  405. out.insert(child);
  406. }
  407. }
  408. }
  409. void CBonusSystemNode::newRedDescendant(CBonusSystemNode & descendant) const
  410. {
  411. for(const auto & b : exportedBonuses)
  412. {
  413. if(b->propagator)
  414. descendant.propagateBonus(b, *this);
  415. }
  416. TCNodes redParents;
  417. getRedAncestors(redParents); //get all red parents recursively
  418. for(const auto * parent : redParents)
  419. {
  420. for(const auto & b : parent->exportedBonuses)
  421. {
  422. if(b->propagator)
  423. descendant.propagateBonus(b, *this);
  424. }
  425. }
  426. }
  427. void CBonusSystemNode::removedRedDescendant(CBonusSystemNode & descendant) const
  428. {
  429. for(const auto & b : exportedBonuses)
  430. if(b->propagator)
  431. descendant.unpropagateBonus(b);
  432. TCNodes redParents;
  433. getRedAncestors(redParents); //get all red parents recursively
  434. for(auto * parent : redParents)
  435. {
  436. for(const auto & b : parent->exportedBonuses)
  437. if(b->propagator)
  438. descendant.unpropagateBonus(b);
  439. }
  440. }
  441. void CBonusSystemNode::getRedAncestors(TCNodes &out) const
  442. {
  443. getRedParents(out);
  444. TCNodes redParents;
  445. getRedParents(redParents);
  446. for(const CBonusSystemNode * parent : redParents)
  447. parent->getRedAncestors(out);
  448. }
  449. void CBonusSystemNode::exportBonus(const std::shared_ptr<Bonus> & b)
  450. {
  451. if(b->propagator)
  452. {
  453. propagateBonus(b, *this);
  454. }
  455. else
  456. {
  457. bonuses.push_back(b);
  458. nodeHasChanged();
  459. }
  460. }
  461. void CBonusSystemNode::exportBonuses()
  462. {
  463. for(const auto & b : exportedBonuses)
  464. exportBonus(b);
  465. }
  466. BonusNodeType CBonusSystemNode::getNodeType() const
  467. {
  468. return nodeType;
  469. }
  470. const TCNodesVector& CBonusSystemNode::getParentNodes() const
  471. {
  472. return parentsToInherit;
  473. }
  474. BonusList & CBonusSystemNode::getExportedBonusList()
  475. {
  476. return exportedBonuses;
  477. }
  478. const BonusList & CBonusSystemNode::getExportedBonusList() const
  479. {
  480. return exportedBonuses;
  481. }
  482. void CBonusSystemNode::limitBonuses(const BonusList &allBonuses, BonusList &out) const
  483. {
  484. assert(&allBonuses != &out); //todo should it work in-place?
  485. BonusList undecided = allBonuses;
  486. BonusList & accepted = out;
  487. while(true)
  488. {
  489. int undecidedCount = static_cast<int>(undecided.size());
  490. for(int i = 0; i < undecided.size(); i++)
  491. {
  492. auto b = undecided[i];
  493. BonusLimitationContext context = {*b, *this, out, undecided};
  494. auto decision = b->limiter ? b->limiter->limit(context) : ILimiter::EDecision::ACCEPT; //bonuses without limiters will be accepted by default
  495. if(decision == ILimiter::EDecision::DISCARD || decision == ILimiter::EDecision::NOT_APPLICABLE)
  496. {
  497. undecided.erase(i);
  498. i--; continue;
  499. }
  500. else if(decision == ILimiter::EDecision::ACCEPT)
  501. {
  502. accepted.push_back(b);
  503. undecided.erase(i);
  504. i--; continue;
  505. }
  506. else
  507. assert(decision == ILimiter::EDecision::NOT_SURE);
  508. }
  509. if(undecided.size() == undecidedCount) //we haven't moved a single bonus -> limiters reached a stable state
  510. return;
  511. }
  512. }
  513. void CBonusSystemNode::nodeHasChanged()
  514. {
  515. invalidateChildrenNodes(++globalCounter);
  516. }
  517. void CBonusSystemNode::recomputePropagationUpdaters(const CBonusSystemNode & source)
  518. {
  519. for(const auto & b : exportedBonuses)
  520. {
  521. if (b->propagator && b->propagationUpdater)
  522. {
  523. unpropagateBonus(b);
  524. propagateBonus(b, source);
  525. }
  526. }
  527. for(const CBonusSystemNode * parent : source.parentsToInherit)
  528. if (parent->actsAsBonusSourceOnly())
  529. recomputePropagationUpdaters(*parent);
  530. }
  531. void CBonusSystemNode::invalidateChildrenNodes(int32_t changeCounter)
  532. {
  533. if (nodeChanged == changeCounter)
  534. return;
  535. nodeChanged = changeCounter;
  536. recomputePropagationUpdaters(*this);
  537. for(CBonusSystemNode * child : children)
  538. child->invalidateChildrenNodes(changeCounter);
  539. }
  540. int32_t CBonusSystemNode::getTreeVersion() const
  541. {
  542. return nodeChanged;
  543. }
  544. VCMI_LIB_NAMESPACE_END