SimpleTerrain.H

Go to the documentation of this file.

#ifndef SimpleTerrain_H
#define SimpleTerrain_H

// $Id: SimpleTerrain.H 5279 2007-06-23 02:49:08Z mburo $

// This is an ORTS file 
// (c) Michael Buro, Sami Wagiaalla, David Deutscher
// licensed under the GPL

// simple grid-based terrain representation

#include "Global.H"
#include "TerrainBasicImp.H"
#include "ST_SimpleMap.H"
#include "Random.H"
#include "Coord.H"
#include "Distance.H"

#include "boost/shared_ptr.hpp"


namespace SimpleTerrain {

  typedef TerrainBase::Loc              Loc;
  typedef TerrainBase::Segment          Segment;  
  typedef TerrainBase::Task             Task;
  typedef TerrainBase::Path             Path;
  typedef TerrainBase::Goal             Goal;
  typedef TerrainBase::MoveCmd          MoveCmd;
  typedef TerrainBase::StatusMsg        StatusMsg;
  typedef TerrainBase::TaskId           TaskId;
  typedef TerrainBase::ConsiderObjects  ConsiderObjects;

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
  /// make a CIRCLE Object appear to be at an arbitrary location
  struct ObjectTranslocator : public Object {
    const Object *obj;
    sint4 newx, newy;

    ObjectTranslocator(const Object *obj_) : obj(obj_), newx(0), newy(0) { 
      assert(obj->get_shape() == Object::CIRCLE);
    };
    void set_position(sint4 newx_, sint4 newy_) { newx = newx_; newy = newy_; };

    // make it look like it's in a new location
    void  get_center(sint4 &x, sint4 &y, sint4 *px=0, sint4 *py=0) const
      { x = newx; y = newy; if(px) *px = newx; if(py) *py = newy; };
    real8 distance_to(const Object &other) const 
      { return Distance::distance(*this, other); };

    // forward calls to the internal 'real' object
    Shape get_shape() const               { return obj->get_shape(); };
    sint4 get_max_speed() const           { return obj->get_max_speed(); };
    sint4 get_radius() const              { return obj->get_radius(); };
    ZCat  get_zcat(ZCat *prev=0) const    { return obj->get_zcat(prev); };
    sint4 get_speed(sint4 *prev=0) const  { return obj->get_speed(prev); };
    bool  get_moving(bool *prev=0) const  { return obj->get_moving(prev); }; 
    bool is_pending_action(void) const    { return obj->is_pending_action(); };

    // not relevant for circles
    void get_p1(sint4 &, sint4 &, sint4 *, sint4 *) const { assert(0 && "Unimplemented for SimpleTerrain::ObjectTranslocator"); }; 
    void get_p2(sint4 &, sint4 &, sint4 *, sint4 *) const { assert(0 && "Unimplemented for SimpleTerrain::ObjectTranslocator"); };
  };

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
  // fixme: Transfer this functionality into ST_Task, this is a heritage from before
  // the TerrainBase interface.
  struct UnitPath
  {
    /// Path data
    //@{
    const Object *obj;
    Vector<Loc> path;
    Loc goal;
    int current_target; // index of current way point in path vector
    bool no_orders_yet; // true at the beginning, before the first move command is issued
    //@}

    /// Collision avoidance and resolution
    //@{
    // If adding fields - check ST_Task::set_path for needed updates.
    bool stopped_to_avoid_collision; // true if the object was stopped temporarily to avoid a collision
    int collision_step; // this is incremented while solving unexpected stops
    uint4 wakeup;       // if SDL_GetTicks() >= wakeup then this UnitPath is not
                        // sleeping ie not to be skipped over.
    Loc spot;           // spot of the last unexpected collision
    //@}

    UnitPath(const Object *obj_, const Vector<Loc> &path_);
    ~UnitPath() {};

    void mark_spot(const Loc &p) { spot = p; };
    void sleep(int time) { wakeup = SDL_GetTicks() + time; };
    bool sleeping() const { return wakeup > SDL_GetTicks(); };

    bool is_intersect(const Segment &) const;
  };


