AINodeStorage.cpp 37 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452
  1. /*
  2. * AINodeStorage.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 "AINodeStorage.h"
  12. #include "Actions/TownPortalAction.h"
  13. #include "../Goals/Goals.h"
  14. #include "../AIGateway.h"
  15. #include "../Engine/Nullkiller.h"
  16. #include "../../../CCallback.h"
  17. #include "../../../lib/mapping/CMap.h"
  18. #include "../../../lib/mapObjects/MapObjects.h"
  19. #include "../../../lib/PathfinderUtil.h"
  20. #include "../../../lib/CPlayerState.h"
  21. namespace NKAI
  22. {
  23. std::shared_ptr<boost::multi_array<AIPathNode, 5>> AISharedStorage::shared;
  24. boost::mutex AISharedStorage::locker;
  25. std::set<int3> commitedTiles;
  26. std::set<int3> commitedTilesInitial;
  27. const uint64_t FirstActorMask = 1;
  28. const uint64_t MIN_ARMY_STRENGTH_FOR_CHAIN = 5000;
  29. const uint64_t MIN_ARMY_STRENGTH_FOR_NEXT_ACTOR = 1000;
  30. const uint64_t CHAIN_MAX_DEPTH = 4;
  31. AISharedStorage::AISharedStorage(int3 sizes)
  32. {
  33. if(!shared){
  34. shared.reset(new boost::multi_array<AIPathNode, 5>(
  35. boost::extents[EPathfindingLayer::NUM_LAYERS][sizes.z][sizes.x][sizes.y][AIPathfinding::NUM_CHAINS]));
  36. }
  37. nodes = shared;
  38. }
  39. AISharedStorage::~AISharedStorage()
  40. {
  41. nodes.reset();
  42. if(shared && shared.use_count() == 1)
  43. {
  44. shared.reset();
  45. }
  46. }
  47. AINodeStorage::AINodeStorage(const Nullkiller * ai, const int3 & Sizes)
  48. : sizes(Sizes), ai(ai), cb(ai->cb.get()), nodes(Sizes)
  49. {
  50. dangerEvaluator.reset(new FuzzyHelper(ai));
  51. }
  52. AINodeStorage::~AINodeStorage() = default;
  53. void AINodeStorage::initialize(const PathfinderOptions & options, const CGameState * gs)
  54. {
  55. if(heroChainPass)
  56. return;
  57. //TODO: fix this code duplication with NodeStorage::initialize, problem is to keep `resetTile` inline
  58. const PlayerColor fowPlayer = ai->playerID;
  59. const auto fow = static_cast<const CGameInfoCallback *>(gs)->getPlayerTeam(fowPlayer)->fogOfWarMap;
  60. const int3 sizes = gs->getMapSize();
  61. //Each thread gets different x, but an array of y located next to each other in memory
  62. parallel_for(blocked_range<size_t>(0, sizes.x), [&](const blocked_range<size_t>& r)
  63. {
  64. int3 pos;
  65. for(pos.z = 0; pos.z < sizes.z; ++pos.z)
  66. {
  67. const bool useFlying = options.useFlying;
  68. const bool useWaterWalking = options.useWaterWalking;
  69. const PlayerColor player = playerID;
  70. for(pos.x = r.begin(); pos.x != r.end(); ++pos.x)
  71. {
  72. for(pos.y = 0; pos.y < sizes.y; ++pos.y)
  73. {
  74. const TerrainTile & tile = gs->map->getTile(pos);
  75. if (!tile.terType->isPassable())
  76. continue;
  77. if (tile.terType->isWater())
  78. {
  79. resetTile(pos, ELayer::SAIL, PathfinderUtil::evaluateAccessibility<ELayer::SAIL>(pos, tile, fow, player, gs));
  80. if (useFlying)
  81. resetTile(pos, ELayer::AIR, PathfinderUtil::evaluateAccessibility<ELayer::AIR>(pos, tile, fow, player, gs));
  82. if (useWaterWalking)
  83. resetTile(pos, ELayer::WATER, PathfinderUtil::evaluateAccessibility<ELayer::WATER>(pos, tile, fow, player, gs));
  84. }
  85. else
  86. {
  87. resetTile(pos, ELayer::LAND, PathfinderUtil::evaluateAccessibility<ELayer::LAND>(pos, tile, fow, player, gs));
  88. if (useFlying)
  89. resetTile(pos, ELayer::AIR, PathfinderUtil::evaluateAccessibility<ELayer::AIR>(pos, tile, fow, player, gs));
  90. }
  91. }
  92. }
  93. }
  94. });
  95. }
  96. void AINodeStorage::clear()
  97. {
  98. actors.clear();
  99. heroChainPass = EHeroChainPass::INITIAL;
  100. heroChainTurn = 0;
  101. heroChainMaxTurns = 1;
  102. turnDistanceLimit[HeroRole::MAIN] = 255;
  103. turnDistanceLimit[HeroRole::SCOUT] = 255;
  104. }
  105. boost::optional<AIPathNode *> AINodeStorage::getOrCreateNode(
  106. const int3 & pos,
  107. const EPathfindingLayer layer,
  108. const ChainActor * actor)
  109. {
  110. int bucketIndex = ((uintptr_t)actor) % AIPathfinding::BUCKET_COUNT;
  111. int bucketOffset = bucketIndex * AIPathfinding::BUCKET_SIZE;
  112. auto chains = nodes.get(pos, layer);
  113. if(chains[0].blocked())
  114. {
  115. return boost::none;
  116. }
  117. for(auto i = AIPathfinding::BUCKET_SIZE - 1; i >= 0; i--)
  118. {
  119. AIPathNode & node = chains[i + bucketOffset];
  120. if(node.actor == actor)
  121. {
  122. return &node;
  123. }
  124. if(!node.actor)
  125. {
  126. node.actor = actor;
  127. return &node;
  128. }
  129. }
  130. return boost::none;
  131. }
  132. std::vector<CGPathNode *> AINodeStorage::getInitialNodes()
  133. {
  134. if(heroChainPass)
  135. {
  136. if(heroChainTurn == 0)
  137. calculateTownPortalTeleportations(heroChain);
  138. return heroChain;
  139. }
  140. std::vector<CGPathNode *> initialNodes;
  141. for(auto actorPtr : actors)
  142. {
  143. ChainActor * actor = actorPtr.get();
  144. auto allocated = getOrCreateNode(actor->initialPosition, actor->layer, actor);
  145. if(!allocated)
  146. continue;
  147. AIPathNode * initialNode = allocated.get();
  148. initialNode->inPQ = false;
  149. initialNode->pq = nullptr;
  150. initialNode->turns = actor->initialTurn;
  151. initialNode->moveRemains = actor->initialMovement;
  152. initialNode->danger = 0;
  153. initialNode->setCost(actor->initialTurn);
  154. initialNode->action = CGPathNode::ENodeAction::NORMAL;
  155. if(actor->isMovable)
  156. {
  157. initialNodes.push_back(initialNode);
  158. }
  159. else
  160. {
  161. initialNode->locked = true;
  162. }
  163. }
  164. if(heroChainTurn == 0)
  165. calculateTownPortalTeleportations(initialNodes);
  166. return initialNodes;
  167. }
  168. void AINodeStorage::resetTile(const int3 & coord, EPathfindingLayer layer, CGPathNode::EAccessibility accessibility)
  169. {
  170. for(AIPathNode & heroNode : nodes.get(coord, layer))
  171. {
  172. heroNode.actor = nullptr;
  173. heroNode.danger = 0;
  174. heroNode.manaCost = 0;
  175. heroNode.specialAction.reset();
  176. heroNode.armyLoss = 0;
  177. heroNode.chainOther = nullptr;
  178. heroNode.update(coord, layer, accessibility);
  179. }
  180. }
  181. void AINodeStorage::commit(CDestinationNodeInfo & destination, const PathNodeInfo & source)
  182. {
  183. const AIPathNode * srcNode = getAINode(source.node);
  184. updateAINode(destination.node, [&](AIPathNode * dstNode)
  185. {
  186. commit(dstNode, srcNode, destination.action, destination.turn, destination.movementLeft, destination.cost);
  187. if(srcNode->specialAction || srcNode->chainOther)
  188. {
  189. // there is some action on source tile which should be performed before we can bypass it
  190. destination.node->theNodeBefore = source.node;
  191. }
  192. if(dstNode->specialAction && dstNode->actor)
  193. {
  194. dstNode->specialAction->applyOnDestination(dstNode->actor->hero, destination, source, dstNode, srcNode);
  195. }
  196. });
  197. }
  198. void AINodeStorage::commit(
  199. AIPathNode * destination,
  200. const AIPathNode * source,
  201. CGPathNode::ENodeAction action,
  202. int turn,
  203. int movementLeft,
  204. float cost) const
  205. {
  206. destination->action = action;
  207. destination->setCost(cost);
  208. destination->moveRemains = movementLeft;
  209. destination->turns = turn;
  210. destination->armyLoss = source->armyLoss;
  211. destination->manaCost = source->manaCost;
  212. destination->danger = source->danger;
  213. destination->theNodeBefore = source->theNodeBefore;
  214. destination->chainOther = nullptr;
  215. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  216. logAi->trace(
  217. "Commited %s -> %s, cost: %f, turn: %s, mp: %d, hero: %s, mask: %x, army: %lld",
  218. source->coord.toString(),
  219. destination->coord.toString(),
  220. destination->getCost(),
  221. std::to_string(destination->turns),
  222. destination->moveRemains,
  223. destination->actor->toString(),
  224. destination->actor->chainMask,
  225. destination->actor->armyValue);
  226. #endif
  227. if(destination->turns <= heroChainTurn)
  228. {
  229. commitedTiles.insert(destination->coord);
  230. }
  231. }
  232. std::vector<CGPathNode *> AINodeStorage::calculateNeighbours(
  233. const PathNodeInfo & source,
  234. const PathfinderConfig * pathfinderConfig,
  235. const CPathfinderHelper * pathfinderHelper)
  236. {
  237. std::vector<CGPathNode *> neighbours;
  238. neighbours.reserve(16);
  239. const AIPathNode * srcNode = getAINode(source.node);
  240. auto accessibleNeighbourTiles = pathfinderHelper->getNeighbourTiles(source);
  241. for(auto & neighbour : accessibleNeighbourTiles)
  242. {
  243. for(EPathfindingLayer i = EPathfindingLayer::LAND; i <= EPathfindingLayer::AIR; i.advance(1))
  244. {
  245. auto nextNode = getOrCreateNode(neighbour, i, srcNode->actor);
  246. if(!nextNode || nextNode.get()->accessible == CGPathNode::NOT_SET)
  247. continue;
  248. neighbours.push_back(nextNode.get());
  249. }
  250. }
  251. return neighbours;
  252. }
  253. EPathfindingLayer phisycalLayers[2] = {EPathfindingLayer::LAND, EPathfindingLayer::SAIL};
  254. bool AINodeStorage::increaseHeroChainTurnLimit()
  255. {
  256. if(heroChainTurn >= heroChainMaxTurns)
  257. return false;
  258. heroChainTurn++;
  259. commitedTiles.clear();
  260. for(auto layer : phisycalLayers)
  261. {
  262. foreach_tile_pos([&](const int3 & pos)
  263. {
  264. auto chains = nodes.get(pos, layer);
  265. if(!chains[0].blocked())
  266. {
  267. for(AIPathNode & node : chains)
  268. {
  269. if(node.turns <= heroChainTurn && node.action != CGPathNode::ENodeAction::UNKNOWN)
  270. {
  271. commitedTiles.insert(pos);
  272. break;
  273. }
  274. }
  275. }
  276. });
  277. }
  278. return true;
  279. }
  280. bool AINodeStorage::calculateHeroChainFinal()
  281. {
  282. heroChainPass = EHeroChainPass::FINAL;
  283. heroChain.resize(0);
  284. for(auto layer : phisycalLayers)
  285. {
  286. foreach_tile_pos([&](const int3 & pos)
  287. {
  288. auto chains = nodes.get(pos, layer);
  289. if(!chains[0].blocked())
  290. {
  291. for(AIPathNode & node : chains)
  292. {
  293. if(node.turns > heroChainTurn
  294. && !node.locked
  295. && node.action != CGPathNode::ENodeAction::UNKNOWN
  296. && node.actor->actorExchangeCount > 1
  297. && !hasBetterChain(&node, &node, chains))
  298. {
  299. heroChain.push_back(&node);
  300. }
  301. }
  302. }
  303. });
  304. }
  305. return heroChain.size();
  306. }
  307. struct DelayedWork
  308. {
  309. AIPathNode * carrier;
  310. AIPathNode * other;
  311. DelayedWork()
  312. {
  313. }
  314. DelayedWork(AIPathNode * carrier, AIPathNode * other) : carrier(carrier), other(other)
  315. {
  316. }
  317. };
  318. class HeroChainCalculationTask
  319. {
  320. private:
  321. AISharedStorage & nodes;
  322. AINodeStorage & storage;
  323. std::vector<AIPathNode *> existingChains;
  324. std::vector<ExchangeCandidate> newChains;
  325. uint64_t chainMask;
  326. int heroChainTurn;
  327. std::vector<CGPathNode *> heroChain;
  328. const std::vector<int3> & tiles;
  329. std::vector<DelayedWork> delayedWork;
  330. public:
  331. HeroChainCalculationTask(
  332. AINodeStorage & storage, AISharedStorage & nodes, const std::vector<int3> & tiles, uint64_t chainMask, int heroChainTurn)
  333. :existingChains(), newChains(), delayedWork(), nodes(nodes), storage(storage), chainMask(chainMask), heroChainTurn(heroChainTurn), heroChain(), tiles(tiles)
  334. {
  335. existingChains.reserve(AIPathfinding::NUM_CHAINS);
  336. newChains.reserve(AIPathfinding::NUM_CHAINS);
  337. }
  338. void execute(const blocked_range<size_t>& r)
  339. {
  340. std::random_device randomDevice;
  341. std::mt19937 randomEngine(randomDevice());
  342. for(int i = r.begin(); i != r.end(); i++)
  343. {
  344. auto & pos = tiles[i];
  345. for(auto layer : phisycalLayers)
  346. {
  347. auto chains = nodes.get(pos, layer);
  348. // fast cut inactive nodes
  349. if(chains[0].blocked())
  350. continue;
  351. existingChains.clear();
  352. newChains.clear();
  353. for(AIPathNode & node : chains)
  354. {
  355. if(node.turns <= heroChainTurn && node.action != CGPathNode::ENodeAction::UNKNOWN)
  356. existingChains.push_back(&node);
  357. }
  358. std::shuffle(existingChains.begin(), existingChains.end(), randomEngine);
  359. for(AIPathNode * node : existingChains)
  360. {
  361. if(node->actor->isMovable)
  362. {
  363. calculateHeroChain(node, existingChains, newChains);
  364. }
  365. }
  366. for(auto delayed = delayedWork.begin(); delayed != delayedWork.end();)
  367. {
  368. auto newActor = delayed->carrier->actor->tryExchangeNoLock(delayed->other->actor);
  369. if(!newActor.lockAcquired) continue;
  370. if(newActor.actor)
  371. {
  372. newChains.push_back(calculateExchange(newActor.actor, delayed->carrier, delayed->other));
  373. }
  374. delayed++;
  375. }
  376. delayedWork.clear();
  377. cleanupInefectiveChains(newChains);
  378. addHeroChain(newChains);
  379. }
  380. }
  381. }
  382. void calculateHeroChain(
  383. AIPathNode * srcNode,
  384. const std::vector<AIPathNode *> & variants,
  385. std::vector<ExchangeCandidate> & result);
  386. void calculateHeroChain(
  387. AIPathNode * carrier,
  388. AIPathNode * other,
  389. std::vector<ExchangeCandidate> & result);
  390. void cleanupInefectiveChains(std::vector<ExchangeCandidate> & result) const;
  391. void addHeroChain(const std::vector<ExchangeCandidate> & result);
  392. ExchangeCandidate calculateExchange(
  393. ChainActor * exchangeActor,
  394. AIPathNode * carrierParentNode,
  395. AIPathNode * otherParentNode) const;
  396. void flushResult(std::vector<CGPathNode *> & result)
  397. {
  398. vstd::concatenate(result, heroChain);
  399. }
  400. };
  401. bool AINodeStorage::calculateHeroChain()
  402. {
  403. std::random_device randomDevice;
  404. std::mt19937 randomEngine(randomDevice());
  405. heroChainPass = EHeroChainPass::CHAIN;
  406. heroChain.clear();
  407. std::vector<int3> data(commitedTiles.begin(), commitedTiles.end());
  408. if(data.size() > 100)
  409. {
  410. boost::mutex resultMutex;
  411. std::shuffle(data.begin(), data.end(), randomEngine);
  412. parallel_for(blocked_range<size_t>(0, data.size()), [&](const blocked_range<size_t>& r)
  413. {
  414. //auto r = blocked_range<size_t>(0, data.size());
  415. HeroChainCalculationTask task(*this, nodes, data, chainMask, heroChainTurn);
  416. task.execute(r);
  417. {
  418. boost::lock_guard<boost::mutex> resultLock(resultMutex);
  419. task.flushResult(heroChain);
  420. }
  421. });
  422. }
  423. else
  424. {
  425. auto r = blocked_range<size_t>(0, data.size());
  426. HeroChainCalculationTask task(*this, nodes, data, chainMask, heroChainTurn);
  427. task.execute(r);
  428. task.flushResult(heroChain);
  429. }
  430. commitedTiles.clear();
  431. return !heroChain.empty();
  432. }
  433. bool AINodeStorage::selectFirstActor()
  434. {
  435. if(actors.empty())
  436. return false;
  437. auto strongest = *vstd::maxElementByFun(actors, [](std::shared_ptr<ChainActor> actor) -> uint64_t
  438. {
  439. return actor->armyValue;
  440. });
  441. chainMask = strongest->chainMask;
  442. commitedTilesInitial = commitedTiles;
  443. return true;
  444. }
  445. bool AINodeStorage::selectNextActor()
  446. {
  447. auto currentActor = std::find_if(actors.begin(), actors.end(), [&](std::shared_ptr<ChainActor> actor)-> bool
  448. {
  449. return actor->chainMask == chainMask;
  450. });
  451. auto nextActor = actors.end();
  452. for(auto actor = actors.begin(); actor != actors.end(); actor++)
  453. {
  454. if(actor->get()->armyValue > currentActor->get()->armyValue
  455. || (actor->get()->armyValue == currentActor->get()->armyValue && actor <= currentActor))
  456. {
  457. continue;
  458. }
  459. if(nextActor == actors.end()
  460. || actor->get()->armyValue > nextActor->get()->armyValue)
  461. {
  462. nextActor = actor;
  463. }
  464. }
  465. if(nextActor != actors.end())
  466. {
  467. if(nextActor->get()->armyValue < MIN_ARMY_STRENGTH_FOR_NEXT_ACTOR)
  468. return false;
  469. chainMask = nextActor->get()->chainMask;
  470. commitedTiles = commitedTilesInitial;
  471. return true;
  472. }
  473. return false;
  474. }
  475. void HeroChainCalculationTask::cleanupInefectiveChains(std::vector<ExchangeCandidate> & result) const
  476. {
  477. vstd::erase_if(result, [&](const ExchangeCandidate & chainInfo) -> bool
  478. {
  479. auto pos = chainInfo.coord;
  480. auto chains = nodes.get(pos, EPathfindingLayer::LAND);
  481. auto isNotEffective = storage.hasBetterChain(chainInfo.carrierParent, &chainInfo, chains)
  482. || storage.hasBetterChain(chainInfo.carrierParent, &chainInfo, result);
  483. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  484. if(isNotEffective)
  485. {
  486. logAi->trace(
  487. "Skip exchange %s[%x] -> %s[%x] at %s is ineficient",
  488. chainInfo.otherParent->actor->toString(),
  489. chainInfo.otherParent->actor->chainMask,
  490. chainInfo.carrierParent->actor->toString(),
  491. chainInfo.carrierParent->actor->chainMask,
  492. chainInfo.carrierParent->coord.toString());
  493. }
  494. #endif
  495. return isNotEffective;
  496. });
  497. }
  498. void HeroChainCalculationTask::calculateHeroChain(
  499. AIPathNode * srcNode,
  500. const std::vector<AIPathNode *> & variants,
  501. std::vector<ExchangeCandidate> & result)
  502. {
  503. for(AIPathNode * node : variants)
  504. {
  505. if(node == srcNode || !node->actor)
  506. continue;
  507. if((node->actor->chainMask & chainMask) == 0 && (srcNode->actor->chainMask & chainMask) == 0)
  508. continue;
  509. if(node->actor->actorExchangeCount + srcNode->actor->actorExchangeCount > CHAIN_MAX_DEPTH)
  510. continue;
  511. if(node->action == CGPathNode::ENodeAction::BATTLE
  512. || node->action == CGPathNode::ENodeAction::TELEPORT_BATTLE
  513. || node->action == CGPathNode::ENodeAction::TELEPORT_NORMAL
  514. || node->action == CGPathNode::ENodeAction::TELEPORT_BLOCKING_VISIT)
  515. {
  516. continue;
  517. }
  518. if(node->turns > heroChainTurn
  519. || (node->action == CGPathNode::ENodeAction::UNKNOWN && node->actor->hero)
  520. || (node->actor->chainMask & srcNode->actor->chainMask) != 0)
  521. {
  522. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  523. logAi->trace(
  524. "Skip exchange %s[%x] -> %s[%x] at %s because of %s",
  525. node->actor->toString(),
  526. node->actor->chainMask,
  527. srcNode->actor->toString(),
  528. srcNode->actor->chainMask,
  529. srcNode->coord.toString(),
  530. (node->turns > heroChainTurn
  531. ? "turn limit"
  532. : (node->action == CGPathNode::ENodeAction::UNKNOWN && node->actor->hero)
  533. ? "action unknown"
  534. : "chain mask"));
  535. #endif
  536. continue;
  537. }
  538. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  539. logAi->trace(
  540. "Thy exchange %s[%x] -> %s[%x] at %s",
  541. node->actor->toString(),
  542. node->actor->chainMask,
  543. srcNode->actor->toString(),
  544. srcNode->actor->chainMask,
  545. srcNode->coord.toString());
  546. #endif
  547. calculateHeroChain(srcNode, node, result);
  548. }
  549. }
  550. void HeroChainCalculationTask::calculateHeroChain(
  551. AIPathNode * carrier,
  552. AIPathNode * other,
  553. std::vector<ExchangeCandidate> & result)
  554. {
  555. if(carrier->armyLoss < carrier->actor->armyValue
  556. && (carrier->action != CGPathNode::BATTLE || (carrier->actor->allowBattle && carrier->specialAction))
  557. && carrier->action != CGPathNode::BLOCKING_VISIT
  558. && (other->armyLoss == 0 || other->armyLoss < other->actor->armyValue))
  559. {
  560. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  561. logAi->trace(
  562. "Exchange allowed %s[%x] -> %s[%x] at %s",
  563. other->actor->toString(),
  564. other->actor->chainMask,
  565. carrier->actor->toString(),
  566. carrier->actor->chainMask,
  567. carrier->coord.toString());
  568. #endif
  569. if(other->actor->isMovable)
  570. {
  571. bool hasLessMp = carrier->turns > other->turns || (carrier->turns == other->turns && carrier->moveRemains < other->moveRemains);
  572. bool hasLessExperience = carrier->actor->hero->exp < other->actor->hero->exp;
  573. if(hasLessMp && hasLessExperience)
  574. {
  575. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  576. logAi->trace("Exchange at %s is ineficient. Blocked.", carrier->coord.toString());
  577. #endif
  578. return;
  579. }
  580. }
  581. auto newActor = carrier->actor->tryExchangeNoLock(other->actor);
  582. if(!newActor.lockAcquired) delayedWork.push_back(DelayedWork(carrier, other));
  583. if(newActor.actor) result.push_back(calculateExchange(newActor.actor, carrier, other));
  584. }
  585. }
  586. void HeroChainCalculationTask::addHeroChain(const std::vector<ExchangeCandidate> & result)
  587. {
  588. for(const ExchangeCandidate & chainInfo : result)
  589. {
  590. auto carrier = chainInfo.carrierParent;
  591. auto newActor = chainInfo.actor;
  592. auto other = chainInfo.otherParent;
  593. auto chainNodeOptional = storage.getOrCreateNode(carrier->coord, carrier->layer, newActor);
  594. if(!chainNodeOptional)
  595. {
  596. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  597. logAi->trace("Exchange at %s can not allocate node. Blocked.", carrier->coord.toString());
  598. #endif
  599. continue;
  600. }
  601. auto exchangeNode = chainNodeOptional.get();
  602. if(exchangeNode->action != CGPathNode::ENodeAction::UNKNOWN)
  603. {
  604. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  605. logAi->trace(
  606. "Skip exchange %s[%x] -> %s[%x] at %s because node is in use",
  607. other->actor->toString(),
  608. other->actor->chainMask,
  609. carrier->actor->toString(),
  610. carrier->actor->chainMask,
  611. carrier->coord.toString());
  612. #endif
  613. continue;
  614. }
  615. if(exchangeNode->turns != 0xFF && exchangeNode->getCost() < chainInfo.getCost())
  616. {
  617. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  618. logAi->trace(
  619. "Skip exchange %s[%x] -> %s[%x] at %s because not effective enough. %f < %f",
  620. other->actor->toString(),
  621. other->actor->chainMask,
  622. carrier->actor->toString(),
  623. carrier->actor->chainMask,
  624. carrier->coord.toString(),
  625. exchangeNode->getCost(),
  626. chainInfo.getCost());
  627. #endif
  628. continue;
  629. }
  630. storage.commit(exchangeNode, carrier, carrier->action, chainInfo.turns, chainInfo.moveRemains, chainInfo.getCost());
  631. if(carrier->specialAction || carrier->chainOther)
  632. {
  633. // there is some action on source tile which should be performed before we can bypass it
  634. exchangeNode->theNodeBefore = carrier;
  635. }
  636. if(exchangeNode->actor->actorAction)
  637. {
  638. exchangeNode->theNodeBefore = carrier;
  639. exchangeNode->specialAction = exchangeNode->actor->actorAction;
  640. }
  641. exchangeNode->chainOther = other;
  642. exchangeNode->armyLoss = chainInfo.armyLoss;
  643. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  644. logAi->trace(
  645. "Chain accepted at %s %s -> %s, mask %x, cost %f, turn: %s, mp: %d, army %i",
  646. exchangeNode->coord.toString(),
  647. other->actor->toString(),
  648. exchangeNode->actor->toString(),
  649. exchangeNode->actor->chainMask,
  650. exchangeNode->getCost(),
  651. std::to_string(exchangeNode->turns),
  652. exchangeNode->moveRemains,
  653. exchangeNode->actor->armyValue);
  654. #endif
  655. heroChain.push_back(exchangeNode);
  656. }
  657. }
  658. ExchangeCandidate HeroChainCalculationTask::calculateExchange(
  659. ChainActor * exchangeActor,
  660. AIPathNode * carrierParentNode,
  661. AIPathNode * otherParentNode) const
  662. {
  663. ExchangeCandidate candidate;
  664. candidate.layer = carrierParentNode->layer;
  665. candidate.coord = carrierParentNode->coord;
  666. candidate.carrierParent = carrierParentNode;
  667. candidate.otherParent = otherParentNode;
  668. candidate.actor = exchangeActor;
  669. candidate.armyLoss = carrierParentNode->armyLoss + otherParentNode->armyLoss;
  670. candidate.turns = carrierParentNode->turns;
  671. candidate.setCost(carrierParentNode->getCost() + otherParentNode->getCost() / 1000.0);
  672. candidate.moveRemains = carrierParentNode->moveRemains;
  673. if(carrierParentNode->turns < otherParentNode->turns)
  674. {
  675. int moveRemains = exchangeActor->maxMovePoints(carrierParentNode->layer);
  676. float waitingCost = otherParentNode->turns - carrierParentNode->turns - 1
  677. + carrierParentNode->moveRemains / (float)moveRemains;
  678. candidate.turns = otherParentNode->turns;
  679. candidate.setCost(candidate.getCost() + waitingCost);
  680. candidate.moveRemains = moveRemains;
  681. }
  682. return candidate;
  683. }
  684. const std::set<const CGHeroInstance *> AINodeStorage::getAllHeroes() const
  685. {
  686. std::set<const CGHeroInstance *> heroes;
  687. for(auto actor : actors)
  688. {
  689. if(actor->hero)
  690. heroes.insert(actor->hero);
  691. }
  692. return heroes;
  693. }
  694. bool AINodeStorage::isDistanceLimitReached(const PathNodeInfo & source, CDestinationNodeInfo & destination) const
  695. {
  696. if(heroChainPass == EHeroChainPass::CHAIN && destination.node->turns > heroChainTurn)
  697. {
  698. return true;
  699. }
  700. auto aiNode = getAINode(destination.node);
  701. if(heroChainPass != EHeroChainPass::CHAIN
  702. && destination.node->turns > turnDistanceLimit[aiNode->actor->heroRole])
  703. {
  704. return true;
  705. }
  706. return false;
  707. }
  708. void AINodeStorage::setHeroes(std::map<const CGHeroInstance *, HeroRole> heroes)
  709. {
  710. playerID = ai->playerID;
  711. for(auto & hero : heroes)
  712. {
  713. // do not allow our own heroes in garrison to act on map
  714. if(hero.first->getOwner() == ai->playerID && hero.first->inTownGarrison)
  715. continue;
  716. uint64_t mask = FirstActorMask << actors.size();
  717. auto actor = std::make_shared<HeroActor>(hero.first, hero.second, mask, ai);
  718. if(actor->hero->tempOwner != ai->playerID)
  719. {
  720. bool onLand = !actor->hero->boat;
  721. actor->initialMovement = actor->hero->maxMovePoints(onLand);
  722. }
  723. playerID = actor->hero->tempOwner;
  724. actors.push_back(actor);
  725. }
  726. }
  727. void AINodeStorage::setTownsAndDwellings(
  728. const std::vector<const CGTownInstance *> & towns,
  729. const std::set<const CGObjectInstance *> & visitableObjs)
  730. {
  731. for(auto town : towns)
  732. {
  733. uint64_t mask = FirstActorMask << actors.size();
  734. // TODO: investigate logix of second condition || ai->nullkiller->getHeroLockedReason(town->garrisonHero) != HeroLockedReason::DEFENCE
  735. // check defence imrove
  736. if(!town->garrisonHero)
  737. {
  738. actors.push_back(std::make_shared<TownGarrisonActor>(town, mask));
  739. }
  740. }
  741. /*auto dayOfWeek = cb->getDate(Date::DAY_OF_WEEK);
  742. auto waitForGrowth = dayOfWeek > 4;*/
  743. for(auto obj: visitableObjs)
  744. {
  745. if(obj->ID == Obj::HILL_FORT)
  746. {
  747. uint64_t mask = FirstActorMask << actors.size();
  748. actors.push_back(std::make_shared<HillFortActor>(obj, mask));
  749. }
  750. /*const CGDwelling * dwelling = dynamic_cast<const CGDwelling *>(obj);
  751. if(dwelling)
  752. {
  753. uint64_t mask = 1 << actors.size();
  754. auto dwellingActor = std::make_shared<DwellingActor>(dwelling, mask, false, dayOfWeek);
  755. if(dwellingActor->creatureSet->getArmyStrength())
  756. {
  757. actors.push_back(dwellingActor);
  758. }
  759. if(waitForGrowth)
  760. {
  761. mask = 1 << actors.size();
  762. dwellingActor = std::make_shared<DwellingActor>(dwelling, mask, waitForGrowth, dayOfWeek);
  763. if(dwellingActor->creatureSet->getArmyStrength())
  764. {
  765. actors.push_back(dwellingActor);
  766. }
  767. }
  768. }*/
  769. }
  770. }
  771. std::vector<CGPathNode *> AINodeStorage::calculateTeleportations(
  772. const PathNodeInfo & source,
  773. const PathfinderConfig * pathfinderConfig,
  774. const CPathfinderHelper * pathfinderHelper)
  775. {
  776. std::vector<CGPathNode *> neighbours;
  777. if(source.isNodeObjectVisitable())
  778. {
  779. auto accessibleExits = pathfinderHelper->getTeleportExits(source);
  780. auto srcNode = getAINode(source.node);
  781. for(auto & neighbour : accessibleExits)
  782. {
  783. auto node = getOrCreateNode(neighbour, source.node->layer, srcNode->actor);
  784. if(!node)
  785. continue;
  786. neighbours.push_back(node.get());
  787. }
  788. }
  789. return neighbours;
  790. }
  791. struct TowmPortalFinder
  792. {
  793. const std::vector<CGPathNode *> & initialNodes;
  794. SecSkillLevel::SecSkillLevel townPortalSkillLevel;
  795. uint64_t movementNeeded;
  796. const ChainActor * actor;
  797. const CGHeroInstance * hero;
  798. std::vector<const CGTownInstance *> targetTowns;
  799. AINodeStorage * nodeStorage;
  800. SpellID spellID;
  801. const CSpell * townPortal;
  802. TowmPortalFinder(
  803. const ChainActor * actor,
  804. const std::vector<CGPathNode *> & initialNodes,
  805. std::vector<const CGTownInstance *> targetTowns,
  806. AINodeStorage * nodeStorage)
  807. :actor(actor), initialNodes(initialNodes), hero(actor->hero),
  808. targetTowns(targetTowns), nodeStorage(nodeStorage)
  809. {
  810. spellID = SpellID::TOWN_PORTAL;
  811. townPortal = spellID.toSpell();
  812. // TODO: Copy/Paste from TownPortalMechanics
  813. townPortalSkillLevel = SecSkillLevel::SecSkillLevel(hero->getSpellSchoolLevel(townPortal));
  814. movementNeeded = GameConstants::BASE_MOVEMENT_COST * (townPortalSkillLevel >= SecSkillLevel::EXPERT ? 2 : 3);
  815. }
  816. bool actorCanCastTownPortal()
  817. {
  818. return hero->canCastThisSpell(townPortal) && hero->mana >= hero->getSpellCost(townPortal);
  819. }
  820. CGPathNode * getBestInitialNodeForTownPortal(const CGTownInstance * targetTown)
  821. {
  822. for(CGPathNode * node : initialNodes)
  823. {
  824. auto aiNode = nodeStorage->getAINode(node);
  825. if(aiNode->actor->baseActor != actor
  826. || node->layer != EPathfindingLayer::LAND
  827. || node->moveRemains < movementNeeded)
  828. {
  829. continue;
  830. }
  831. if(townPortalSkillLevel < SecSkillLevel::ADVANCED)
  832. {
  833. const CGTownInstance * nearestTown = *vstd::minElementByFun(targetTowns, [&](const CGTownInstance * t) -> int
  834. {
  835. return node->coord.dist2dSQ(t->visitablePos());
  836. });
  837. if(targetTown != nearestTown)
  838. continue;
  839. }
  840. return node;
  841. }
  842. return nullptr;
  843. }
  844. boost::optional<AIPathNode *> createTownPortalNode(const CGTownInstance * targetTown)
  845. {
  846. auto bestNode = getBestInitialNodeForTownPortal(targetTown);
  847. if(!bestNode)
  848. return boost::none;
  849. auto nodeOptional = nodeStorage->getOrCreateNode(targetTown->visitablePos(), EPathfindingLayer::LAND, actor->castActor);
  850. if(!nodeOptional)
  851. return boost::none;
  852. AIPathNode * node = nodeOptional.get();
  853. float movementCost = (float)movementNeeded / (float)hero->maxMovePoints(EPathfindingLayer::LAND);
  854. movementCost += bestNode->getCost();
  855. if(node->action == CGPathNode::UNKNOWN || node->getCost() > movementCost)
  856. {
  857. nodeStorage->commit(
  858. node,
  859. nodeStorage->getAINode(bestNode),
  860. CGPathNode::TELEPORT_NORMAL,
  861. bestNode->turns,
  862. bestNode->moveRemains - movementNeeded,
  863. movementCost);
  864. node->theNodeBefore = bestNode;
  865. node->specialAction.reset(new AIPathfinding::TownPortalAction(targetTown));
  866. }
  867. return nodeOptional;
  868. }
  869. };
  870. template<class TVector>
  871. void AINodeStorage::calculateTownPortal(
  872. const ChainActor * actor,
  873. const std::map<const CGHeroInstance *, int> & maskMap,
  874. const std::vector<CGPathNode *> & initialNodes,
  875. TVector & output)
  876. {
  877. auto towns = cb->getTownsInfo(false);
  878. vstd::erase_if(towns, [&](const CGTownInstance * t) -> bool
  879. {
  880. return cb->getPlayerRelations(actor->hero->tempOwner, t->tempOwner) == PlayerRelations::ENEMIES;
  881. });
  882. if(!towns.size())
  883. {
  884. return; // no towns no need to run loop further
  885. }
  886. TowmPortalFinder townPortalFinder(actor, initialNodes, towns, this);
  887. if(townPortalFinder.actorCanCastTownPortal())
  888. {
  889. for(const CGTownInstance * targetTown : towns)
  890. {
  891. // TODO: allow to hide visiting hero in garrison
  892. if(targetTown->visitingHero && maskMap.find(targetTown->visitingHero.get()) != maskMap.end())
  893. {
  894. auto basicMask = maskMap.at(targetTown->visitingHero.get());
  895. bool heroIsInChain = (actor->chainMask & basicMask) != 0;
  896. bool sameActorInTown = actor->chainMask == basicMask;
  897. if(sameActorInTown || !heroIsInChain)
  898. continue;
  899. }
  900. auto nodeOptional = townPortalFinder.createTownPortalNode(targetTown);
  901. if(nodeOptional)
  902. {
  903. #if NKAI_PATHFINDER_TRACE_LEVEL >= 1
  904. logAi->trace("Adding town portal node at %s", targetTown->name);
  905. #endif
  906. output.push_back(nodeOptional.get());
  907. }
  908. }
  909. }
  910. }
  911. void AINodeStorage::calculateTownPortalTeleportations(std::vector<CGPathNode *> & initialNodes)
  912. {
  913. std::set<const ChainActor *> actorsOfInitial;
  914. for(const CGPathNode * node : initialNodes)
  915. {
  916. auto aiNode = getAINode(node);
  917. if(aiNode->actor->hero)
  918. actorsOfInitial.insert(aiNode->actor->baseActor);
  919. }
  920. std::map<const CGHeroInstance *, int> maskMap;
  921. for(std::shared_ptr<ChainActor> basicActor : actors)
  922. {
  923. if(basicActor->hero)
  924. maskMap[basicActor->hero] = basicActor->chainMask;
  925. }
  926. boost::sort(initialNodes, NodeComparer<CGPathNode>());
  927. std::vector<const ChainActor *> actorsVector(actorsOfInitial.begin(), actorsOfInitial.end());
  928. tbb::concurrent_vector<CGPathNode *> output;
  929. if(actorsVector.size() * initialNodes.size() > 1000)
  930. {
  931. parallel_for(blocked_range<size_t>(0, actorsVector.size()), [&](const blocked_range<size_t> & r)
  932. {
  933. for(int i = r.begin(); i != r.end(); i++)
  934. {
  935. calculateTownPortal(actorsVector[i], maskMap, initialNodes, output);
  936. }
  937. });
  938. std::copy(output.begin(), output.end(), std::back_inserter(initialNodes));
  939. }
  940. else
  941. {
  942. for(auto actor : actorsVector)
  943. {
  944. calculateTownPortal(actor, maskMap, initialNodes, initialNodes);
  945. }
  946. }
  947. }
  948. bool AINodeStorage::hasBetterChain(const PathNodeInfo & source, CDestinationNodeInfo & destination) const
  949. {
  950. auto pos = destination.coord;
  951. auto chains = nodes.get(pos, EPathfindingLayer::LAND);
  952. return hasBetterChain(source.node, getAINode(destination.node), chains);
  953. }
  954. template<class NodeRange>
  955. bool AINodeStorage::hasBetterChain(
  956. const CGPathNode * source,
  957. const AIPathNode * candidateNode,
  958. const NodeRange & chains) const
  959. {
  960. auto candidateActor = candidateNode->actor;
  961. for(const AIPathNode & node : chains)
  962. {
  963. auto sameNode = node.actor == candidateNode->actor;
  964. if(sameNode || node.action == CGPathNode::ENodeAction::UNKNOWN || !node.actor || !node.actor->hero)
  965. {
  966. continue;
  967. }
  968. if(node.danger <= candidateNode->danger && candidateNode->actor == node.actor->battleActor)
  969. {
  970. if(node.getCost() < candidateNode->getCost())
  971. {
  972. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  973. logAi->trace(
  974. "Block ineficient battle move %s->%s, hero: %s[%X], army %lld, mp diff: %i",
  975. source->coord.toString(),
  976. candidateNode->coord.toString(),
  977. candidateNode->actor->hero->name,
  978. candidateNode->actor->chainMask,
  979. candidateNode->actor->armyValue,
  980. node.moveRemains - candidateNode->moveRemains);
  981. #endif
  982. return true;
  983. }
  984. }
  985. if(candidateActor->chainMask != node.actor->chainMask && heroChainPass != EHeroChainPass::FINAL)
  986. continue;
  987. auto nodeActor = node.actor;
  988. auto nodeArmyValue = nodeActor->armyValue - node.armyLoss;
  989. auto candidateArmyValue = candidateActor->armyValue - candidateNode->armyLoss;
  990. if(nodeArmyValue > candidateArmyValue
  991. && node.getCost() <= candidateNode->getCost())
  992. {
  993. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  994. logAi->trace(
  995. "Block ineficient move because of stronger army %s->%s, hero: %s[%X], army %lld, mp diff: %i",
  996. source->coord.toString(),
  997. candidateNode->coord.toString(),
  998. candidateNode->actor->hero->name,
  999. candidateNode->actor->chainMask,
  1000. candidateNode->actor->armyValue,
  1001. node.moveRemains - candidateNode->moveRemains);
  1002. #endif
  1003. return true;
  1004. }
  1005. if(heroChainPass == EHeroChainPass::FINAL)
  1006. {
  1007. if(nodeArmyValue == candidateArmyValue
  1008. && nodeActor->heroFightingStrength >= candidateActor->heroFightingStrength
  1009. && node.getCost() <= candidateNode->getCost())
  1010. {
  1011. if(nodeActor->heroFightingStrength == candidateActor->heroFightingStrength
  1012. && node.getCost() == candidateNode->getCost()
  1013. && &node < candidateNode)
  1014. {
  1015. continue;
  1016. }
  1017. #if NKAI_PATHFINDER_TRACE_LEVEL >= 2
  1018. logAi->trace(
  1019. "Block ineficient move because of stronger hero %s->%s, hero: %s[%X], army %lld, mp diff: %i",
  1020. source->coord.toString(),
  1021. candidateNode->coord.toString(),
  1022. candidateNode->actor->hero->name,
  1023. candidateNode->actor->chainMask,
  1024. candidateNode->actor->armyValue,
  1025. node.moveRemains - candidateNode->moveRemains);
  1026. #endif
  1027. return true;
  1028. }
  1029. }
  1030. }
  1031. return false;
  1032. }
  1033. bool AINodeStorage::isTileAccessible(const HeroPtr & hero, const int3 & pos, const EPathfindingLayer layer) const
  1034. {
  1035. auto chains = nodes.get(pos, layer);
  1036. for(const AIPathNode & node : chains)
  1037. {
  1038. if(node.action != CGPathNode::ENodeAction::UNKNOWN
  1039. && node.actor && node.actor->hero == hero.h)
  1040. {
  1041. return true;
  1042. }
  1043. }
  1044. return false;
  1045. }
  1046. std::vector<AIPath> AINodeStorage::getChainInfo(const int3 & pos, bool isOnLand) const
  1047. {
  1048. std::vector<AIPath> paths;
  1049. paths.reserve(AIPathfinding::NUM_CHAINS / 4);
  1050. auto chains = nodes.get(pos, isOnLand ? EPathfindingLayer::LAND : EPathfindingLayer::SAIL);
  1051. for(const AIPathNode & node : chains)
  1052. {
  1053. if(node.action == CGPathNode::ENodeAction::UNKNOWN || !node.actor || !node.actor->hero)
  1054. {
  1055. continue;
  1056. }
  1057. AIPath path;
  1058. path.targetHero = node.actor->hero;
  1059. path.heroArmy = node.actor->creatureSet;
  1060. path.armyLoss = node.armyLoss;
  1061. path.targetObjectDanger = evaluateDanger(pos, path.targetHero, !node.actor->allowBattle);
  1062. path.targetObjectArmyLoss = evaluateArmyLoss(path.targetHero, path.heroArmy->getArmyStrength(), path.targetObjectDanger);
  1063. path.chainMask = node.actor->chainMask;
  1064. path.exchangeCount = node.actor->actorExchangeCount;
  1065. fillChainInfo(&node, path, -1);
  1066. paths.push_back(path);
  1067. }
  1068. return paths;
  1069. }
  1070. void AINodeStorage::fillChainInfo(const AIPathNode * node, AIPath & path, int parentIndex) const
  1071. {
  1072. while(node != nullptr)
  1073. {
  1074. if(!node->actor->hero)
  1075. return;
  1076. if(node->chainOther)
  1077. fillChainInfo(node->chainOther, path, parentIndex);
  1078. //if(node->actor->hero->visitablePos() != node->coord)
  1079. {
  1080. AIPathNodeInfo pathNode;
  1081. pathNode.cost = node->getCost();
  1082. pathNode.targetHero = node->actor->hero;
  1083. pathNode.chainMask = node->actor->chainMask;
  1084. pathNode.specialAction = node->specialAction;
  1085. pathNode.turns = node->turns;
  1086. pathNode.danger = node->danger;
  1087. pathNode.coord = node->coord;
  1088. pathNode.parentIndex = parentIndex;
  1089. pathNode.actionIsBlocked = false;
  1090. if(pathNode.specialAction)
  1091. {
  1092. auto targetNode =node->theNodeBefore ? getAINode(node->theNodeBefore) : node;
  1093. pathNode.actionIsBlocked = !pathNode.specialAction->canAct(targetNode);
  1094. }
  1095. parentIndex = path.nodes.size();
  1096. path.nodes.push_back(pathNode);
  1097. }
  1098. node = getAINode(node->theNodeBefore);
  1099. }
  1100. }
  1101. AIPath::AIPath()
  1102. : nodes({})
  1103. {
  1104. }
  1105. std::shared_ptr<const SpecialAction> AIPath::getFirstBlockedAction() const
  1106. {
  1107. for(auto node = nodes.rbegin(); node != nodes.rend(); node++)
  1108. {
  1109. if(node->specialAction && node->actionIsBlocked)
  1110. return node->specialAction;
  1111. }
  1112. return std::shared_ptr<const SpecialAction>();
  1113. }
  1114. int3 AIPath::firstTileToGet() const
  1115. {
  1116. if(nodes.size())
  1117. {
  1118. return nodes.back().coord;
  1119. }
  1120. return int3(-1, -1, -1);
  1121. }
  1122. int3 AIPath::targetTile() const
  1123. {
  1124. if(nodes.size())
  1125. {
  1126. return targetNode().coord;
  1127. }
  1128. return int3(-1, -1, -1);
  1129. }
  1130. const AIPathNodeInfo & AIPath::firstNode() const
  1131. {
  1132. return nodes.back();
  1133. }
  1134. const AIPathNodeInfo & AIPath::targetNode() const
  1135. {
  1136. auto & node = nodes.front();
  1137. return targetHero == node.targetHero ? node : nodes.at(1);
  1138. }
  1139. uint64_t AIPath::getPathDanger() const
  1140. {
  1141. if(nodes.empty())
  1142. return 0;
  1143. return targetNode().danger;
  1144. }
  1145. float AIPath::movementCost() const
  1146. {
  1147. if(nodes.empty())
  1148. return 0.0f;
  1149. return targetNode().cost;
  1150. }
  1151. uint8_t AIPath::turn() const
  1152. {
  1153. if(nodes.empty())
  1154. return 0;
  1155. return targetNode().turns;
  1156. }
  1157. uint64_t AIPath::getHeroStrength() const
  1158. {
  1159. return targetHero->getFightingStrength() * heroArmy->getArmyStrength();
  1160. }
  1161. uint64_t AIPath::getTotalDanger() const
  1162. {
  1163. uint64_t pathDanger = getPathDanger();
  1164. uint64_t danger = pathDanger > targetObjectDanger ? pathDanger : targetObjectDanger;
  1165. return danger;
  1166. }
  1167. bool AIPath::containsHero(const CGHeroInstance * hero) const
  1168. {
  1169. if(targetHero == hero)
  1170. return true;
  1171. for(auto node : nodes)
  1172. {
  1173. if(node.targetHero == hero)
  1174. return true;
  1175. }
  1176. return false;
  1177. }
  1178. uint64_t AIPath::getTotalArmyLoss() const
  1179. {
  1180. return armyLoss + targetObjectArmyLoss;
  1181. }
  1182. std::string AIPath::toString() const
  1183. {
  1184. std::stringstream str;
  1185. str << targetHero->getNameTranslated() << "[" << std::hex << chainMask << std::dec << "]" << ", turn " << (int)(turn()) << ": ";
  1186. for(auto node : nodes)
  1187. str << node.targetHero->getNameTranslated() << "[" << std::hex << node.chainMask << std::dec << "]" << "->" << node.coord.toString() << "; ";
  1188. return str.str();
  1189. }
  1190. }