1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
/*
* CPathfinder.h, part of VCMI engine
*
* Authors: listed in file AUTHORS in main folder
*
* License: GNU General Public License v2.0 or later
* Full text of license available in license.txt file, in main folder
*
*/
#pragma once
#include "CGPathNode.h"
#include "../IGameCallback.h"
#include "../bonuses/BonusEnum.h"
VCMI_LIB_NAMESPACE_BEGIN
class CGWhirlpool;
class TurnInfo;
struct PathfinderOptions;
// Optimized storage - tile can have 0-8 neighbour tiles
// static_vector uses fixed, preallocated storage (capacity) and dynamic size
// this avoid dynamic allocations on huge number of neighbour list queries
using NeighbourTilesVector = boost::container::static_vector<int3, 8>;
// Optimized storage to minimize dynamic allocations - most of teleporters have only one exit, but some may have more (premade maps, castle gates)
using TeleporterTilesVector = boost::container::small_vector<int3, 4>;
class DLL_LINKAGE CPathfinder
{
public:
friend class CPathfinderHelper;
CPathfinder(
CGameState * _gs,
std::shared_ptr<PathfinderConfig> config);
void calculatePaths(); //calculates possible paths for hero, uses current hero position and movement left; returns pointer to newly allocated CPath or nullptr if path does not exists
private:
CGameState * gamestate;
using ELayer = EPathfindingLayer;
std::shared_ptr<PathfinderConfig> config;
boost::heap::fibonacci_heap<CGPathNode *, boost::heap::compare<NodeComparer<CGPathNode>> > pq;
PathNodeInfo source; //current (source) path node -> we took it from the queue
CDestinationNodeInfo destination; //destination node -> it's a neighbour of source that we consider
bool isLayerTransitionPossible() const;
EPathNodeAction getTeleportDestAction() const;
bool isDestinationGuardian() const;
void initializeGraph();
STRONG_INLINE
void push(CGPathNode * node);
STRONG_INLINE
CGPathNode * topAndPop();
};
class DLL_LINKAGE CPathfinderHelper : private CGameInfoCallback
{
public:
enum EPatrolState
{
PATROL_NONE = 0,
PATROL_LOCKED = 1,
PATROL_RADIUS
} patrolState;
std::unordered_set<int3> patrolTiles;
int turn;
PlayerColor owner;
const CGHeroInstance * hero;
std::vector<std::unique_ptr<TurnInfo>> turnsInfo;
const PathfinderOptions & options;
bool canCastFly;
bool canCastWaterWalk;
bool whirlpoolProtection;
CPathfinderHelper(CGameState * gs, const CGHeroInstance * Hero, const PathfinderOptions & Options);
virtual ~CPathfinderHelper();
void initializePatrol();
bool isHeroPatrolLocked() const;
bool canMoveFromNode(const PathNodeInfo & source) const;
bool isPatrolMovementAllowed(const int3 & dst) const;
void updateTurnInfo(const int turn = 0);
bool isLayerAvailable(const EPathfindingLayer & layer) const;
const TurnInfo * getTurnInfo() const;
int getMaxMovePoints(const EPathfindingLayer & layer) const;
TeleporterTilesVector getCastleGates(const PathNodeInfo & source) const;
bool isAllowedTeleportEntrance(const CGTeleport * obj) const;
TeleporterTilesVector getAllowedTeleportChannelExits(const TeleportChannelID & channelID) const;
bool addTeleportTwoWay(const CGTeleport * obj) const;
bool addTeleportOneWay(const CGTeleport * obj) const;
bool addTeleportOneWayRandom(const CGTeleport * obj) const;
bool addTeleportWhirlpool(const CGWhirlpool * obj) const;
bool canMoveBetween(const int3 & a, const int3 & b) const; //checks only for visitable objects that may make moving between tiles impossible, not other conditions (like tiles itself accessibility)
void calculateNeighbourTiles(NeighbourTilesVector & result, const PathNodeInfo & source) const;
TeleporterTilesVector getTeleportExits(const PathNodeInfo & source) const;
void getNeighbours(
const TerrainTile & srcTile,
const int3 & srcCoord,
NeighbourTilesVector & vec,
const boost::logic::tribool & onLand,
const bool limitCoastSailing) const;
int getMovementCost(
const int3 & src,
const int3 & dst,
const TerrainTile * ct,
const TerrainTile * dt,
const int remainingMovePoints = -1,
const bool checkLast = true,
boost::logic::tribool isDstSailLayer = boost::logic::indeterminate,
boost::logic::tribool isDstWaterLayer = boost::logic::indeterminate) const;
int getMovementCost(
const PathNodeInfo & src,
const PathNodeInfo & dst,
const int remainingMovePoints = -1,
const bool checkLast = true) const;
int movementPointsAfterEmbark(int movement, int basicCost, bool disembark) const;
bool passOneTurnLimitCheck(const PathNodeInfo & source) const;
int getGuardiansCount(int3 tile) const;
};
VCMI_LIB_NAMESPACE_END
|