  /// The internal data complementing Task data:
  struct ST_Task {
    Task task;                           //< This is the actual task and is characterized by:
    bool isPending;                      //< pending or yet to be planned
    bool isFailed;                       //< failed, and try to replan 
    bool noPathFound;                    //< could not find a path to that location 
    boost::shared_ptr<UnitPath> path;    // todo: replace with a cleaner implementation

    // These are used to calculate the approximate priority of the task:

    /// When was the task created, as return by SDL_GetTicks()
    uint8 start_time;
    /// Straight-line length of the path, to prefer planning shorter paths first
    real8 path_dist;
 
    ST_Task(const Task& task_);
    ST_Task(const ST_Task& other) 
      : task(other.task), isPending(other.isPending),
        isFailed(other.isFailed), noPathFound(other.noPathFound), path(other.path),
        start_time(other.start_time), path_dist(other.path_dist) {};
    void set_path(const Object *obj_, const Vector<Loc> &path_);
    bool isValid() const { return !isPending && !isFailed && !noPathFound && path; };
  private:
    ST_Task operator=(const ST_Task& other);
  };

  /// The definition of a square using two corners.
  struct UnitSquare {
    Loc topLeft;
    Loc bottomRight;
    const Object *obj;
    ST_Task *task;

    UnitSquare() : obj(NULL), task(NULL) {};
    UnitSquare(Loc topLeft_, Loc bottomRight_, const Object *obj_, ST_Task *task_)
      : topLeft(topLeft_), bottomRight(bottomRight_), obj(obj_), task(task_) {};
    ~UnitSquare() {};

    UnitSquare& operator=(const UnitSquare& other) {
      if( this != &other ) {
        topLeft = other.topLeft;
        bottomRight = other.bottomRight;
        obj = other.obj;
        task = other.task;
      }
      return *this;
    }
    
  };

  /** A sector is a large area, containing objects (actually tasks) whose paths 
      in the near future will pass through the area, and hence may collide. */
  struct Sector {
    Vector<ST_Task*> tasks;
    
    Sector() {};
    Sector(const Sector &other) : tasks(other.tasks) {};
    Sector& operator=(const Sector &other) { 
      if( this != &other ) 
        tasks = other.tasks; 
      return *this; 
    };
  };

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

  /// A Simple implementation of the TerrainBase interface.
  /** This TerrainBase implementation is using a relatively basic Astar algorithm,
      originally written by Sami Wagiaalla and adapted by David Deutscher. 
      Limitations:
      - Only considers a single Obj per Task (ignoring the second and on obj_ids).
      - Assumes all objects are either ON_LAND or IN_AIR (and that boundaries do not 
        apply to the latter, though this is currently always true so it's not really a
        limitation).
      - Using a target *object*:
        a) No pursuit is implemented. Instead, the target location at the moment 
           of pathfinding is used as the goal.
        b) If the object is removed, it's last known location is used as goal.
        Nonetheless, it is useful (mainly for static targets) since it allows a 
        'touch' condition - where the unit is not really at the exact goal location -
        to be reported as a successful arrival and not retried.
  */
  class ST_Terrain : public TerrainBasicImp<ST_Task>
  {
  public:
    ST_Terrain();
    virtual ~ST_Terrain() {};

    /// add command-line options specific to this implementation, using static methods of class Options
    static void add_options(void);

    //---------------------------------------------------------------------
    /// \name Implementation of relevant parts of the TerrainBase interface
    //---------------------------------------------------------------------
    //@{
    virtual void init(sint4 tiles_x_, sint4 tiles_y_, sint4 tile_points_, sint4 client_pID_, sint4 neutral_pID_);

    virtual void add_obj(const Object *obj);
    virtual void update_obj(const Object *obj);
    virtual void remove_obj(const Object *obj);
    virtual void add_segments(const Vector<Segment> &s);

    virtual void cancel_task(const Object *obj);
    virtual void remove_task(TaskId tid);

    virtual void execute_tasks(Vector<MoveCmd> &cmds, Vector<StatusMsg> &msgs);
    virtual bool plan_tasks(uint4 max_time=0);

