ST_ForceField.H

Go to the documentation of this file.

#ifndef ST_FORCEFIELD_H
#define ST_FORCEFIELD_H

//Comments coming soon, sorry...
// This is an ORTS file
// (c) Michael Buro, Sami Wagiaalla, David Deutscher, Nick Wiebe
// licensed under the GPL

// Local Pathfinder using ForceFields to execute paths,
// and interface to global (simple a*) pathfinder.


#include "TerrainBasicImp.H"
#include "Random.H"
#include "Coord.H"
#include "SimpleTerrain.H"

#include "boost/shared_ptr.hpp"

namespace SimpleTerrain{

  typedef TerrainBase::Loc      Loc;
  typedef TerrainBase::Segment  Segment;
  typedef TerrainBase::Task     Task;

  /** Structure to keep data associated to a path
      fixme: right now this inherits from UnitPath, from SimpleTerrain,
      but that doesn't make much sense. This was done primarily for convenience.
   */
  struct UnitPath_FF : public 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
    //@}

    bool replanned;

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

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


  /** Functor that allows Locations to be put into sets*/
  class Loc_less : public std::binary_function<Loc, Loc, bool>{
  public:
    bool operator() (Loc a, Loc b) const;
  };

  /** Two Dimensional Vector */
  class Vec_2D{
  public:
    sint4 x;/// x-coord
    sint4 y;/// y-coord
    Vec_2D(sint4 x_=0, sint4 y_=0) :  x(x_), y(y_){};
    Vec_2D(const Vec_2D &other) :  x(other.x), y(other.y){};
    Vec_2D(const Loc &a, const Loc &b) : x(b.x - a.x), y(b.y - a.y) {};
    Vec_2D operator+(const Vec_2D &other) const; ///Vector addition
    Vec_2D operator-(const Vec_2D &other) const; ///Vector subtraction
    Vec_2D project_onto(const Vec_2D &other) const; /// Project the vector onto the line defined by the given vector
    sint4 dot_prod(const Vec_2D &other) const;
    real8 length() const;
    Vec_2D multiply(real8 k) const;
    bool operator==(const Vec_2D &other) const;
    bool operator!= (const Vec_2D &other) const;

    inline static sint4 round(real8 real) {
      return (sint4)floor(real + 0.5);
    }
  };

  /// The internal data complementing Task data:
  struct FF_Task {
    Task task;
    bool isPending;
    bool isFailed;
    bool noPathFound;
    boost::shared_ptr<UnitPath_FF> path;    // todo: replace with a cleaner implementation
    //Vector<const Object*> followers;
    uint4 replanned;
    //sint4 ticks; //used for automatic replanning when moving to a mobile object

    FF_Task(const Task& task_)
      : task(task_), isPending(true), isFailed(false), noPathFound(false), replanned(0) {};
    FF_Task(const FF_Task& other)
      : task(other.task), isPending(other.isPending),
    isFailed(other.isFailed), noPathFound(other.noPathFound),
      path(other.path), /*followers(other.followers),*/ replanned(other.replanned) {};
    void set_path(const Object *obj_, const Vector<Loc> &path_);
    //void init_path(const Object *obj_, const Vector<Loc> &path_) { path=boost::shared_ptr<UnitPath>(new UnitPath(obj_, path_)); };
    bool isValid() const { return !isPending && !isFailed && !noPathFound && path; };
  private:
    FF_Task operator=(const FF_Task& other);
  };

  /// An implementation of the TerrainBase interface using forcefields for local
  /// pathfinding.
  class ST_ForceField : public TerrainBasicImp<FF_Task>
  {
  public:

    ST_ForceField();
    virtual ~ST_ForceField() {};

    /// 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<TerrainBase::Segment> &s);

    virtual void cancel_task(const Object *obj);
    virtual void remove_task(TaskId tid);
    TaskId execute_task(const Task &task, const Path &path);

    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);

    //@}
    //---------------------------------------------------------------------

    // public to allow REGISTER_TYPEOF definitions
    typedef std::map<const Object*, Loc>  Obj2LocMap;
    typedef std::map<Loc, bool, Loc_less> SegmentEndsMap;

  private:

    /** 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);
    /** 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);
    /** 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);
    static bool is_in_range(const Object *moving_obj, const Loc goal_loc);

    /** Add a move command to the Vector of commands, telling the object to
    move to the target location at maximum speed.
    Also, updates the location associated with the object for forcefield purposes
    */
    void add_move_command(const Object *obj, Loc target, Vector<TerrainBase::MoveCmd> &cmds);
    /** Determines what team an object is on.
    If the team cannot be determined, returns -1 */
    sint4 what_team(const Object *obj);

