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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
/*! \file astar2.h
\brief Interface for the A* pathfinding algorithm
*/
#ifndef astar2H
#define astar2H
#include <vector>
#include "mapalgorithms.h"
#include "gamemap.h"
#include <boost/unordered_map.hpp>
enum HexDirection { DirN, DirNE, DirSE, DirS, DirSW, DirNW, DirNone };
//! A 3D path finding algorithm, based on the 2D algorithm by Amit J. Patel
class AStar3D {
public:
typedef float DistanceType;
static const DistanceType longestPath;
class OperationLimiter {
public:
virtual bool allowHeightChange() = 0;
virtual bool allowMovement() = 0;
virtual bool allowLeavingContainer() = 0;
virtual bool allowDocking() = 0;
virtual ~OperationLimiter() {};
};
class PathPoint: public MapCoordinate3D {
PathPoint() {};
public:
PathPoint ( const MapCoordinate3D& mc, int dist_, int enterHeight_, bool hasAttacked_ ) : MapCoordinate3D(mc), dist(dist_), enterHeight(enterHeight_), hasAttacked(hasAttacked_) {};
// PathPoint ( const MapCoordinate3D& mc ) : MapCoordinate3D(mc), dist(-1), enterHeight(-1), hasAttacked(false) {};
int getRealHeight() { if ( getNumericalHeight() != -1 ) return getNumericalHeight(); else return enterHeight; };
MapCoordinate3D getRealPos() { MapCoordinate3D p; p.setnum(x,y, getRealHeight()); return p; };
int dist;
int enterHeight;
bool hasAttacked;
void write( tnstream& stream ) const;
void read( tnstream& stream );
static PathPoint newFromStream( tnstream& stream );
};
typedef deque<PathPoint> Path;
struct hash_MapCoordinate3D {
size_t operator()(const MapCoordinate3D &h) const{
return h.x ^ (h.y << 12) ^ (h.getNumericalHeight() << 24);
}
};
struct hash_MapCoordinate {
size_t operator()(const MapCoordinate &h) const{
return h.x ^ (h.y << 16);
}
};
struct Node {
const Node* previous;
MapCoordinate3D h; // location on the map, in hex coordinates
AStar3D::DistanceType gval; // g in A* represents how far we've already gone
AStar3D::DistanceType hval; // h in A* represents an estimate of how far is left
int enterHeight;
bool canStop;
bool hasAttacked;
bool operator< ( const Node& b ) const;
bool operator> ( const Node& b ) const;
};
protected:
OperationLimiter* operationLimiter;
int MAXIMUM_PATH_LENGTH;
GameMap* tempsMarked;
Path *_path;
Vehicle* veh;
GameMap* actmap;
float vehicleSpeedFactor[8];
float maxVehicleSpeedFactor;
bool markTemps;
WindMovement* wind;
virtual DistanceType getMoveCost ( const MapCoordinate3D& start, const MapCoordinate3D& dest, const Vehicle* vehicle, bool& hasAttacked );
typedef boost::unordered_map<MapCoordinate, int, hash_MapCoordinate> fieldAccessType;
fieldAccessType fieldAccess;
DistanceType dist( const MapCoordinate3D& a, const MapCoordinate3D& b );
DistanceType dist( const MapCoordinate3D& a, const vector<MapCoordinate3D>& b );
public:
//! the reachable fields
// pointers to nodes in this container need to stay valid when the
// container grows, so we can't use a vector for this.
class VisitedContainer {
typedef boost::unordered_map<MapCoordinate3D, Node*, hash_MapCoordinate3D> index_t;
typedef deque<Node> storage_t;
index_t index;
storage_t storage;
public:
typedef storage_t::iterator iterator;
const Node* add ( const Node& n) {
storage.push_back(n);
index.insert(make_pair(n.h, &storage.back()));
return &storage.back();
};
const Node* find ( const MapCoordinate3D& pos ) {
index_t::iterator i = index.find(pos);
if (i == index.end()) return NULL;
else return i->second;
}
iterator begin() { return storage.begin(); };
iterator end() { return storage.end(); };
const Node& back() { return storage.back(); };
int size() const { return storage.size(); };
int empty() const { return storage.empty(); };
};
VisitedContainer visited;
protected:
int initNode ( Node& newN,
const Node* oldN_ptr,
const MapCoordinate3D& newpos,
const vector<MapCoordinate3D>& B,
bool disableAttack=false,
bool enter=false,
bool dock=false);
public:
AStar3D ( GameMap* actmap, Vehicle* veh, bool markTemps_ = true, int maxDistance = maxint );
//! the search can be restricted to certain operations
void registerOperationLimiter( OperationLimiter* ol ) { operationLimiter = ol; };
//! searches for a path from the unit's current position to dest
bool findPath( const MapCoordinate3D& dest );
//! searches for a path from the units current position to one of the dest fields
bool findPath( const vector<MapCoordinate3D>& dest );
//! searches for a path from the unit's current position to dest and stores it in path
void findPath( Path& path, const MapCoordinate3D& dest );
//! searches for a path from the units current position to one of the dest fields and stores it in path
bool findPath( Path& path, const vector<MapCoordinate3D>& dest );
/** searches for all fields that are within the range of maxDist and marks them.
On each field one bit for each level of height will be set.
The Destructor removes all marks.
\param path if non-null, all fields will be stored there
*/
void findAllAccessibleFields ( );
//! construct a path from a pointer to a visited node, return false if pointer is NULL, else true
bool constructPath( Path& path, const Node* n);
//! construct a path from a pointer to a visited node; return false if position doesn't exist, else true
inline bool constructPath( Path& path, const MapCoordinate3D& pos) { return constructPath ( path, visited.find (pos) ); }
//! returns the distance of the last found path, or -1 on any error
int getDistance( );
//! returns the number of turns that the unit will need to travel along the last found path
int getTravelTime( );
int getFieldAccess ( int x, int y );
int getFieldAccess ( const MapCoordinate& mc );
//! for debugging: dumps the contents of the visited node to stdout
void dumpVisited();
virtual ~AStar3D ( );
};
#endif
|