    virtual real8 find_path(const Loc &l1, const Loc &l2, sint4 radius, Path *path, ConsiderObjects consider = CONSIDER_ALL);
    virtual real8 find_path(const Object *obj, const Goal &goal, Path *path, ConsiderObjects consider = CONSIDER_ALL);
    //@}
    //---------------------------------------------------------------------

   
    //---------------------------------------------------------------------
    /// \name Richer interfaces, candidates for adding to TerrainBase
    //---------------------------------------------------------------------
    //@{
    /// mark the path as an obstacle to be avoided in future PFing.
    void block_path(const Object *obj, const Path &path);
    /** Release a previously marked obstacle-path. 
        Releasing an unblocked-path might corrupt the inner world view. */
    void release_path(const Object *obj, const Path &path);
    /** Execute a previously planned path. The waypoints are assumed
        to be in forward order, as returned by TerrainBase::find_path().
        The caller is responsible that the given arguments are consistent. */
    TaskId execute_task(const Task &task, const Path &path);
    //@}
    //---------------------------------------------------------------------


    /// The mechanics of world representation and basic A* path-finding
    class PFEngine; friend class ST_Terrain::PFEngine;

  private:

    // prevent copying as we currently don't need it.
    ST_Terrain(const ST_Terrain& other);
    ST_Terrain operator=(const ST_Terrain& other);

  protected:
 
    //---------------------------------------------------------------------
    /// \name Internal accessories
    //---------------------------------------------------------------------
    //@{
    /// Define the maximum amount of time that a long distance task can be put off
    static const uint4 MAXIMUM_TASK_AGE;

    /** Perform PF for a single pending task, and insert results to data structures. 
        Return true iff did some planning. */
    bool plan_pending_task(uint4 stop_time = 0);
    /** Perform PF for a single failed task, and insert results to data structures. 
        Return true iff did some planning. */
    bool plan_failed_task(uint4 stop_time = 0);
    /** Accessory function for planning either a pending or a failed task. */
    void plan_task(TIter tit, uint4 stop_time);
    /** Randomly choose a failed task. Return tasks.end() if no failed task exists. */
    TIter get_random_failed_task(void);
 
    /** Invalidate existing paths that intersect a given new boundary. */
    void invalidate_paths(const Vector<Segment> &segments);
    
    /** Test if the object is at the given location, 
    accounting for a 1-tick look-ahead for moving objects. */
    static bool is_at_location(const Object* obj, const Loc& target);
    /** Test if the distance from the object to the target is within the given range.*/
    static bool is_near_location(const Object* obj, const Loc& target, sint4 range);
    /** Test if the object is at the goal of the given task, implementing 
        (some) of the various definitions of 'goal'. */
    bool is_at_goal(const Object* obj, const Task& task);
    /** Test if the object is within firing range */
    static bool is_in_range(const Object* moving_obj, const Object *goal_obj);
    /** Test if the location is within firing range */
    static bool is_in_range(const Object* moving_obj, const Loc goal_loc);
   
    /** Find the best task to plan now.  This is based on the task's age and also
    how short its path is.*/
    std::deque<TIter>::iterator get_best_task(void);

    /// Create a MoveCmd for the current waypoint of the given UnitPath, and add to the vector.
    static void add_move_command(const UnitPath& path, Vector<MoveCmd> &cmds);
    //@}
    //---------------------------------------------------------------------


    //---------------------------------------------------------------------
    /// \name Local obstacle avoidance
    //---------------------------------------------------------------------
    //@{
    /// Anticipate and handle collisions that are expected to occur in the next X ticks.
    static const sint4 ANTICIPATE_COLLISION_TICKS;
    /// Compute expected collisions using integral coordinates but with a higher accuracy.
    static const sint4 FINE_GRID_RES_BITS;

