Advanced Strategic Command
astar2.h
Go to the documentation of this file.
1 
6 #ifndef astar2H
7  #define astar2H
8 
9  #include <vector>
10  #include "mapalgorithms.h"
11  #include "gamemap.h"
12 
13  #include <boost/unordered_map.hpp>
14 
16 
17 
19 class AStar3D {
20  public:
21  typedef float DistanceType;
22  static const DistanceType longestPath;
24  public:
25  virtual bool allowHeightChange() = 0;
26  virtual bool allowMovement() = 0;
27  virtual bool allowLeavingContainer() = 0;
28  virtual bool allowDocking() = 0;
29  virtual ~OperationLimiter() {};
30  };
31 
32 
33  class PathPoint: public MapCoordinate3D {
34  PathPoint() {};
35  public:
36  PathPoint ( const MapCoordinate3D& mc, int dist_, int enterHeight_, bool hasAttacked_ ) : MapCoordinate3D(mc), dist(dist_), enterHeight(enterHeight_), hasAttacked(hasAttacked_) {};
37  // PathPoint ( const MapCoordinate3D& mc ) : MapCoordinate3D(mc), dist(-1), enterHeight(-1), hasAttacked(false) {};
38  int getRealHeight() { if ( getNumericalHeight() != -1 ) return getNumericalHeight(); else return enterHeight; };
40  int dist;
43  void write( tnstream& stream ) const;
44  void read( tnstream& stream );
45  static PathPoint newFromStream( tnstream& stream );
46  };
47 
48  typedef deque<PathPoint> Path;
49 
51  size_t operator()(const MapCoordinate3D &h) const{
52  return h.x ^ (h.y << 12) ^ (h.getNumericalHeight() << 24);
53  }
54  };
55 
57  size_t operator()(const MapCoordinate &h) const{
58  return h.x ^ (h.y << 16);
59  }
60  };
61 
62  struct Node {
63  const Node* previous;
64  MapCoordinate3D h; // location on the map, in hex coordinates
65  AStar3D::DistanceType gval; // g in A* represents how far we've already gone
66  AStar3D::DistanceType hval; // h in A* represents an estimate of how far is left
68  bool canStop;
70  bool operator< ( const Node& b ) const;
71  bool operator> ( const Node& b ) const;
72  };
73 
74  protected:
83  bool markTemps;
85 
86  virtual DistanceType getMoveCost ( const MapCoordinate3D& start, const MapCoordinate3D& dest, const Vehicle* vehicle, bool& hasAttacked );
87 
88  typedef boost::unordered_map<MapCoordinate, int, hash_MapCoordinate> fieldAccessType;
90 
91  DistanceType dist( const MapCoordinate3D& a, const MapCoordinate3D& b );
92  DistanceType dist( const MapCoordinate3D& a, const vector<MapCoordinate3D>& b );
93 
94  public:
96  // pointers to nodes in this container need to stay valid when the
97  // container grows, so we can't use a vector for this.
99  typedef boost::unordered_map<MapCoordinate3D, Node*, hash_MapCoordinate3D> index_t;
100  typedef deque<Node> storage_t;
101  index_t index;
102  storage_t storage;
103  public:
104  typedef storage_t::iterator iterator;
105  const Node* add ( const Node& n) {
106  storage.push_back(n);
107  index.insert(make_pair(n.h, &storage.back()));
108  return &storage.back();
109  };
110  const Node* find ( const MapCoordinate3D& pos ) {
111  index_t::iterator i = index.find(pos);
112  if (i == index.end()) return NULL;
113  else return i->second;
114  }
115 
116  iterator begin() { return storage.begin(); };
117  iterator end() { return storage.end(); };
118  const Node& back() { return storage.back(); };
119  int size() const { return storage.size(); };
120  int empty() const { return storage.empty(); };
121  };
123  protected:
124 
125  int initNode ( Node& newN,
126  const Node* oldN_ptr,
127  const MapCoordinate3D& newpos,
128  const vector<MapCoordinate3D>& B,
129  bool disableAttack=false,
130  bool enter=false,
131  bool dock=false);
132 
133  public:
134  AStar3D ( GameMap* actmap, Vehicle* veh, bool markTemps_ = true, int maxDistance = maxint );
135 
136 
139 
141  bool findPath( const MapCoordinate3D& dest );
142 
144  bool findPath( const vector<MapCoordinate3D>& dest );
145 
147  void findPath( Path& path, const MapCoordinate3D& dest );
148 
150  bool findPath( Path& path, const vector<MapCoordinate3D>& dest );
151 
157  void findAllAccessibleFields ( );
158 
160  bool constructPath( Path& path, const Node* n);
161 
163  inline bool constructPath( Path& path, const MapCoordinate3D& pos) { return constructPath ( path, visited.find (pos) ); }
164 
166  int getDistance( );
167 
169  int getTravelTime( );
170 
171  int getFieldAccess ( int x, int y );
172  int getFieldAccess ( const MapCoordinate& mc );
173 
175  void dumpVisited();
176 
177  virtual ~AStar3D ( );
178  };
179 
180 #endif
void findAllAccessibleFields()
searches for all fields that are within the range of maxDist and marks them.
Definition: astar2.cpp:562
OperationLimiter * operationLimiter
Definition: astar2.h:75
PathPoint(const MapCoordinate3D &mc, int dist_, int enterHeight_, bool hasAttacked_)
Definition: astar2.h:36
float vehicleSpeedFactor[8]
Definition: astar2.h:81
int MAXIMUM_PATH_LENGTH
Definition: astar2.h:76
Definition: astar2.h:15
bool operator>(const Node &b) const
Definition: astar2.cpp:115
int size() const
Definition: astar2.h:119
int getTravelTime()
returns the number of turns that the unit will need to travel along the last found path ...
VisitedContainer visited
Definition: astar2.h:122
bool operator<(const Node &b) const
Definition: astar2.cpp:109
static const DistanceType longestPath
Definition: astar2.h:22
virtual bool allowLeavingContainer()=0
float maxVehicleSpeedFactor
Definition: astar2.h:82
int getNumericalHeight() const
Definition: typen.h:242
int initNode(Node &newN, const Node *oldN_ptr, const MapCoordinate3D &newpos, const vector< MapCoordinate3D > &B, bool disableAttack=false, bool enter=false, bool dock=false)
Definition: astar2.cpp:242
int enterHeight
Definition: astar2.h:67
storage_t::iterator iterator
Definition: astar2.h:104
size_t operator()(const MapCoordinate3D &h) const
Definition: astar2.h:51
The interface for all kinds of IO stream.
bool hasAttacked
Definition: astar2.h:42
MapCoordinate3D getRealPos()
Definition: astar2.h:39
bool hasAttacked
Definition: astar2.h:69
virtual ~AStar3D()
Definition: astar2.cpp:173
virtual bool allowHeightChange()=0
bool findPath(const MapCoordinate3D &dest)
searches for a path from the unit's current position to dest
Definition: astar2.cpp:335
size_t operator()(const MapCoordinate &h) const
Definition: astar2.h:57
const Node * previous
Definition: astar2.h:63
GameMap * tempsMarked
Definition: astar2.h:77
virtual bool allowMovement()=0
Coordinate on the twodimensional map.
Definition: typen.h:202
Definition of THE central asc class: GameMap.
bool canStop
Definition: astar2.h:68
WindMovement * wind
Definition: astar2.h:84
virtual bool allowDocking()=0
Definition: astar2.h:15
virtual ~OperationLimiter()
Definition: astar2.h:29
void setnum(int _x, int _y, int numericalz)
Definition: typen.h:250
AStar3D(GameMap *actmap, Vehicle *veh, bool markTemps_=true, int maxDistance=maxint)
Definition: astar2.cpp:128
virtual DistanceType getMoveCost(const MapCoordinate3D &start, const MapCoordinate3D &dest, const Vehicle *vehicle, bool &hasAttacked)
Definition: astar2.cpp:221
GameMap * actmap
Definition: astar2.h:80
float DistanceType
Definition: astar2.h:21
boost::unordered_map< MapCoordinate, int, hash_MapCoordinate > fieldAccessType
Definition: astar2.h:88
const Node & back()
Definition: astar2.h:118
bool markTemps
Definition: astar2.h:83
DistanceType dist(const MapCoordinate3D &a, const MapCoordinate3D &b)
Definition: astar2.cpp:184
AStar3D::DistanceType hval
Definition: astar2.h:66
caches some calculations for the effects that wind has on the movement of units
bool constructPath(Path &path, const MapCoordinate3D &pos)
construct a path from a pointer to a visited node; return false if position doesn't exist...
Definition: astar2.h:163
HexDirection
Definition: astar2.h:15
the reachable fields
Definition: astar2.h:98
void write(tnstream &stream) const
Definition: astar2.cpp:593
void read(tnstream &stream)
Definition: astar2.cpp:602
int getDistance()
returns the distance of the last found path, or -1 on any error
void registerOperationLimiter(OperationLimiter *ol)
the search can be restricted to certain operations
Definition: astar2.h:138
void dumpVisited()
for debugging: dumps the contents of the visited node to stdout
Definition: astar2.cpp:619
Definition: astar2.h:15
Definition: astar2.h:15
static PathPoint newFromStream(tnstream &stream)
Definition: astar2.cpp:612
deque< PathPoint > Path
Definition: astar2.h:48
int getFieldAccess(int x, int y)
Definition: astar2.cpp:582
int getRealHeight()
Definition: astar2.h:38
Coordinate on the map including height.
Definition: typen.h:238
bool constructPath(Path &path, const Node *n)
construct a path from a pointer to a visited node, return false if pointer is NULL, else true
Definition: astar2.cpp:546
A 3D path finding algorithm, based on the 2D algorithm by Amit J. Patel.
Definition: astar2.h:19
#define maxint
Definition: typen.h:462
fieldAccessType fieldAccess
Definition: astar2.h:89
const Node * find(const MapCoordinate3D &pos)
Definition: astar2.h:110
const Node * add(const Node &n)
Definition: astar2.h:105
Vehicle * veh
Definition: astar2.h:79
int empty() const
Definition: astar2.h:120
Definition: astar2.h:15
AStar3D::DistanceType gval
Definition: astar2.h:65
Path * _path
Definition: astar2.h:78
Definition: astar2.h:15
Definition: astar2.h:15
The map. THE central structure of ASC, which holds everything not globally available together...
Definition: gamemap.h:182
MapCoordinate3D h
Definition: astar2.h:64