astar2.h

Go to the documentation of this file.

#ifndef astar2H
 #define astar2H


 #include <vector>
 #include <map>
 #include <set>
 #include "mapalgorithms.h"
 #include "gamemap.h"




 enum HexDirection { DirN, DirNE, DirSE, DirS, DirSW, DirNW, DirNone };


 class AStar {
    public:
       typedef vector<MapCoordinate> Path;

    protected:
       int MAXIMUM_PATH_LENGTH;
       GameMap* tempsMarked;
       Path *_path;
       Vehicle* _veh;
       GameMap* _actmap;


       virtual int getMoveCost ( int x1, int y1, int x2, int y2, const Vehicle* vehicle );
    public:
       AStar ( GameMap* actmap, Vehicle* veh );

       struct HexCoord{
           int m, n;
           HexCoord(): m(0), n(0) {}
           HexCoord( int m_, int n_ ): m(m_), n(n_) {}
           ~HexCoord() {}
       };

       struct Node {
           HexCoord h;        // location on the map, in hex coordinates
           int gval;        // g in A* represents how far we've already gone
           int hval;        // h in A* represents an estimate of how far is left
           Node(): h(0,0), gval(0), hval(0) {}
           bool operator< ( const Node& a );
       };

       int dist( HexCoord a, HexCoord b );

       typedef std::vector<Node> Container;
       greater<Node> comp;

       inline void get_first( Container& v, Node& n );


       Container visited;

       void findPath( HexCoord A, HexCoord B, Path& path );

       void findPath( Path& path, int x, int y );

       void findAllAccessibleFields ( int maxDist = maxint );  // all accessible fields will have a.temp set to 1

       int getDistance( );

       int getTravelTime( );

       bool fieldVisited ( int x, int y);
      
       virtual ~AStar ( );
 };


extern void findPath( GameMap* actmap, AStar::Path& path, Vehicle* veh, int x, int y );



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 {
          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;
       };

       typedef vector<PathPoint> Path;
       struct Node {
           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
           bool canStop;
           bool hasAttacked;
           int enterHeight;
           Node(): gval(0), hval(0), canStop(false), enterHeight(-1), deleted(false) {}
           bool deleted;
           bool operator< ( const Node& b ) const;
       };

    protected:
       OperationLimiter* operationLimiter;
       int MAXIMUM_PATH_LENGTH;
       GameMap* tempsMarked;
       Path *_path;
       Vehicle* veh;
       GameMap* actmap;
       float vehicleSpeedFactor[8];
       bool markTemps;
       WindMovement* wind;

       virtual DistanceType getMoveCost ( const MapCoordinate3D& start, const MapCoordinate3D& dest, const Vehicle* vehicle, bool& canStop, bool& hasAttacked );

       HexDirection* posDirs;
       int*          posHHops;
       int*          fieldAccess;

       HexDirection& getPosDir ( const MapCoordinate3D& pos ) { return posDirs [(pos.y * actmap->xsize + pos.x) * 9 + 1+pos.getNumericalHeight()]; };
       int& getPosHHop ( const MapCoordinate3D& pos )         { return posHHops[(pos.y * actmap->xsize + pos.x) * 9 + 1+pos.getNumericalHeight()]; };

       DistanceType dist( const MapCoordinate3D& a, const MapCoordinate3D& b );
       DistanceType dist( const MapCoordinate3D& a, const vector<MapCoordinate3D>& b );

    public:

       class Container: protected multiset<Node, less<Node> > {
          public:
             typedef multiset<Node, less<Node> > Parent;

             // Container() {};
             void add ( const Node& node ) { insert ( node ); };
             bool update ( const Node& node );
             Node getFirst() { Node n = *Parent::begin(); Parent::erase ( Parent::begin() ); return n; };
             bool empty() { return Parent::empty(); };


             typedef Parent::iterator iterator;
             iterator find( const MapCoordinate3D& pos );

             iterator begin() { return Parent::begin(); };
             iterator end() { return Parent::end(); };

       };

       Container visited;
       // vector<Node> visited;
    protected:

       
       bool get_first( Container& v, Node& n );

       void nodeVisited ( const Node& n, HexDirection direc, Container& open, int prevHeight = -10, int heightChangeDist = 0 );


    public:
       AStar3D ( GameMap* actmap, Vehicle* veh, bool markTemps_ = true, int maxDistance = maxint );


       void registerOperationLimiter( OperationLimiter* ol ) { operationLimiter = ol; };

       void findPath( const MapCoordinate3D& A, const vector<MapCoordinate3D>& B, Path& path );

       void findPath( Path& path, const MapCoordinate3D& dest );

       void findPath( Path& path, const vector<MapCoordinate3D>& dest );

       void findAllAccessibleFields (  );

       int getDistance( );

       int getTravelTime( );

       const Node* fieldVisited ( const MapCoordinate3D& fld );

       int& getFieldAccess ( int x, int y );
       int& getFieldAccess ( const MapCoordinate& mc );

       virtual ~AStar3D ( );
 };

#endif

---