    /// Identify and resolve expected collisions between controlled units.
    void resolve_friendly_collisions(void);
    /** true iff the objects of the given tasks will collide before 
        reaching their next waypoint, and within the ANTICIPATE_COLLISION_TICKS 
        next ticks. */
    bool will_collide(Vector<ST_Task*>::iterator i, 
              Vector<ST_Task*>::iterator j, 
                      bool assume_obj1_stopped=false, 
                      bool assume_obj2_stopped=false);
    /// Convert to the higher resolution
    static sint4 fine_grid(sint4 v) { return v << FINE_GRID_RES_BITS; };
    /** \brief Get the position of a given object and its heading towards a given target, using fine coordinates.
        Compute the spatial params (position, target, velocity) using the fine-grid
        coordinates.
        @param o              The object
        @param target         The location it is moving to, in world (not fine) coordinates. This will be translated to fine coords as output.
        @param fine_position  If != NULL, will contain o's position in fine coords, as output.
        @param fine_velocity  If != NULL, will contain o's velocity (direction+speed) in fine coords, as output.
    */
    void get_fine_spatial_params(const Object *o, ScalarPoint &target,
                                 ScalarPoint *fine_position, ScalarPoint *fine_heading);
    //@}
    //---------------------------------------------------------------------


    //---------------------------------------------------------------------
    /// \name Motion Sectors for faster collision detection - James Bergsma
    //---------------------------------------------------------------------
    //@{
    /// How many tiles per motion sector (side)
    static const uint4 TILES_PER_MOTION_SECTOR;

    /** Find the position of an object in 'when' ticks. 
        For multiple-waypoints paths, this is only an approximation:
        1. It assumes a continuous motion, disregarding the rounding of the
           time it takes to travel each straight line leg of the path to 
           integer ticks (rounding done by the ORTS engine).
        2. It doesn't consider delays in giving the "go to next 
           waypoint" actions (eg due to network lag or slow client sise 
           processing), which cause the unit to stop at waypoints.

        @param  cur_path  The path to analyze.
        @param  when      Compute the location in that many ticks.
        @param  where     Returns the future position in this parameter.
        @return the waypoint number (0 is first waypoint, located at the back() 
                of cur_path.path) that will already be passed through by 
                that time, -1 if the first waypoint will not be reached.
    */
    sint4 get_future_position(const UnitPath &cur_path, sint4 when, Loc &where);

    /** Using a future position create a square containing the object. 
        @param task   The task to analyze. Assuming that task->path is valid.
        @return       The UnitSquare that will contain the object in the close future.
    */   
    UnitSquare find_motion_square(const TIter &task);

    /** Insert each motion square into the sectors that contain it. Sectors
        with >= 2 squares are marked as active (meaning they should be 
        tested for potential collisions. 
    @param motionSquares    These are the squares in which units are currently active.
    @param sectors          This is a large grid representation in which the sectors will be placed.
    */
    void insert_into_sectors(const Vector<UnitSquare> &motionSquares,
                                         SimpleMap<Sector> &sectors);
    //@}
    //---------------------------------------------------------------------


    boost::shared_ptr<PFEngine> pfEngine; ///< The internal Path Finding engine
    std::set<const Object*> objsToStop;   ///< Objects for which we should set a stop-moving action
    Random rand;
    bool noMotionSectors;                ///< Should the motion sectors optimization be used for collision detection

    friend class SimpleTerrainWidget;
    friend class SimpleTerrainOverlay;
  };

} // end of namespace SimpleTerrain

REGISTER_TYPEOF(2501, Vector<SimpleTerrain::Sector>::iterator);
REGISTER_TYPEOF(2502, Vector<SimpleTerrain::Sector>::const_iterator);
REGISTER_TYPEOF(2503, Vector<SimpleTerrain::Sector*>::iterator);
REGISTER_TYPEOF(2504, Vector<SimpleTerrain::Sector*>::const_iterator);
REGISTER_TYPEOF(2505, Vector<SimpleTerrain::ST_Task*>::iterator);
REGISTER_TYPEOF(2506, Vector<SimpleTerrain::ST_Task*>::const_iterator);
REGISTER_TYPEOF(2507, Vector<const SimpleTerrain::ST_Task*>::iterator);
REGISTER_TYPEOF(2508, Vector<const SimpleTerrain::ST_Task*>::const_iterator);
REGISTER_TYPEOF(2509, Vector<SimpleTerrain::UnitSquare>::iterator);
REGISTER_TYPEOF(2510, Vector<SimpleTerrain::UnitSquare>::const_iterator);
REGISTER_TYPEOFS_TerrainBasicImp_OneTime(2511, SimpleTerrain::ST_Task);
REGISTER_TYPEOFS_TerrainBasicImp_ForEach(2515, SimpleTerrain::ST_Task);
#endif