AINodeStorage.cpp 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290
  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. AINodeStorage::AINodeStorage(const int3 & Sizes)
  13. : sizes(Sizes)
  14. {
  15. nodes.resize(boost::extents[sizes.x][sizes.y][sizes.z][EPathfindingLayer::NUM_LAYERS][NUM_CHAINS]);
  16. }
  17. AINodeStorage::~AINodeStorage()
  18. {
  19. }
  20. const AIPathNode * AINodeStorage::getAINode(const CGPathNode * node) const
  21. {
  22. return static_cast<const AIPathNode *>(node);
  23. }
  24. void AINodeStorage::updateAINode(CGPathNode * node, std::function<void(AIPathNode *)> updater)
  25. {
  26. auto aiNode = static_cast<AIPathNode *>(node);
  27. updater(aiNode);
  28. }
  29. bool AINodeStorage::isBattleNode(const CGPathNode * node) const
  30. {
  31. return (getAINode(node)->chainMask & BATTLE_CHAIN) > 0;
  32. }
  33. boost::optional<AIPathNode *> AINodeStorage::getOrCreateNode(const int3 & pos, const EPathfindingLayer layer, int chainNumber)
  34. {
  35. auto chains = nodes[pos.x][pos.y][pos.z][layer];
  36. for(AIPathNode & node : chains)
  37. {
  38. if(node.chainMask == chainNumber)
  39. {
  40. return &node;
  41. }
  42. if(node.chainMask == 0)
  43. {
  44. node.chainMask = chainNumber;
  45. return &node;
  46. }
  47. }
  48. return boost::none;
  49. }
  50. CGPathNode * AINodeStorage::getInitialNode()
  51. {
  52. auto hpos = hero->getPosition(false);
  53. auto initialNode =
  54. getOrCreateNode(hpos, hero->boat ? EPathfindingLayer::SAIL : EPathfindingLayer::LAND, NORMAL_CHAIN)
  55. .get();
  56. initialNode->turns = 0;
  57. initialNode->moveRemains = hero->movement;
  58. initialNode->danger = 0;
  59. return initialNode;
  60. }
  61. void AINodeStorage::resetTile(const int3 & coord, EPathfindingLayer layer, CGPathNode::EAccessibility accessibility)
  62. {
  63. for(int i = 0; i < NUM_CHAINS; i++)
  64. {
  65. AIPathNode & heroNode = nodes[coord.x][coord.y][coord.z][layer][i];
  66. heroNode.chainMask = 0;
  67. heroNode.danger = 0;
  68. heroNode.manaCost = 0;
  69. heroNode.specialAction.reset();
  70. heroNode.update(coord, layer, accessibility);
  71. }
  72. }
  73. void AINodeStorage::commit(CDestinationNodeInfo & destination, const PathNodeInfo & source)
  74. {
  75. const AIPathNode * srcNode = getAINode(source.node);
  76. updateAINode(destination.node, [&](AIPathNode * dstNode) {
  77. dstNode->moveRemains = destination.movementLeft;
  78. dstNode->turns = destination.turn;
  79. dstNode->danger = srcNode->danger;
  80. dstNode->action = destination.action;
  81. dstNode->theNodeBefore = srcNode->theNodeBefore;
  82. dstNode->manaCost = srcNode->manaCost;
  83. if(dstNode->specialAction)
  84. {
  85. dstNode->specialAction->applyOnDestination(getHero(), destination, source, dstNode, srcNode);
  86. }
  87. });
  88. }
  89. std::vector<CGPathNode *> AINodeStorage::calculateNeighbours(
  90. const PathNodeInfo & source,
  91. const PathfinderConfig * pathfinderConfig,
  92. const CPathfinderHelper * pathfinderHelper)
  93. {
  94. std::vector<CGPathNode *> neighbours;
  95. neighbours.reserve(16);
  96. const AIPathNode * srcNode = getAINode(source.node);
  97. auto accessibleNeighbourTiles = pathfinderHelper->getNeighbourTiles(source);
  98. for(auto & neighbour : accessibleNeighbourTiles)
  99. {
  100. for(EPathfindingLayer i = EPathfindingLayer::LAND; i <= EPathfindingLayer::AIR; i.advance(1))
  101. {
  102. auto nextNode = getOrCreateNode(neighbour, i, srcNode->chainMask);
  103. if(!nextNode || nextNode.get()->accessible == CGPathNode::NOT_SET)
  104. continue;
  105. neighbours.push_back(nextNode.get());
  106. }
  107. }
  108. return neighbours;
  109. }
  110. std::vector<CGPathNode *> AINodeStorage::calculateTeleportations(
  111. const PathNodeInfo & source,
  112. const PathfinderConfig * pathfinderConfig,
  113. const CPathfinderHelper * pathfinderHelper)
  114. {
  115. std::vector<CGPathNode *> neighbours;
  116. auto accessibleExits = pathfinderHelper->getTeleportExits(source);
  117. auto srcNode = getAINode(source.node);
  118. for(auto & neighbour : accessibleExits)
  119. {
  120. auto node = getOrCreateNode(neighbour, source.node->layer, srcNode->chainMask);
  121. if(!node)
  122. continue;
  123. neighbours.push_back(node.get());
  124. }
  125. return neighbours;
  126. }
  127. bool AINodeStorage::hasBetterChain(const PathNodeInfo & source, CDestinationNodeInfo & destination) const
  128. {
  129. auto pos = destination.coord;
  130. auto chains = nodes[pos.x][pos.y][pos.z][EPathfindingLayer::LAND];
  131. auto destinationNode = getAINode(destination.node);
  132. for(const AIPathNode & node : chains)
  133. {
  134. auto sameNode = node.chainMask == destinationNode->chainMask;
  135. if(sameNode || node.action == CGPathNode::ENodeAction::UNKNOWN)
  136. {
  137. continue;
  138. }
  139. if(node.danger <= destinationNode->danger && destinationNode->chainMask == 1 && node.chainMask == 0)
  140. {
  141. if(node.turns < destinationNode->turns
  142. || (node.turns == destinationNode->turns && node.moveRemains >= destinationNode->moveRemains))
  143. {
  144. logAi->trace(
  145. "Block ineficient move %s:->%s, mask=%i, mp diff: %i",
  146. source.coord.toString(),
  147. destination.coord.toString(),
  148. destinationNode->chainMask,
  149. node.moveRemains - destinationNode->moveRemains);
  150. return true;
  151. }
  152. }
  153. }
  154. return false;
  155. }
  156. bool AINodeStorage::isTileAccessible(int3 pos, const EPathfindingLayer layer) const
  157. {
  158. std::vector<AIPath> paths;
  159. auto chains = nodes[pos.x][pos.y][pos.z][layer];
  160. auto initialPos = hero->visitablePos();
  161. for(const AIPathNode & node : chains)
  162. {
  163. if(node.action != CGPathNode::ENodeAction::UNKNOWN)
  164. {
  165. return true;
  166. }
  167. }
  168. return false;
  169. }
  170. std::vector<AIPath> AINodeStorage::getChainInfo(int3 pos, bool isOnLand) const
  171. {
  172. std::vector<AIPath> paths;
  173. auto chains = nodes[pos.x][pos.y][pos.z][isOnLand ? EPathfindingLayer::LAND : EPathfindingLayer::SAIL];
  174. auto initialPos = hero->visitablePos();
  175. for(const AIPathNode & node : chains)
  176. {
  177. if(node.action == CGPathNode::ENodeAction::UNKNOWN)
  178. {
  179. continue;
  180. }
  181. AIPath path;
  182. const AIPathNode * current = &node;
  183. while(current != nullptr && current->coord != initialPos)
  184. {
  185. AIPathNodeInfo pathNode;
  186. pathNode.movementPointsLeft = current->moveRemains;
  187. pathNode.movementPointsUsed = (int)(current->turns * hero->maxMovePoints(true) + hero->movement) - (int)current->moveRemains;
  188. pathNode.turns = current->turns;
  189. pathNode.danger = current->danger;
  190. pathNode.coord = current->coord;
  191. path.nodes.push_back(pathNode);
  192. path.specialAction = current->specialAction;
  193. current = getAINode(current->theNodeBefore);
  194. }
  195. paths.push_back(path);
  196. }
  197. return paths;
  198. }
  199. AIPath::AIPath()
  200. : nodes({})
  201. {
  202. }
  203. int3 AIPath::firstTileToGet() const
  204. {
  205. if(nodes.size())
  206. {
  207. return nodes.back().coord;
  208. }
  209. return int3(-1, -1, -1);
  210. }
  211. uint64_t AIPath::getPathDanger() const
  212. {
  213. if(nodes.size())
  214. {
  215. return nodes.front().danger;
  216. }
  217. return 0;
  218. }
  219. uint32_t AIPath::movementCost() const
  220. {
  221. if(nodes.size())
  222. {
  223. return nodes.front().movementPointsUsed;
  224. }
  225. // TODO: boost:optional?
  226. return 0;
  227. }
  228. uint64_t AIPath::getTotalDanger(HeroPtr hero) const
  229. {
  230. uint64_t pathDanger = getPathDanger();
  231. uint64_t objDanger = evaluateDanger(nodes.front().coord, hero.get()); // bank danger is not checked by pathfinder
  232. uint64_t danger = pathDanger > objDanger ? pathDanger : objDanger;
  233. return danger;
  234. }