Advanced Strategic Command
astar2.cpp
Go to the documentation of this file.
1 
7 #include <vector>
8 #include <cmath>
9 
10 #include <boost/heap/pairing_heap.hpp>
11 
12 #include "vehicletype.h"
13 #include "spfst.h"
14 #include "controls.h"
15 
16 #include "astar2.h"
17 
18 #include <iostream>
19 
20 void dumpNode(const AStar3D::Node& n) {
21  cout << "(" << n.h.x << "," << n.h.y << "," << n.h.getNumericalHeight() << ")@" << n.gval << "\n";
22 }
23 
25  typedef boost::heap::pairing_heap<
27  boost::heap::compare<greater<AStar3D::Node> >,
28  boost::heap::stable<true>,
29  boost::heap::constant_time_size<false>
30  > storage_t;
31  typedef boost::unordered_map<
33  storage_t::handle_type,
35  > index_t;
36  typedef storage_t::handle_type handle_type;
37  storage_t storage;
38  index_t index;
39  public:
40  const AStar3D::Node& top() const { return storage.top(); }
41  void pop() { index.erase(storage.top().h); storage.pop(); }
42  int empty() const { return storage.empty(); }
43  void pushOrUpdate ( const AStar3D::Node& n ) {
44  const index_t::iterator i = index.find(n.h);
45  if (i == index.end()) {
46  index[n.h] = storage.push(n);
47  } else if (((*i->second).gval > n.gval) || ((*i->second).gval == n.gval && (*i->second).hasAttacked && !n.hasAttacked)) {
48  storage.increase(i->second, n);
49  }
50  }
51 };
52 
53 static inline int windbeeline ( const MapCoordinate& start, const MapCoordinate& dest, const WindMovement* wm ) {
54  int distance = 0;
55  int dx = dest.x - start.x;
56  int dy = dest.y - start.y;
57  int dyOdd = ((start.y & 1) - (dest.y & 1));
58 
59  if (dx == 0) {
60  if (dy > 0) {
61  distance = (minmalq - wm->getDist(2)) * ((dy - (dyOdd != 0)) / 2);
62  if (dyOdd == -1) {
63  distance += minmalq - wm->getDist(2);
64  } else if (dyOdd == 1) {
65  distance += minmalq - wm->getDist(4);
66  }
67  } if (dy < 0) {
68  distance = (minmalq - wm->getDist(2)) * -((dy + (dyOdd != 0)) / 2);
69  if (dyOdd == -1) {
70  distance += minmalq - wm->getDist(1);
71  } else if (dyOdd == 1) {
72  distance += minmalq - wm->getDist(5);
73  }
74  } // if dy == 0 then all values stay 0
75  } else if (dx > 0) {
76  if (dy >= (dx * 2)) {
77  distance = (minmalq - wm->getDist(3)) * (((dy + dyOdd) / 2) - dx)
78  + (minmalq - wm->getDist(2)) * (-dyOdd + dx * 2);
79  } else if (-dy >= (dx * 2)) {
80  distance = (minmalq - wm->getDist(0)) * (-((dy - dyOdd) / 2) - dx)
81  + (minmalq - wm->getDist(1)) * (-dyOdd + dx * 2);
82  } else {
83  distance = (minmalq - wm->getDist(2)) * (((dy - dyOdd) / 2) + dx)
84  + (minmalq - wm->getDist(1)) * (((-dy - dyOdd) / 2) + dx);
85  }
86  } else if (dx < 0) {
87  if (dy >= -(dx * 2)) {
88  distance = (minmalq - wm->getDist(3)) * (((dy - dyOdd) / 2) + dx)
89  + (minmalq - wm->getDist(4)) * (dyOdd - dx * 2);
90  } else if (-dy >= -(dx * 2)) {
91  distance = (minmalq - wm->getDist(0)) * (-((dy + dyOdd) / 2) + dx)
92  + (minmalq - wm->getDist(5)) * (dyOdd - dx * 2);
93  } else {
94  distance = (minmalq - wm->getDist(4)) * (((dy + dyOdd) / 2) - dx)
95  + (minmalq - wm->getDist(5)) * (((-dy + dyOdd) / 2) - dx);
96  }
97  }
98 
99  return distance;
100 }
101 
102 
107 
108 
110 {
111  // To compare two nodes, we compare the `f' value, which is the
112  // sum of the g and h values.
113  return (gval+hval) < (b.gval+b.hval);
114 }
116 {
117  // To compare two nodes, we compare the `f' value, which is the
118  // sum of the g and h values.
119  return (gval+hval) > (b.gval+b.hval);
120 }
121 
122 bool operator == ( const AStar3D::Node& a, const AStar3D::Node& b )
123 {
124  // Two nodes are equal if their components are equal
125  return (a.h == b.h) && (a.gval == b.gval ) && (a.hval == b.hval );
126 }
127 
128 AStar3D :: AStar3D ( GameMap* actmap_, Vehicle* veh_, bool markTemps_, int maxDistance )
129  : operationLimiter ( NULL )
130 {
131  markTemps = markTemps_;
132  tempsMarked = NULL;
133  _path = NULL;
134  veh = veh_;
135  actmap = actmap_;
136 
137  MAXIMUM_PATH_LENGTH = maxDistance;
140 
141 /*
142  if ( !veh->maxMovement() ) {
143  // fatalError ( "AStar3D :: AStar3D - trying to move a immobile unit");
144  int foo = veh->maxMovement()*2;
145  }
146 */
147 
148  if ( veh->getPosition().getNumericalHeight() >= 0 )
149  for ( int i = 0; i < 8; i++ )
150  if ( veh->maxMovement() )
151  vehicleSpeedFactor[i] = float(veh->typ->movement[i]) / veh->maxMovement();
152  else
153  vehicleSpeedFactor[i] = 0.00001;
154 
155  else
156  for ( int i = 0; i < 8; i++ )
157  vehicleSpeedFactor[i] = float(veh->typ->movement[i]);
158 
160  for ( int i = 0; i < 8; ++i )
162 
164  wind = new WindMovement ( veh );
165  else
166  wind = NULL;
167 
168 }
169 
171 
172 
174 {
175  if( tempsMarked )
176  tempsMarked->cleartemps ( 3 );
177 
178  if ( wind ) {
179  delete wind;
180  wind = NULL;
181  }
182 }
183 
185 {
186  int heightDiff;
187  if ( b.getNumericalHeight() >= 0 && a.getNumericalHeight() >= 0 )
188  heightDiff = abs ( b.getNumericalHeight() - a.getNumericalHeight() ) * minmalq/2;
189  else
190  heightDiff = 0;
191 
193  if ( b.valid() ) {
195  dist = windbeeline(a, b, wind ) + heightDiff;
196  } else {
197  dist = beeline ( a, b ) + heightDiff;
198  }
199  } else {
200  dist = 0;
201  }
202  return dist;
203 }
204 
205 AStar3D::DistanceType AStar3D::dist ( const MapCoordinate3D& a, const vector<MapCoordinate3D>& b )
206 {
207  if (b.empty())
208  return 0;
209 
211  for ( vector<MapCoordinate3D>::const_iterator i = b.begin(); i != b.end(); ++i ) {
212  DistanceType e = dist(a,*i);
213  if ( maxVehicleSpeedFactor )
215  e2 = min( e2,e );
216  }
217  return min(e2, longestPath);
218 }
219 
220 
221 AStar3D::DistanceType AStar3D::getMoveCost ( const MapCoordinate3D& start, const MapCoordinate3D& dest, const Vehicle* vehicle, bool& hasAttacked )
222 {
223  // since we are operating at different levels of height and the unit has different
224  // speeds at different levels of height, we must not optimize for distance, but for
225  // travel time.
226  int movecost = calcMoveMalus ( start, dest, vehicle, wind, &hasAttacked ).first;
227 
228  if ( start.getNumericalHeight() >= 0 )
229  if ( movecost > veh->typ->movement[start.getNumericalHeight()] )
230  return longestPath;
231 
232 
233  if ( start.getNumericalHeight() < 0 )
234  return movecost;
235  else
236  if ( !vehicleSpeedFactor[start.getNumericalHeight()] )
237  return longestPath;
238  else
239  return movecost / vehicleSpeedFactor[start.getNumericalHeight()];
240 }
241 
243  const Node* oldN_ptr,
244  const MapCoordinate3D& newpos,
245  const vector<MapCoordinate3D>& B,
246  bool disableAttack,
247  bool enter,
248  bool dock) {
249  int fa;
250 
251  newN.h = newpos;
252 
253  // No need to reassess already visited Node
254  if ( (oldN_ptr->previous) && (newN.h == oldN_ptr->previous->h) )
255  return 0;
256 
257  // If it's off the end of the map, then don't keep scanning
258  if( newN.h.x < 0 || newN.h.y < 0 || newN.h.x >= actmap->xsize || newN.h.y >= actmap->ysize )
259  return 0;
260 
261  if (enter) {
262  newN.enterHeight = newN.h.getNumericalHeight();
263  newN.h.setNumericalHeight(-1);
264  } else {
265  newN.enterHeight = -1;
266  }
267 
268  if ( visited.find(newN.h) )
269  return 0;
270 
271  newN.hasAttacked = oldN_ptr->hasAttacked || disableAttack;
272 
273  if ( !dock ) {
274  fa = fieldAccessible ( actmap->getField ( newN.h ), veh, newN.h.getBitmappedHeight(), &newN.hasAttacked );
275  if ( !fa )
276  return 0;
277  newN.canStop = fa >= 2;
278 
279  newN.gval = oldN_ptr->gval + getMoveCost ( oldN_ptr->h, newN.h, veh, newN.hasAttacked );
280  } else {
281  fa = 1;
282  newN.canStop = true;
283  newN.gval = oldN_ptr->gval + 10;
284  }
285  if ( (newN.gval >= longestPath) || ( newN.gval > MAXIMUM_PATH_LENGTH ) )
286  return 0;
287 
288  newN.previous = oldN_ptr;
289  newN.hval = dist(newN.h, B);
290  return fa;
291 }
292 
293 const int* getDirectionOrder ( int x, int y, int x2, int y2 )
294 {
295  typedef const int Directions[sidenum];
296  static const Directions directions[3][3] = {{{5, 0, 4, 1, 3, 2 }, {0, 1, 5, 2, 4, 3 }, {1, 0, 2, 5, 3, 4 }},
297  {{5, 4, 0, 3, 1, 2 }, {0, 1, 2, 3, 4, 5 }, {1, 2, 0, 3, 5, 4 }},
298  {{4, 3, 5, 2, 0, 1 }, {3, 4, 2, 5, 1, 0 }, {2, 3, 1, 4, 0, 5 }}};
299  int a,b;
300 
301  int dx = (2 * x2 + (y2 & 1)) - (2 * x + (y & 1));
302  int dy = y2 - y;
303 
304  if (dx < 0)
305  a = 0;
306  else
307  if (dx == 0)
308  a = 1;
309  else
310  a = 2;
311 
312  if (dy < 0)
313  b = 0;
314  else
315  if (dy == 0)
316  b = 1;
317  else
318  b = 2;
319 
320  return (const int*)(&directions[b][a]);
321 }
322 
323 bool AStar3D::findPath( Path& path, const vector<MapCoordinate3D>& B ) {
324  _path = &path;
325 
326  if (findPath (B)) {
327  constructPath ( path, &visited.back() );
328  return true;
329  } else {
330  return false;
331  }
332 
333 }
334 
336  vector<MapCoordinate3D> vB;
337  vB.push_back(B);
338  return findPath(vB);
339 }
340 
341 bool AStar3D::findPath( const vector<MapCoordinate3D>& B ) {
342 
344 
345  OpenContainer open;
346 
347  /* this should be checked outside by giving the pathfinder the right movement
348  if ( !veh->canMove() )
349  return;
350  */
351 
352  if ( !visited.find(A) ) {
353  Node firstNode = Node();
354  firstNode.previous = NULL;
355  firstNode.gval = 0;
356  firstNode.hval = dist(A, B);
357  firstNode.enterHeight = -1;
358  firstNode.canStop = true;
359  firstNode.hasAttacked = veh->attacked;
360 
361  firstNode.h = A;
362  if ( !(actmap->getField(A)->unitHere(veh)) ) {
363  firstNode.h.setNumericalHeight(-1);
364  }
365  // insert the original node
366  open.pushOrUpdate(firstNode);
367  }
368  bool found = false;
369  const Node* N_ptr;
370 
371  // While there are still nodes to visit, visit them!
372  while( !open.empty() ) {
373  //N_ptr = visited.add(*open.begin());
374  N_ptr = visited.add(open.top());
375  open.pop();
376  // If we're at the goal, then exit
377  MapField* oldFld = actmap->getField(N_ptr->h);
378  for ( vector<MapCoordinate3D>::const_iterator i = B.begin(); i != B.end(); i++ )
379  if( N_ptr->h == *i ) {
380  if ( N_ptr->h.getNumericalHeight() == -1 || !(oldFld->building || (oldFld->vehicle && oldFld->vehicle != veh ))) {
381  found = true;
382  break;
383  }
384  }
385  if ( found )
386  break;
387 
388  if ( N_ptr->h.getNumericalHeight() == -1 ) {
389  // the unit is inside a container
390 
392  for ( int dir = 0; dir < 6; dir++ ) {
393  MapCoordinate3D pos = getNeighbouringFieldCoordinate ( N_ptr->h, dir );
394  if ( actmap->getField(pos)) {
395  int h = oldFld->getContainer()->vehicleUnloadable(veh->typ);
396  for ( int i = 0; i < 8; i++ )
397  if ( h & (1<<i)) {
399  if ( tio ) {
400  pos.setNumericalHeight(i);
401  Node N2 = Node();
402  if (!initNode(N2, N_ptr, pos, B, tio->disableAttack))
403  continue;
404 
405  if ( N2.canStop && actmap->getField(N2.h)->getContainer() && actmap->getField(N2.h)->vehicle != veh) {
406  // there's an container on the field that can be entered. This means, the unit can't stop 'over' the container...
407  N2.canStop = false;
408  open.pushOrUpdate ( N2 );
409 
410  // ... only inside it
411  N2.canStop = true;
412  N2.enterHeight = N2.h.getNumericalHeight() ;
413  N2.h.setNumericalHeight(-1);
414  // N2.hasAttacked = true;
415  if (!visited.find(N2.h))
416  open.pushOrUpdate ( N2 );
417  } else
418  open.pushOrUpdate ( N2 );
419  }
420 
421  }
422  }
423  }
424  }
425 
427  int dock = oldFld->getContainer()->vehicleDocking(veh, true );
428  for ( int dir = 0; dir < 6; dir++ ) {
429  if ( dock ) {
430  MapCoordinate3D pos = getNeighbouringFieldCoordinate ( N_ptr->h, dir );
431  MapField* fld = actmap->getField( pos );
432  if ( fld && fld->getContainer() && ( fld->getContainer() != oldFld->getContainer() ))
433  if ( fld->getContainer()->vehicleDocking(veh, false ) & dock )
434  if ( fld->getContainer()->getOwner() == oldFld->getContainer()->getOwner()
436  if ( !fld->building || (fld->bdt & getTerrainBitType(cbbuildingentry) ).any()) {
437  pos.setNumericalHeight(-1);
438  Node N2 = Node();
439  if ( !initNode(N2, N_ptr, pos, B, false, false, true) )
440  continue;
441  open.pushOrUpdate ( N2 );
442  }
443  }
444  }
445  }
446 
447 
448  } else {
449  // the unit is not inside a container
450 
451  const int* directions;
452  if ( !B.empty() && B.begin()->valid() ) {
453  directions = getDirectionOrder ( N_ptr->h.x, N_ptr->h.y, B.begin()->x, B.begin()->y );
454  } else {
455  static const int d[6] = {0,1,2,3,4,5};
456  directions = d;
457  }
458 
460 
461  // this check is actually only necessary for the very first field in which the unit starts.
462  // The unit may not be able to leave it, for example if a ship is frozen in ice
464 
465  for( int dci = 0; dci < 6; dci++ ) {
466  HexDirection dir = HexDirection(directions[dci]);
467  Node N2 = Node();
468  if ( !initNode(N2, N_ptr, getNeighbouringFieldCoordinate(N_ptr->h, dir), B) )
469  continue;
470  if ( N2.canStop && actmap->getField(N2.h)->getContainer() && actmap->getField(N2.h)->vehicle != veh) {
471  // there's an container on the field that can be entered. This means, the unit can't stop 'over' the container...
473  N2.canStop = false;
474  open.pushOrUpdate ( N2 );
475  }
476 
477  // ... only inside it
478  N2.canStop = true;
479  N2.enterHeight = N2.h.getNumericalHeight() ;
480  N2.h.setNumericalHeight (-1);
481  // N2.hasAttacked = true;
482  if (!visited.find(N2.h))
483  open.pushOrUpdate ( N2 );
484  } else
486  open.pushOrUpdate ( N2 );
487  }
488  }
489  }
490  // and now change the units' height. That's only possible on fields where the unit can stop it's movement
491 
492 
494  if ( (fieldAccessible ( oldFld, veh, N_ptr->h.getBitmappedHeight() ) == 2 ) || actmap->getgameparameter( cgp_movefrominvalidfields) )
495  for ( int heightDelta = -1; heightDelta <= 1; heightDelta += 2 ) {
496  const VehicleType::HeightChangeMethod* hcm = veh->getHeightChange( heightDelta, N_ptr->h.getBitmappedHeight());
497  if ( hcm ) {
498  for ( int dir = 0; (dir < 6 && hcm->dist) || (dir < 1 && !hcm->dist); dir++ ) {
499  MapCoordinate3D newpos = N_ptr->h;
500  bool access = true;
501  for ( int step = 0; step <= hcm->dist; step++ ) {
502  MapField* fld = actmap->getField(newpos);
503  if ( !fld ) {
504  access = false;
505  break;
506  }
507 
508  if ( !fieldAccessible ( fld, veh, N_ptr->h.getBitmappedHeight()) && (actmap->getgameparameter( cgp_movefrominvalidfields)==0 || step>0))
509  access = false;
510 
511  if ( !fieldAccessible( fld, veh, 1 << (N_ptr->h.getNumericalHeight() + hcm->heightDelta)) )
512  access = false;
513 
514  if ( fld && fld->building )
515  access = false;
516 
517  if ( step < hcm->dist ) {
518  newpos.x += getnextdx( dir, newpos.y );
519  newpos.y += getnextdy( dir );
520  } else {
521  if ( fld && (fld->building || (fld->vehicle && fld->vehicle != veh)))
522  access = false;
523  }
524  }
525 
526  MapField* fld = actmap->getField( newpos );
527  if ( fld && access ) {
528  newpos.setNumericalHeight(newpos.getNumericalHeight() + hcm->heightDelta);
529  bool enter = actmap->getField(newpos)->getContainer() && actmap->getField(newpos)->vehicle != veh;
530  Node N2 = Node();
531  if ( initNode(N2, N_ptr, newpos, B, false, enter ) != 2)
532  continue;
533  open.pushOrUpdate ( N2 );
534  }
535  }
536  }
537  }
538 
539 
540  }
541  }
542 
543  return found;
544 }
545 
546 bool AStar3D::constructPath( Path& path, const Node* n_ptr) {
547  if ( n_ptr == NULL )
548  return false;
549  for ( const Node* n = n_ptr; n != NULL; n = n->previous )
550  path.push_front ( PathPoint(n->h, int(n->gval), n->enterHeight, n->hasAttacked) );
551  return true;
552 }
553 
554 void AStar3D::findPath( Path& path, const MapCoordinate3D& dest )
555 {
556  vector<MapCoordinate3D> d;
557  d.push_back ( dest );
558  findPath ( path, d );
559 }
560 
561 
563 {
564  if ( markTemps )
565  actmap->cleartemps ( 3 );
566 
567  vector<MapCoordinate3D> v;
568  findPath ( v );
569  for ( VisitedContainer::iterator i = visited.begin(); i != visited.end(); ++i ) {
570  fieldAccess[i->h] |= i->h.getBitmappedHeight();
571 
572  if ( markTemps ) {
573  char atemp = actmap->getField ( i->h )->getaTemp();
574  actmap->getField ( i->h )->setaTemp( atemp | i->h.getBitmappedHeight());
575  }
576  }
577 
578  if ( markTemps )
580 }
581 
582 int AStar3D::getFieldAccess ( int x, int y )
583 {
584  return getFieldAccess( MapCoordinate(x, y) );
585 }
586 
588 {
589  fieldAccessType::iterator i = fieldAccess.find(mc);
590  return (i == fieldAccess.end()) ? 0 : i->second;
591 }
592 
593 void AStar3D::PathPoint::write( tnstream& stream ) const
594 {
595  stream.writeInt(1);
596  MapCoordinate::write( stream );
597  stream.writeInt( dist );
598  stream.writeInt( enterHeight );
599  stream.writeInt( hasAttacked );
600 }
601 
603 {
604  stream.readInt(); // version
605  MapCoordinate::read ( stream );
606  dist = stream.readInt();
607  enterHeight = stream.readInt(),
608  hasAttacked = stream.readInt();
609 }
610 
611 
613 {
614  PathPoint pp;
615  pp.read(stream);
616  return pp;
617 }
618 
620 {
621  for ( VisitedContainer::iterator i = visited.begin(); i != visited.end(); ++i ) {
622  dumpNode(*i);
623  }
624 }
625 
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
bool operator==(const AStar3D::Node &a, const AStar3D::Node &b)
Definition: astar2.cpp:122
void setaTemp(Uint8 atemp)
Various algorithms need to store some information in the fields they process.
Definition: mapfield.cpp:49
void cleartemps(int b=-1, int value=0)
Definition: gamemap.cpp:964
int fieldAccessible(const MapField *field, const Vehicle *vehicle, int uheight, const bool *attacked, bool ignoreVisibility)
Definition: spfst.cpp:124
Player & getPlayer(PlayerID p)
Definition: gamemap.h:257
float vehicleSpeedFactor[8]
Definition: astar2.h:81
int xsize
the size of the map
Definition: gamemap.h:201
virtual void writeInt(int i)
Writes a 32 bit signed Integer. In the stream little-endian byte order is used and a translation is p...
Definition: basestrm.cpp:363
int MAXIMUM_PATH_LENGTH
Definition: astar2.h:76
map accessing and usage routines used by ASC and the mapeditor
int maxMovement() const
the maximum distance that the unit can drive in a single turn on the current level of height ...
Definition: vehicle.cpp:1069
bool operator>(const Node &b) const
Definition: astar2.cpp:115
Vehicle * vehicle
Definition: mapfield.h:89
const int * getDirectionOrder(int x, int y, int x2, int y2)
Definition: astar2.cpp:293
bool valid() const
Definition: typen.h:221
virtual int readInt(void)
Reads a 32 bit signed Integer. In the stream little-endian byte order is used and a translation is pe...
Definition: basestrm.cpp:284
VisitedContainer visited
Definition: astar2.h:122
bool operator<(const Node &b) const
Definition: astar2.cpp:109
static const DistanceType longestPath
Definition: astar2.h:22
DiplomaticStateVector diplomacy
Definition: player.h:209
bool hasFunction(ContainerFunctions function) const
int getOwner() const
returns the number of the player this vehicle/building belongs to
virtual bool allowLeavingContainer()=0
bool unitHere(const Vehicle *veh)
checks if the unit is standing on this field. Since units are being cloned for some checks...
Definition: mapfield.cpp:311
float maxVehicleSpeedFactor
Definition: astar2.h:82
int getNumericalHeight() const
Definition: typen.h:242
void read(tnstream &stream)
Definition: typen.h:213
MapCoordinate3D getPosition() const
returns the units position
Definition: vehicle.cpp:1552
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
#define chhochfliegend
Definition: typen.h:416
storage_t::iterator iterator
Definition: astar2.h:104
ContainerBase * getContainer()
returns a pointer to the ContainerBase of the field or NULL if there is none
Definition: mapfield.cpp:331
The interface for all kinds of IO stream.
a single field of the map
Definition: mapfield.h:26
struct GameMap::Weather weather
bool hasAttacked
Definition: astar2.h:42
const VehicleType::HeightChangeMethod * getHeightChange(int dir, int height=0) const
returns the method for changing the height in the specified direction, or none if there is none...
Definition: vehicle.cpp:777
bool hasAttacked
Definition: astar2.h:69
virtual ~AStar3D()
Definition: astar2.cpp:173
vector< int > movement
the distance a unit can travel each round. One value for each of the 8 levels of height ...
Definition: vehicletype.h:203
const AStar3D::Node & top() const
Definition: astar2.cpp:40
virtual bool allowHeightChange()=0
int getDist(int dir)
void pop()
Definition: astar2.cpp:41
bool findPath(const MapCoordinate3D &dest)
searches for a path from the unit's current position to dest
Definition: astar2.cpp:335
int beeline(const Vehicle *a, const Vehicle *b)
returns the distance between the units a and b
void setNumericalHeight(int nh)
Definition: typen.h:243
pair< int, int > calcMoveMalus(const MapCoordinate3D &start, const MapCoordinate3D &dest, const Vehicle *vehicle, WindMovement *wm, bool *inhibitAttack, bool container2container)
Definition: controls.cpp:64
const int sidenum
the number of sides that a field has; is now fixed at 6;
Definition: typen.h:438
MapCoordinate3D getPosition3D() const
returns the units position; if inside building then Height is -1
Definition: vehicle.cpp:1557
int terrainaccessible(const MapField *field, const Vehicle *vehicle, int uheight)
Checks if the unit can drive on the field.
Definition: spfst.cpp:70
const Node * previous
Definition: astar2.h:63
int vehicleUnloadable(const VehicleType *vehicleType, int carrierHeight=-1) const
checks the unloading of a unit type
GameMap * tempsMarked
Definition: astar2.h:77
TerrainBits getTerrainBitType(TerrainBitTypes tbt)
virtual bool allowMovement()=0
void write(tnstream &stream) const
Definition: typen.h:212
#define chtieffliegend
Definition: typen.h:414
Coordinate on the twodimensional map.
Definition: typen.h:202
bool canStop
Definition: astar2.h:68
void pushOrUpdate(const AStar3D::Node &n)
Definition: astar2.cpp:43
WindMovement * wind
Definition: astar2.h:84
virtual bool allowDocking()=0
Uint8 getaTemp()
Definition: mapfield.cpp:52
int getnextdx(int dir, int y)
Definition: mapalgorithms.h:77
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
void dumpNode(const AStar3D::Node &n)
Definition: astar2.cpp:20
float DistanceType
Definition: astar2.h:21
const Node & back()
Definition: astar2.h:118
bool markTemps
Definition: astar2.h:83
int getnextdy(int dir)
Definition: mapalgorithms.h:80
int ysize
Definition: gamemap.h:201
DistanceType dist(const MapCoordinate3D &a, const MapCoordinate3D &b)
Definition: astar2.cpp:184
TerrainBits bdt
the terraintype properties. They determine which units can move over the field. This variable is reca...
Definition: mapfield.h:161
AStar3D::DistanceType hval
Definition: astar2.h:66
caches some calculations for the effects that wind has on the movement of units
HexDirection
Definition: astar2.h:15
static int windbeeline(const MapCoordinate &start, const MapCoordinate &dest, const WindMovement *wm)
Definition: astar2.cpp:53
int getgameparameter(GameParameter num) const
Definition: gamemap.cpp:1047
int height
the levels of height which this unit can enter
void write(tnstream &stream) const
Definition: astar2.cpp:593
const ContainerBaseType::TransportationIO * vehicleUnloadSystem(const VehicleType *vehicle, int height)
returns the unloading system
void read(tnstream &stream)
Definition: astar2.cpp:602
void dumpVisited()
for debugging: dumps the contents of the visited node to stdout
Definition: astar2.cpp:619
static PathPoint newFromStream(tnstream &stream)
Definition: astar2.cpp:612
int getBitmappedHeight() const
Definition: typen.h:241
deque< PathPoint > Path
Definition: astar2.h:48
const VehicleType * typ
Definition: vehicle.h:83
bool isAllied(PlayerID towardsPlayer) const
Definition: player.h:82
int getFieldAccess(int x, int y)
Definition: astar2.cpp:582
bool attacked
did the unit already attack this turn
Definition: vehicle.h:109
Coordinate on the map including height.
Definition: typen.h:238
Building * building
Definition: mapfield.h:102
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
int empty() const
Definition: astar2.cpp:42
GameMap * getMap() const
const T & max(const T &a, const T &b, const T &c)
Definition: misc.h:97
fieldAccessType fieldAccess
Definition: astar2.h:89
const T & min(const T &a, const T &b, const T &c)
Definition: misc.h:80
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 vehicleDocking(const Vehicle *vehicle, bool out) const
returns the levels of height on which this unit can be transfered by docking; or 0 if no unloading is...
AStar3D::DistanceType gval
Definition: astar2.h:65
#define chfliegend
Definition: typen.h:415
Path * _path
Definition: astar2.h:78
Interface for the A* pathfinding algorithm.
#define minmalq
Definition: typen.h:430
MapCoordinate3D getNeighbouringFieldCoordinate(const MapCoordinate3D &pos, int direc)
returns the coordinate of the field that is adjecent to the given field in the direction of direc ...
The map. THE central structure of ASC, which holds everything not globally available together...
Definition: gamemap.h:182
MapField * getField(int x, int y)
Definition: gamemap.h:465
MapCoordinate3D h
Definition: astar2.h:64