    //---------------------------------------------------------------------
    /// \name Force Field methods
    //---------------------------------------------------------------------
    //@{
    /**
    Calculates the direction that an object should move to, based on the path
    they are following and any obstacles in the vicinity.
    @param path Path data
    @param output reference to a location that in the direction that the object should
    move to.
    fixme: maybe a location should be returned, instead of the pass by reference
    */
    void get_forcefield_target(UnitPath_FF &path, Loc &output);

    /**
      @param object The object that is moving
      @param attractor The point that is attracting the object
      @param output reference to a location that is in the direction that the
      object should move to.
    */
    void get_forcefield_target(const Object *obj, const Loc &attractor, Loc &output);

    /** used for pushing, where there is no attractor*/
    void get_push_target(const Object *obj, Loc &output);


    /** Adjusts the vector so that it is not directed more than 90 degrees on either side
    of the target vector.*/
    void restrict_vector(const Vec_2D &target_vec, Vec_2D &vec);

    /** Finds the location of point on a line that is closest to the given location*/
    Loc find_point_on_line(Loc loc, Loc line_start, Loc line_end);

    /** Calculates the repulsion caused by a point on an object and returns
    it as a vector*/
    Vec_2D get_point_repulsion(const Object *moving_obj, const Loc &point, sint4 radius = 0);

    /** Calculates the repulsion caused by a line on an object and returns
    it as a vector */
    Vec_2D get_line_repulsion(const Object *moving_obj, const Segment &seg);

    /** Calculates the position of the attractor along the path.
    The attractor is positioned a set distance ahead of the point closest to the
    object on the path.
     */
    Loc get_attractor(UnitPath_FF &path);

    //@}
    Obj2LocMap      objects;      ///< Used to calculate object repulsion
    Vector<Segment> segments;     ///< Used to calculate wall repulsion
    SegmentEndsMap  segment_ends; ///< Used to calculate repulsion from the ends of walls

    boost::shared_ptr<ST_Terrain::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 pushing_on;
    bool wp_attract;
    bool stop_to_plan;

    /** This multiplied by the max speed of an object gives the range at which objects
    and walls will exert a force on the objec*/
    static const sint4 FIELD_RANGE_MULTIPLIER = 2;

    /** The strength of attractors (does not vary with distance)*/
    static const sint4 ATTRACTOR_FORCE = 26;

    /** This divided by the distance squared to the moving object gives the strength
    of the repulsors*/
    static const sint4 REPULSOR_BASELINE = 200;

    /** No longer used*/
    static const sint4 WAYPOINT_PROX = 2;

    /** this multiplied by the object max speed gives the distance
    ahead of the object on the path that the attractor will be set to*/
    static const sint4 PATH_LOOK_AHEAD = 3;

    //static const uint4 REPLAN_HARDCAP = 2; ///< Max number of replans for a task
    //static const sint4 REPLAN_TRIGGER = 5; ///< Number of occilation steps before a replan will be triggered
    //static const sint4 OCCILATION_TRIGGER = 15;  ///< Number of occilation steps before a path movement failure will be passed

    static const uint4 REPLAN_HARDCAP =2; ///< Max number of replans for a task
    static const sint4 REPLAN_TRIGGER = 5; ///< Number of occilation steps before a replan will be triggered
    static const sint4 OCCILATION_TRIGGER = 15;  ///< Number of occilation steps before a path movement failure will be passed
    //GameStateModule &gms;

    friend class SimpleTerrainWidget;
    friend class SimpleTerrainOverlay;
    friend class ST_Terrain::PFEngine;
  };

}

REGISTER_TYPEOF(2601, SimpleTerrain::ST_ForceField::Obj2LocMap::iterator);
REGISTER_TYPEOF(2602, SimpleTerrain::ST_ForceField::Obj2LocMap::const_iterator);
REGISTER_TYPEOF(2603, SimpleTerrain::ST_ForceField::SegmentEndsMap::iterator);
REGISTER_TYPEOF(2604, SimpleTerrain::ST_ForceField::SegmentEndsMap::const_iterator);
REGISTER_TYPEOFS_TerrainBasicImp_ForEach(2605, SimpleTerrain::FF_Task);

#endif